## TIL: How to find if a number is power of 2

Take the number and take the number - 1, perform a binary and (`&`) operation on the two numbers. If the result is 0 then the number is the power of 2.

``````number != 0 && (number & (number - 1)) == 0
``````

Let's see some numbers which are power of 2 and their binary representation (padded with 0 for easer reading):

``````2  00010
4  00100
8  01000
16 10000

``````

Let's see the numbers - 1 and their binary representation (padded with 0 for easer reading):

``````1  00001
3  00011
7  00111
15 01111
``````

An `&` (and) operation will give 1 for a digit if both of digits are 1.

For example

``````4: 00100
3: 00011
--------
&: 00000
``````

Which will end up in 0, because a number which is the power of 2 only the first digit will be 1 and when we substitute 1 from the same number, we will get a number where all digits are 1 (except the first of the original number). So in the and we will &-ing 0 to 1 in every digit.

But on the other hand, if we substitute 1 from a non-power of 2, at least the first digit will always be 1 for both numbers, so &-ing them will always return a non 0 number:

``````3: 00011
2: 00010
--------
&: 00010
``````

Which is 2

``````6: 00110
5: 00101
--------
&: 00100
``````

Which is 4, so it's definetly not 0. So they are not power of 2.

Originally I found it in the Plan9 source code

Hozzászóláshoz a Disqus szolgáltatását használom, korábbi vélemények elovlasásához és új hozzászólás írásához engedélyezd a Disqus-tól származó JavaScripteteket.