some algorithmic puzzles, tutorials, interview questions... and stuff...

Sunday, September 06, 2009

How to check if a number is a power of 2 (Google phone screening)

This is actually one of the questions I was asked in my Google first phone screening, and it's really easy, because there's a trick for that: given a number N, you can check if it's a power of two if N & (N-1) == 0.

   1:  int n = 1024;
   2:  cout << n << " is " 
   3:      << ((n & (n-1)) ? "NOT " : "" )
   4:      << "power of 2" << endl;
You could also do the iterative version, where you repeatedly check the first byte (N & 1), then shift to the right (N >> 1), and again, for all 32 bits (assuming it's a 32bit integer). If the total number of bits with value 1 is just one, it means it's a power of two. I gave this as an alternative to the trick above and everything was fine.

No comments:

Post a Comment