Problem Description
Having an unsigned integer x (x > 0), return True if it is a power of 2, else return False. Example:
16 -> True (12 = 2 * 2 * 2 * 2)
12 -> False (12 = 2 * 2 * 3)
Traditional Algorithm : O(logn)
def is_power_of_two(x):
while x > 1:
if x % 2 != 0:
return False
x = x // 2
return True
Explanation: This code keeps dividing the number by 2 until it reaches 1 (for powers of 2) or finds an odd number (for non-powers of 2).
Prerequisites
Before getting to O(1) algorithm let's spend some time playing with bitwise operations
Bitwise AND
Bitwise AND (&) is a binary operation that compares each bit of two numbers: - It returns 1 for each bit position where both input bits are 1. - It returns 0 for all other cases.
Example (&):
1010 (10 in decimal)
1100 (12 in decimal)
1000 (8 in decimal)
Bitwise OR
Bitwise OR (|) is also a binary operation that compares each bit of two numbers: - It returns 1 for each bit position where at least one of the input bits is 1. - It returns 0 only when both input bits are 0.
Example (|):
1010 (10 in decimal)
1100 (12 in decimal)
1110 (14 in decimal)
Manipulating Rightmost Bits
Use the following formula to flip the rightmost 1-bit to 0 in a binary word, if the word does not contain ones, nothing will be changed: /predownloaded/72/60/7260331deafb1b25bbede890d89ce248fd31eb97.png Example:
00001111 -> 00001110
00000000 -> 00000000
00100000 -> 00000000
(If you still don't understand how the formula works, feel free to try one of the examples on your own)
Constant Algorithm : O(1)
Now after discovering the above wonderful formula, we can use it in our algorithm. Let's see how each number that is a power of two looks in binary :
1 -> 00000001
2 -> 00000010
4 -> 00000100
8 -> 00001000
16 -> 00010000
...
As you can notice, the power of two numbers have only a single 1-bit in their binary representation (of course that is not a coincidence, this is by the core of the binary system)
Therefore, removing this single 1-bit from those numbers will result in a 0.
Ultimately, when removing the rightmost 1-bit from a number, if it turns out to be a 0, then voila, it is a power of two, if not, then unfortunately ... it is not a power of two :(
def is_power_of_two(x):
return (x & (x - 1)) == 0
Final words
Thanks for reading this article.
This is one of many programming tricks from the book in the References section below.
References:
Hacker's Delight, 2nd ed., H. S. Warren, Jr., Addison-Wesley, 2013, ch. 2, sec. 2-1, p. 11.
