bool powOfTwo(int num)
{
return !(num & (num - 1));
}
What on earth is this function doing?
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:
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?
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]
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]
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.
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:
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.
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.
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement