Q:

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 

A:

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.

A:

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

