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
  ...
}