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

Explication: 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. ❤️ Leave a like if you enjoyed it! ❤️

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.