#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/power-of-two

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/power-of-two

Repovive

Power of Two - Bit Manipulation | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Power of Two

Check if n is a power of 2.

A power of two has exactly one bit set: $1, 2, 4, 8, 16, ...$

Method: n & (n - 1) clears the lowest set bit. If the result is $0$ , there was only one bit.

function isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

Example:

$n = 8 = 1000_2$ . $n - 1 = 0111_2$ . $1000 \& 0111 = 0000$ . True.
$n = 6 = 0110_2$ . $n - 1 = 0101_2$ . $0110 \& 0101 = 0100 \neq 0$ . False.

Note: Check $n > 0$ because $0$ is not a power of two but $0 \& (-1) = 0$ .

Time: $O(1)$ .