h1

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

October 21, 2009

My 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: