## Find if a number is a power of two: Part 2

October 21, 2009My 1GB USB has 0 bytes left so Linux cannot boot from it; I have to reinstall Linux from the Live CD again… yaaay… </sarcasm> Anyways, so I looked up the solution to how to find using only bitwise operators, if a number is a power of two. This site led me to another site with 10 different ways to check if an integer is a power of two; the one I need is a slight modification of the 9th way:

`int isPowerOfTwo (unsigned int x) {`

return ((x != 0) && !(x & (x - 1)));

}

I couldn’t use exactly this, because of only being allowed these operators: & | ^ ! + >> << ~. So…here (I’ve broken the parts into separate variables so it doesn’t break onto multiple lines for one line of code, and also so I can use a few less parentheses to make sure the operations happen in the right order):

`int isPowerOfTwo (int x) {`

int a = !( (x>>31) & 1 );

int b = !(!x);

int c = !( x & ( x + ((((((FF<<8)+FF)<<8)+FF)<<8)+FF) ) );

return ( a & b & c );

}

a will return 0 if x is less than 0.

b will return 0 if x is 0. (Using ! twice makes 0 return 0 and anything else return 1.)

c’s explanation I just pasted from the website…since it sums it up nicely.

*Note: ( x + ((((((FF<<8)+FF)<<8)+FF)<<8)+FF) ) is using two’s complement to subtract one from x since we couldn’t use -.

!(x & (x-1)) is true when x is a power of two and false when x is not. Let’s see why.

Let n be the position of the leftmost 1 bit if x. If x is a power of two, its lone 1 bit is in position n. This means x – 1 has a 0 in position n. To see why, recall how binary subtraction works. When subtracting 1 from x, the borrow propagates all the way to position n; bit n becomes 0 and all lower bits become 1. Now, since x has no 1 bits in common with x – 1, x & (x – 1) is 0, and !(x & (x – 1)) is true.

Here are some examples (I’ll use 8-bit unsigned integers to keep things manageable):

Decrement and Compare, when x is a power of two:

x / x – 1 / x & (x – 1)

00000001 00000000 00000000

00000100 00000011 00000000

00010000 00001111 00000000

If x is not a power of two, x – 1 has a 1 in position n. This is because the borrow will not propagate to position n. Subtraction borrows from the lowest 1 bit, which by virtue of x not being a power of two, is before position n. The lowest 1 bit is like a firewall that prevents the borrow from reaching position n. Since x and x – 1 have at least one 1 bit in common — at position n — x & (x – 1) is non-zero, and !(x & (x – 1)) is false.

Here are some examples:

Decrement and Compare, when x is a NOT power of two:

x / x – 1 / x & (x – 1)

00000011 00000010 00000010

00000110 00000101 00000100

00001011 00001010 00001010

00011100 00011011 00011000

## Leave a Reply