How does this Python code check if a number is a power of 2?
n>0 is pretty straightforward, but what does (n & (n - 1)) == 0 do?
def is_Power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
Asked
Active
Viewed 1,199 times
-3
SecretAgentMan
- 2,856
- 7
- 21
- 41
Jimmy Coltrane
- 45
- 6
-
3https://stackoverflow.com/questions/4678333/n-n-1-what-does-this-expression-do – Ollie Feb 25 '21 at 19:57
-
In the future: if something is a duplicate, please actually vote to close as such. – Karl Knechtel Feb 25 '21 at 20:19
-
@KarlKnechtel Sorry about that, I wasn't *entirely* sure (like 94%). I'll vote to close next time. – Ollie Feb 26 '21 at 22:03
2 Answers
0
Post that provides good explanation:
Below is checking if an integer is odd/even and returning a boolean value
(n & (n - 1)) == 0
If n = 2, then
(n & (n - 1)) == 0
>>> True
If n = 7, then
(n & (n - 1)) == 0
>>> False
The function is_Power_of_two(n) checks if n is greater than 0 AND if n is even. If both conditions are met, the function will return true.
nahar
- 41
- 5
0
For integral types '&' computes the logical bitwise AND of its operands. So lets take n=4.
(4 & (4 - 1)) = 4&3
In binary
100 = 4
011 = 3
And
100 & 011= 000
The reason this works is because in binary subtracting 1 from any number that is a power of two is just the same number with all of the bits reversed. When you binary AND (&) these two together you always get a 0.
To elaborate with examples - any number that is power of two is in binary written as a 1 with following 0s. 1,2,4,8,16,... is in binary 1, 10, 100, 1000 and subtracting 1 just gives you a number one smaller than that - 0, 01, 011, 0111 etc.
Nac
- 1
- 3