Rearranged .. might not be more efficient. I think yours might detect some early signs that the test will eventually fail that mine misses.

($num,$base) = @ARGV;
$orig = $num;
$exp = int(log($num)/log($base));
while ($exp) {
  $try = $base ** $exp--;
  if ($try > $num) {
    $bin .= "0"; next 
  }
  $num -= $try if ($try <= $num);
  die "Nope!" if ($try <= $num);
  $bin .= "1"
}
if ($num > 1) {
  die "Nope!"
} else {
  $bin .= $num ? "1" : "0";
  print "$orig in base $base: $bin\n";
}
[download]

Update: written as subroutine that returns 1 if the number can be expressed purely in 1's and 0's:

sub hp_only_1_0_in_base_x {
  ($num,$base) = @_;
  $exp = int(log($num)/log($base));
  while ($exp) {
    $try = $base ** $exp--;
    next if ($try > $num);
    $num -= $try;
    return 0 if ($try <= $num);
  }
  return ($num > 1) ? 0 : 1
}
[download]

Update 2: removed superfluous test in line 7