Bit Masks Explained: Set, Clear, Toggle and the Power-of-Two Test

Bit manipulation questions look like a bag of unrelated tricks: set a bit, count bits, check a power of two, find the lowest set bit. They are one idea used five ways. A mask is a number whose 1s mark the positions you care about, and nearly every trick is "build the right mask, then combine it with AND, OR or XOR".

The problem it solves

An integer is a row of on/off switches. Storing flags in one integer instead of separate booleans is compact — a user's settings, a set of permissions, the visited cities in a travelling-salesman search — and every check or update is a single machine instruction.

The catch is that you cannot touch one switch directly. There is no "set the third bit" instruction in most languages; there is only arithmetic on the whole number. Masks are how you aim that arithmetic at one position without disturbing the rest.

The intuition

Start with 1, which has exactly one bit on, in position 0. Shift it left i places and you have 1 << i: a single 1 in position i. That is your key to lane i. Then:

• Read lane i: shift x right by i and AND with 1. Everything except that lane is discarded.
• Set lane i: x | (1 << i). OR with 0 changes nothing; OR with 1 forces a 1.
• Clear lane i: x & ~(1 << i). The inverted mask is 1 everywhere except lane i, so AND keeps every other bit and drops only that one.
• Flip lane i: x ^ (1 << i). XOR with 1 inverts; XOR with 0 leaves alone.

The power-of-two test uses a different mask: n - 1. Subtracting 1 turns the lowest set bit of n into 0 and every bit below it into 1. The bits above it do not change. So n & (n - 1) is n with its lowest set bit removed. A power of two has exactly one set bit, so removing it leaves 0. Anything with two or more set bits leaves something behind.

Watch it run

The animation works on 11, which is 0b1011. It builds the mask 1 << 2, ANDs it to read that lane (off), ORs it to switch the lane on (11 becomes 15), clears lane 0 with an inverted mask, and flips lane 3 with XOR (11 drops to 3). Then it switches questions: 16 AND 15 is 0, so 16 is a power of two; 12 AND 11 leaves 8, so 12 is not.

The code

The four single-bit operations, the power-of-two test, and two relatives: n & -n isolates the lowest set bit, and bit_length gives the next power of two:

def get_bit(x, i):   return (x >> i) & 1
def set_bit(x, i):   return x | (1 << i)
def clear_bit(x, i): return x & ~(1 << i)
def flip_bit(x, i):  return x ^ (1 << i)

x = 0b1011                                     # 11
print(get_bit(x, 2), bin(set_bit(x, 2)), bin(clear_bit(x, 0)), bin(flip_bit(x, 3)))
# 0 0b1111 0b1010 0b11

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 0           # exactly one bit set

def lowest_set_bit(n):
    return n & -n                               # isolates the rightmost 1

def next_power_of_two(n):                       # smallest power of two >= n, for n >= 1
    return 1 << (n - 1).bit_length()

print([n for n in range(-2, 20) if is_power_of_two(n)])   # [1, 2, 4, 8, 16]
print(bin(44), bin(lowest_set_bit(44)), bin(44 & (44 - 1)))  # 0b101100 0b100 0b101000
print(next_power_of_two(1), next_power_of_two(17), next_power_of_two(64))  # 1 32 64

n & -n works because in two's complement, -n is ~n + 1: inverting flips every bit, and adding 1 carries up to exactly the position of the lowest set bit of n. That position is the only one where n and -n both have a 1.

Flags stored in one integer, the way the lesson's feature-flag example describes:

FLAGS = {"dark_mode": 0, "beta_search": 1, "email_digest": 2}
user = 0
user = set_bit(user, FLAGS["dark_mode"])
user = set_bit(user, FLAGS["email_digest"])
print(bin(user), [f for f, i in FLAGS.items() if get_bit(user, i)])
# 0b101 ['dark_mode', 'email_digest']

Every operation is checked against a slow reference that does the same job on a list of '0' and '1' characters, with no bitwise operators at all — 5,000 random numbers up to 2²⁰ and random positions:

import random

def bits(n, width):                              # brute force: a list of '0'/'1' lanes
    return list(format(n, "0%db" % width))[::-1] # lane i at index i

def unbits(lanes):
    return int("".join(reversed(lanes)), 2)

random.seed(4)
ok = True
for _ in range(5000):
    n = random.randint(0, 2 ** 20)
    i = random.randint(0, 20)
    lanes = bits(n, 21)
    ok &= get_bit(n, i) == int(lanes[i])
    for op, new in ((set_bit, "1"), (clear_bit, "0"),
                    (flip_bit, "1" if lanes[i] == "0" else "0")):
        want = lanes[:]
        want[i] = new
        ok &= op(n, i) == unbits(want)
    ok &= is_power_of_two(n) == (bin(n).count("1") == 1)
    if n:
        ok &= lowest_set_bit(n) == 2 ** lanes.index("1")
        ok &= next_power_of_two(n) == min(2 ** p for p in range(22) if 2 ** p >= n)
print(ok)                                       # True

The complexity

Each operation is O(1): one shift and one logical instruction on a machine word. That is the entire appeal. A set of up to 64 flags fits in one 64-bit word; union is OR, intersection is AND, membership is one AND — no loop, no allocation. Python's integers grow without limit, so the operations stay correct for any size, but they are only constant-time while the number fits in a machine word.

Where it goes wrong

• Forgetting n > 0. 0 & -1 is 0, so zero passes the bare n & (n - 1) == 0 test. In Python, negative numbers behave as if they had infinitely many leading 1s, and none of them pass, but the guard is still needed for zero.
• Operator precedence in C and Java. In both, == binds tighter than &, so n & (n - 1) == 0 means n & ((n - 1) == 0). In C that compiles and gives the wrong answer; in Java it does not compile. Write (n & (n - 1)) == 0. Python happens to parse it the intended way, because comparisons bind looser than &.
• Shifting into the sign bit. In Java, 1 << 31 on an int is negative; in C, shifting a 1 into the sign bit of a signed int is undefined behaviour. Use an unsigned or 64-bit type when you need the top bit.
• Inverting in a fixed width. ~mask in C on a 32-bit type sets all the upper bits too. That is exactly what clearing needs, but printing it, or comparing it to a small constant, surprises people.

How to say it in an interview

"I build a mask with 1 << i. OR sets that bit, AND with the inverted mask clears it, XOR toggles it, and shifting right then ANDing 1 reads it. For a power of two I use n & (n - 1): subtracting one clears the lowest set bit and sets everything below it, so the AND removes the lowest set bit. A power of two has only one, so the result is zero — and I guard n > 0, because zero would pass otherwise. All of it is O(1)."

Once masks are comfortable, a bitmask as a set uses them to enumerate subsets, and XOR tricks covers the other operator that shows up in interviews.