# [c#] How to check if a number is a power of 2

Some sites that document and explain this and other bit twiddling hacks are:

- http://graphics.stanford.edu/~seander/bithacks.html

(http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2) - http://bits.stephan-brumme.com/

(http://bits.stephan-brumme.com/isPowerOfTwo.html)

And the grandaddy of them, the book "Hacker's Delight" by Henry Warren, Jr.:

As Sean Anderson's page explains, the expression `((x & (x - 1)) == 0)`

incorrectly indicates that 0 is a power of 2. He suggests to use:

```
(!(x & (x - 1)) && x)
```

to correct that problem.

Today I needed a simple algorithm for checking if a number is a power of 2.

The algorithm needs to be:

- Simple
- Correct for any
`ulong`

value.

I came up with this simple 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 thought, how about checking if `log`

is an exactly round number? But when I checked for 2^63+1, _{2} x`Math.Log`

returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in `double`

s and not in exact numbers:

```
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
```

This returned `true`

for the given wrong value: `9223372036854775809`

.

Is there a better algorithm?

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

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 a 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's a simple C++ solution:

```
bool IsPowerOfTwo( unsigned int i )
{
return std::bitset<32>(i).count() == 1;
}
```

```
bool isPowerOfTwo(int x_)
{
register int bitpos, bitpos2;
asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
return bitpos > 0 && bitpos == bitpos2;
}
```

Here is another method I devised, in this case using `|`

instead of `&`

:

```
bool is_power_of_2(ulong x) {
if(x == (1 << (sizeof(ulong)*8 -1) ) return true;
return (x > 0) && (x<<1 == (x|(x-1)) +1));
}
```

**Example**

```
0000 0001 Yes
0001 0001 No
```

**Algorithm**

Using a bit mask, divide

`NUM`

the variable in binary`IF R > 0 AND L > 0: Return FALSE`

Otherwise,

`NUM`

becomes the one that is non-zero`IF NUM = 1: Return TRUE`

Otherwise, go to Step 1

**Complexity**

Time ~ `O(log(d))`

where `d`

is number of binary digits

After posting the question I thought of the following solution:

We need to check if exactly one of the binary digits is one. So we simply shift the number right one digit at a time, and return `true`

if it equals 1. If at any point we come by an odd number (`(number & 1) == 1`

), we know the result is `false`

. This proved (using a benchmark) slightly faster than the original method for (large) true values and much faster for false or small values.

```
private static bool IsPowerOfTwo(ulong number)
{
while (number != 0)
{
if (number == 1)
return true;
if ((number & 1) == 1)
// number is an odd number and not 1 - so it's not a power of two.
return false;
number = number >> 1;
}
return false;
}
```

Of course, Greg's solution is much better.

I wrote an article about this recently at http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/. It covers bit counting, how to use logarithms correctly, the classic "x && !(x & (x - 1))" check, and others.

The following addendum to the accepted answer may be useful for some people:

A power of two, when expressed in binary, will always look like *1 followed by n zeroes* where n is greater 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 kind of numbers, they become *0 followed by n ones* and again n is same as above. 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.

Coming to the crux

What happens when we do a bitwise AND of a number

`x`

, which is a power of 2, and`x - 1`

?

*The one of x gets aligned with the zero of x - 1 and all the zeroes of x get aligned with ones of x - 1, causing the bitwise AND to result in 0.* And that is how we have the single line answer mentioned above being right.

## Further adding to the beauty of accepted answer above -

So, we have a property at our disposal now:

When we subtract 1 from any number, then in the binary representation the rightmost 1 will become 0 and all the zeroes before that rightmost 1 will now become 1

One awesome use of this property is in finding out - **How many 1s are present in the binary representation of a given number?** The short and sweet code to do that for a given integer `x`

is:

```
byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);
```

Another aspect of numbers that can be proved from the concept explained above is **"Can every positive number be represented as the sum of powers of 2?"**.

Yes, every positive number can be represented as the sum of powers of 2. For any number, take its binary representation. Ex: Take number `501`

.

```
The binary of 501 is 111110101
Because 111110101 = 100000000 + 10000000 + 1000000 + 100000 + 1000 + 000 + 100 + 00 + 1
we have 501 = 256 + 128 + 64 + 32 + 16 + 0 + 4 + 0 + 1
```

This program in java returns "true" if number is a power of 2 and returns "false" if its not a power of 2

```
// To check if the given number is power of 2
import java.util.Scanner;
public class PowerOfTwo {
int n;
void solve() {
while(true) {
// To eleminate the odd numbers
if((n%2)!= 0){
System.out.println("false");
break;
}
// Tracing the number back till 2
n = n/2;
// 2/2 gives one so condition should be 1
if(n == 1) {
System.out.println("true");
break;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
PowerOfTwo obj = new PowerOfTwo();
obj.n = in.nextInt();
obj.solve();
}
}
OUTPUT :
34
false
16
true
```