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.

❤️ Leave a like if you enjoyed it! ❤️