O(1) Check Power of 2

Problem

Using O(1) time to check whether an integer n is a power of 2.

Example

• For n=4, return true;
• For n=5, return false;

Solution

O(1) time means there's a way to check this in constant time, regardless of how big the number is. If an integer n is power of 2, then its binary format is a leading 1 with multiple 0s, for example, 4 => 100, 8 => 1000, 16 => 10000.

Then n-1's binary is all 1s: 3 => 11, 7 => 111, 15 => 1111.

And n & (n - 1) is always 0: 100 & 11 = 0, 1000 & 111 = 0

So we can use this trait to test if n is a power of 2 in a constant time.