Problem
I wanted a quick method to see if an integer is a power of two today.
The algorithm should be as follows:
I devised the following basic algorithm:
private bool IsPowerOfTwo(ulong number)
{
if (number == 0)
return false;
for (ulong power = 1; power > 0; power = power << 1)
{
// This for loop used shifting for powers of 2, meaning
// that the value will become 0 after the last shift
// (from binary 1000...0000 to 0000...0000) then, the 'for'
// loop will break out.
if (power == number)
return true;
if (power > number)
return false;
}
return false;
}
But then I had an idea: why not see if log2 x is a perfectly round number? When I looked up 263+1 in Math. Because to rounding, Log() returned exactly 63. So I checked to see if 2 to the power 63 is the same as the original value, which it is because the calculation is done in doubles rather than exact integers.
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
For the given incorrect value of 9223372036854775809, this returned true.
Is there a more efficient algorithm?
Asked by configurator
Solution #1
This difficulty can be solved using a simple trick:
bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
This method will return true for a value of 0 that is not a power of 2. Here’s how to make sure that doesn’t happen:
bool IsPowerOfTwo(ulong x)
{
return (x != 0) && ((x & (x - 1)) == 0);
}
First and foremost, the MSDN definition of the bitwise binary & operator:
Let’s take a look at how things are going to play out:
The function returns boolean (true/false) and takes one unsigned long parameter as input (x, in this case). Assume for the purpose of simplicity that the value 4 was passed and the function was called as follows:
bool b = IsPowerOfTwo(4)
Now we replace each occurrence of x with 4:
return (4 != 0) && ((4 & (4-1)) == 0);
So far, so good. We already know that 4!= 0 evals to true. But how about this:
((4 & (4-1)) == 0)
Of course, this translates to:
((4 & 3) == 0)
But, exactly, what is 4&3?
es these numbers’ binary form). As a result, we have:
100 = 4
011 = 3
Consider stacking these values in the same way you would in elementary school. The & operator states that if both values are 1, the outcome will be 1, otherwise it will be 0. So 1 & 1 equals 1, 1 & 0 equals 0, 0 & 0 equals 0, and 0 & 1 equals 0. So here’s how we do the math:
100
011
----
000
The outcome is a simple 0. So let’s have a look at what our new return statement looks like:
return (4 != 0) && ((4 & 3) == 0);
Which currently translates to:
return true && (0 == 0);
return true && true;
We all know that true && true is simply true, and this demonstrates that 4 is a power of 2 in our example.
Answered by Greg Hewgill
Solution #2
This and other bit twiddling hacks are documented and explained on the following websites:
And the granddaddy of them all, Henry Warren, Jr.’s book “Hacker’s Delight”:
According to Anderson’s page, the equation ((x & (x – 1)) == 0) demonstrates that 0 is not a power of 2. He recommends that you use:
(!(x & (x - 1)) && x)
to rectify the situation
Answered by Michael Burr
Solution #3
== return I & -i)
Answered by Andreas Petersson
Solution #4
bool IsPowerOfTwo(ulong x)
{
return x > 0 && (x & (x - 1)) == 0;
}
Answered by Matt Howells
Solution #5
For some persons, the following addendum to the acceptable answer may be useful:
When stated in binary, a power of two will always appear as 1 followed by n zeroes, where n is larger than or equal to 0. Ex:
Decimal Binary
1 1 (1 followed by 0 zero)
2 10 (1 followed by 1 zero)
4 100 (1 followed by 2 zeroes)
8 1000 (1 followed by 3 zeroes)
. .
. .
. .
and so on.
When we subtract 1 from these numbers, we get 0 and then n ones, with n being the same as before. Ex:
Decimal Binary
1 - 1 = 0 0 (0 followed by 0 one)
2 - 1 = 1 01 (0 followed by 1 one)
4 - 1 = 3 011 (0 followed by 2 ones)
8 - 1 = 7 0111 (0 followed by 3 ones)
. .
. .
. .
and so on.
We’ve arrived at the crux of the matter.
The bitwise AND results in 0 because the one of x is aligned with the zero of x – 1 and all of x’s zeroes are aligned with the ones of x – 1. As a result, the single-line response provided earlier is correct.
As a result, we now have a property at our disposal:
This feature can be used to determine how many 1s are contained in the binary representation of a given number. For a given integer x, the short and sweet code to accomplish such is:
byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);
“Can every positive number be represented as the sum of powers of 2?” is another element of numbers that can be shown using the above notion.
Yes, the sum of powers of two can be used to represent any positive number. Take the binary representation of any number. Take, for example, number 117.
The binary representation of 117 is 1110101
Because 1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have 117 = 64 + 32 + 16 + 0 + 4 + 0 + 1
Answered by displayName
Post is based on https://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2