DSA Bit Tricks

Bit tricks are short expressions that use bitwise rules to do a common job in one line. Each trick in this lesson is proven on real numbers.

Clear the lowest set bit

Subtracting 1 flips the lowest set bit and every bit below it. AND with the original number clears that bit.

for n in [12, 10, 7]:
    print(n, format(n, "06b"), "->", n & (n - 1), format(n & (n - 1), "06b"))

XOR cancels pairs

Each value that appears twice cancels itself under XOR. The value left standing appeared an odd number of times.

found = 0
for value in [4, 1, 2, 1, 2]:
    found = found ^ value
print("the unpaired value:", found)

One set bit means a power of two

A power of two clears to zero in a single clearing step. Zero itself is not a power of two.

for n in [0, 1, 2, 6, 8, 16]:
    print(n, "power of two:", n > 0 and (n & (n - 1)) == 0)

Example

numbers = [1, 3, 6, 8, 12, 16, 18]
print("n | binary | cleared | clears to zero | power of two")
for n in numbers:
    m = n
    clears = 0
    while m:
        m = m & (m - 1)
        clears += 1
    print(n, "|", format(n, "06b"), "|", n & (n - 1), "|", clears, "|", n > 0 and (n & (n - 1)) == 0)
found = 0
for value in [7, 3, 5, 3, 7, 9, 5]:
    found = found ^ value
print("unpaired value in the list:", found)

Key points

Bit tricks are short expressions that do a common job in one line.
The expression n AND (n minus 1) clears the lowest set bit of n.
A set bit is a bit that holds 1.
XOR of two equal values gives 0, so paired values cancel out.
A power of two has exactly one set bit.
Clearing set bits one by one counts them without scanning empty positions.

In this example, each number is cleared once and then cleared repeatedly. The cleared column shows the lowest set bit removed. The clears column counts the steps needed to reach zero. That count equals the number of set bits in the row. The last lines fold a list with XOR and print the one unpaired value.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

numbers = [1, 3, 6, 8, 12, 16, 18]
print("n | binary | cleared | clears to zero | power of two")
for n in numbers:
    m = n
    clears = 0
    while m:
        m = m & (m - 1)
        clears += 1
    print(n, "|", format(n, "06b"), "|", n & (n - 1), "|", clears, "|", n > 0 and (n & (n - 1)) == 0)
found = 0
for value in [7, 3, 5, 3, 7, 9, 5]:
    found = found ^ value
print("unpaired value in the list:", found)

Exercise

A list holds [6, 2, 6, 9, 2]. What does folding the whole list with XOR give?

0 9 6 15