Check if one integer is an integer power of another

This is an interview question: "Given 2 integers x and y, check if x is an integer power of y" (e.g. for x = 8 and y = 2 the answer is "true", and for x = 10 and y = 2 "false").

The obvious solution is:

int n = y; while(n < x) n *= y; return n == x

Now I am thinking about how to improve it.

Of course, I can check some special cases: e.g. both x and y should be either odd or even numbers, i.e. we can check the least significant bit of x and y. However I wonder if I can improve the core algorithm itself.

You'd do better to repeatedly divide y into x. The first time you get a non-zero remainder you know x is not an integer power of y.

while (x%y == 0)  x = x / y
return x == 1

This deals with your odd/even point on the first iteration.

It means log_y(x) should be an integer. Don't need any loop. in O(1) time

public class PowerTest {

    public static boolean isPower(int x, int y) {
        double d = Math.log(Math.abs(x)) / Math.log(Math.abs(y));

        if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
            if (d == (int) d) {
                return true;
            } else {
                return false;
            }
        } else if (x > 0 && y < 0) {
            if ((int) d % 2 == 0) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        System.out.println(isPower(-32, -2));
        System.out.println(isPower(2, 8));
        System.out.println(isPower(8, 12));
        System.out.println(isPower(9, 9));
        System.out.println(isPower(-16, 2));
        System.out.println(isPower(-8, -2));
        System.out.println(isPower(16, -2));
        System.out.println(isPower(8, -2));
    }

}

This looks for the exponent in O(log N) steps:

#define MAX_POWERS 100

int is_power(unsigned long x, unsigned long y) {
  int i;
  unsigned long powers[MAX_POWERS];
  unsigned long last;
  last = powers[0] = y;

  for (i = 1; last < x; i++) {
    last *= last; // note that last * last can overflow here!
    powers[i] = last;
  }
  while (x >= y) {
    unsigned long top = powers[--i];
    if (x >= top) {
      unsigned long x1 = x / top;
      if (x1 * top != x) return 0;
      x = x1;
    }
  }
  return (x == 1);
}

Negative numbers are not handled by this code, but it can be done easyly with some conditional code when i = 1