Using a Faster Approach to Judge if a Integer is power of Two

Given a signed-integer, we can use the following straightforward method to judge it is the power of two

1
2
3
4
5
6
7
8
9

inline
bool check1(int i) {
    if (i < 1) return false;
    if (i <= 2) return true;     
    for (int n = 4; ;n *= 2) {         
        if (n == i) return true;         
        if (n > i) return false;
    }
}

inline
bool check1(int i) {
    if (i < 1) return false;
    if (i <= 2) return true;     
    for (int n = 4; ;n *= 2) {         
        if (n == i) return true;         
        if (n > i) return false;
    }
}

For non-positive integers, the answer is clearly false, input 1 and 2 are true since and . For the rest, multiply variable each time by two and return false if the current value becomes bigger than input or otherwise return true if it is equal to the input. The complexity if .

A faster approach (a cheat one) would be to use the log2 function provided in the math.h header. The log2 function takes float parameter (single or double precision) and return the log2 value in the form of single or double. To check if the fraction is smaller enough to conclude if it is power of two.

1
2
3
4
5
6

inline
bool check2(int i) {
    if (i < 1) return false;
    double n = log2(i);
    return (n - (int)n) <= 1e-9;
}

inline
bool check2(int i) {
    if (i < 1) return false;
    double n = log2(i);
    return (n - (int)n) <= 1e-9;
}

The performance depends heavily on the implementation of log2. Surprisingly, on GNU C++ compiler (RELEASE, windows), this version takes roughly the same time as the first approach. However, this approach is considered .

The fastest solution would be to use binary logics. A integer in binary if it is power of two, is written with a single 1 followed by zeros on the right. Therefore, we can check n & (n – 1) == 0. For example, 8 in binary is 01000, 01000 & 00111 == 0 so 8 is the power of two. The exceptional case is when input is 0, so add this check at first.

1
2
3
4
5

inline
bool check3(int i) {
    if (i < 1) return false;
    return (i & (i - 1)) == 0;
}

inline
bool check3(int i) {
    if (i < 1) return false;
    return (i & (i - 1)) == 0;
}

This approach is also . It is around 178 times faster than the above two approaches.

References:

[1] http://helloacm.com/check-integer-is-the-power-of-two/

–EOF (Coding For Speed) —