determine power of number

i know that if number is power of two,then it must satisfy (x&(x-1))=0; for example let's take x=16 or 10000 x-16=10000-1=01111 and (x&(x-1))=0; for another non power number 7 for example, 7=0111,7-1=0110 7&(7-1)=0110 which is not equal 0,my question how can i determine if number is some power of another number k? for example 625 is 5^4,and also how can i find in which power is equal k to n?i am interested using bitwise operators,sure i can find it by brute force methods(by standard algorithm,thanks开发者_开发知识库 a lot

I doubt you're going to find a bitwise algorithm for determining that a number is a power of 5.

In general, given y = n^x, to find x, you need to use logarithms, i.e. x = log_n(y). Most languages don't offer a log_n function, but you can achieve it with the following identity:

log_n(y) = log(y) / log(n)

If y is an integer power of n, then x will be an integer. Of course, due to the limitations of finite-precision computer arithmetic, you won't necessarily get the exact answer with the method above.

I'm afraid, you can't do that with just simple bit magic. Bits are typically good for powers of 2. For powers of, say, 5 you'd probably need to operate in base-5 system, where 1₅=1₁₀, 10₅=5₁₀, 100₅=25₁₀, 1000₅=125₁₀, 10000₅=625₁₀, etc. In base-5 system you can recognize powers of 5 just as easily as powers of 2 in binary. But you'd first need to convert your numbers to that base.

For arbitrary k there is only the generic solution:

bool is_pow(unsigned long x, unsigned int base) {
  assert(base >= 2);
  if (x == 0) {
    return false;
  }
  unsigned long t = x;
  while (t % base == 0) {
    t /= base;
  }
  return t == 1;
}

When k is a power of two, you can speed things up by checking whether x is a power of two and whether the number of trailing zero bits of x is divisible by log2(k).

And if computational speed is important and your k is fixed, you can always use the trivial implementation:

bool is_pow5(unsigned long x) {
  if (x == 5 || x == 25 || x == 125 || x == 625)
    return true;
  if (x < 3125)
    return false;
  // you got the idea
  ...
}