Bit Operation #2

Let's think about simple examples again.

Input: 4 bits integer x (e.g., 1010)

int f(unsigned int x)
{
    return !(x & (x-1));
}

We know that (x & (x-1)) operation erases the rightmost 1 bit in x. Now, consider an integer that is a power of two has exactly one bit that is '1'. Hence, if x contains only one bit that is '1', (x & (x-1)) will be zero (0000). After applying 'logical not' operation (!), a value of 0 becomes 1 and a value other than 0 becomes 0.

Therefore, this function returns whether an integer is a power of two. Consider one case where the input x is zero (0000). Then, this function returns 1 saying x is a power of two although zero is not a power of two. Hence, we have to modify this function as below.

int f(unsigned int x)
{
    return x && !(x & (x-1));
    // same to (x != 0) && !(x & (x-1));
}