Sign in to follow this  
Chrono1081

What on earth is this function doing?

Recommended Posts

Hi guys. I'm reading a book and even though its a simple example, this example stuck out at me. I have no clue what its doing. I'm sure its something stupid I'm missing but I just don't get whats going on here in this function:
bool powOfTwo(int num)
{
     return !(num & (num - 1));
}



Ok you put in an integer but I don't understand the whole ! infront of the return statement (and why on earth its returning what it is returning. I'm sure I'm missing something stupid here but I've never seen anything written like this. Can someone please explain what is going on here?

Share this post


Link to post
Share on other sites
A number that is a power of 2 (in binary) takes the form:

2 = 10
4 = 100
8 = 1000
16 = 10000
32 = 100000
etc.

So, if num is a power of 2, num-1 will always be of the binary form:
2-1 = 1
4-1 = 11
8-1 = 111
etc.

And, for powers of 2, num & (num-1) always = 0. E.g., 10 & 1, 1000 & 111.

!(num & (num-1)) asks the question "Is (num & (num-1))==0?" which will be true for powers of 2.

Actually, the "question" is "Invert the answer to Is (num & (num-1))!=0?"

For all other numbers (num & (num-1)) will have some bit set and
Is (num & (num-1))==0? is always false.

EDIT: changed the question from is(...)==1 to is(...)!=0.

[Edited by - Buckeye on February 21, 2010 9:15:07 AM]

Share this post


Link to post
Share on other sites
Are you familiar with the bitwise operations?

In binary, a number that is a power of two will only have one bit set. Let us take 8 as an example, in binary 8 is 1000. Subtracting 1 from that yields 7, or 0111. The bitwise-and operator will only fill in bits in the result with a 1 when the two operand bits at the same position are 1.

1000
& 0111
------
= 0000

The logical-not operator is quite simple, it returns "true" if the value is 0, and "false" otherwise (in C like languages anyway). Here the value passed to logical-not is 0, so it evalutes "true". 8 is a power of two, after all, and our function verifies this.

It should be easy to see that for any value where only one bit is set, this test will true, as all that really changes is the location of the one in the value.

Let us examine a non power of two, 6. The binary representation us 0110. Subtracting one from that is 5, or 0101. Let us bitwise-and these together:

0110
& 0101
------
= 0100

This value is non-zero, so the logical-not operator will evaluate it as false, which is then returned from the function.

It should be relatively easy to convince yourself that for any binary value with two or more bits set, that subtracting one from it will yield a value with only the lower bits changed. The upper bits will not be affected. There will always be at least one common bit between N and N - 1 when n is not a power of two, bitwise-and will set that bit in the result and logical-not will return false because the value it is passed is not 0.

A similar observation in decimal is to note that subtracting one from any value that isn't a power of 10 won't affect the upper digits.

Share this post


Link to post
Share on other sites
Thanks guys for the responses :D

I'm going on 6 hours of sleep total in 6 days so I'm borderline delerious. I'll re-read everything that was posted in the morning after a long night of sleep.

I've been playing in Objective-C for a year and a half and just now hopping back into C++. I forgot all about bitwise operators because I never use them and most books gloss over them. There is a description, but they never provide a use for them.

I thought the & was some weirdly placed reference operator.

Anyway thank you guys for the responses and I'll be sure to read everything tomorrow more in depth. Now I'm off to bed :D

Share this post


Link to post
Share on other sites
Thank you guys for the detailed explanations :) They make perfect sense now.

Now I've gotta start brushing up on my C++ since I'm finished with a lot of my math and physics classes and now back to programming :D

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this