Power of Two: The n & (n - 1) Trick, Explained Properly

Problem: given an integer n, return true if it is a power of two. 1, 16 and 1024 are; 0, 6 and -8 are not.

The loop answer

Keep dividing by 2 while the number is even, then check you landed on 1. It is O(log n) and nobody will fail you for it, but it invites the follow-up "can you do it in O(1)?"

def is_power_of_two(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

The bit trick, and why it works

A power of two has exactly one set bit: 1000 in binary. Subtracting 1 flips that bit off and turns every lower bit on: 0111. ANDing the two gives zero. Any number with two or more set bits keeps its highest bit after the AND, so the result is non-zero.

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 0

The n > 0 guard matters: 0 & -1 is 0, so without it zero would pass. Say this edge case before the interviewer does.

Follow-ups worth preparing

How to present it

Lead with the loop in one sentence, then offer the bit trick and explain the binary picture. Interviewers care more about the explanation than the one-liner.


Disclosure: I work on Linkjob AI. If you want help staying calm in live coding rounds, take a look at Linkjob AI's coding interview copilot.