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.

Code - Java

class Solution {
    /*
     * @param n: An integer
     * @return: True or false
     */
    public boolean checkPowerOf2(int n) {
        long p = (long) n;
        return n != 0 && (p & (p - 1)) == 0;
    }
};