Bit Manipulation: Working With Individual Bits

Picture a hallway with eight light switches in a row. Each switch is up or down. Eight switches can show 256 different patterns, and you can flip one switch without touching the others. A number inside a computer is exactly such a row. This lesson shows how to read and flip single switches with a few short operators, and why that gives tiny, fast answers to puzzles that otherwise need loops and dictionaries.

Learning Objectives

After this lesson, you will be able to:

Convert between decimal and binary by place value, and work out the result of & | ^ ~ << >> from a hand-drawn column table
Explain how Python models negative numbers (~x equals -x - 1, with an endless row of leading ones), and mask a value to 8 or 32 bits with & 0xFF
Test, set, clear and toggle bit i, and explain why x & (x - 1) clears the lowest set bit and x & -x isolates it
Count set bits with a loop, with the x & (x - 1) loop and with int.bit_count, and compute parity
Use the XOR properties to find the single number, and say why the XOR swap is not worth using
Enumerate all subsets with a bitmask in O(n * 2^n), and explain the subset-sum and bitmask DP ideas
Use flags, Gray code and bit packing, link bits to int8 quantization and bitsets, and avoid the common precedence, shift and negative-number mistakes

Prerequisites

Before You Start

Review

#Bits and Binary: Place Value You Already Know

A bit is one switch with two states, written 0 and 1. A number written with bits is in binary. You already know the idea from ordinary numbers. In 305, the 3 means three hundreds, the 0 means no tens and the 5 means five ones. Each place is worth ten times the place to its right.

Binary is the same with two in place of ten. Each place is worth twice the place to its right: 1, 2, 4, 8, 16, and so on. The place on the far right is bit 0, the next is bit 1, and so on. We count bits from the right, starting at zero. Take 1101.

Bit	3	2	1	0
Worth	8	4	2	1
Digit	1	1	0	1

Add the worth of every place that holds a 1: 8 + 4 + 1 = 13. So 1101 in binary is 13. The cell below checks it by code. In Python, 0b starts a binary number, 0x starts a hexadecimal one (base 16, where one digit stands for four bits) and 0o starts an octal one (base 8).

pythonrunnable cell

print(bin(13), format(13, "08b"), int("1101", 2), 0b1101)
print(0xFF, 0o17)

total = 0
for position, digit in enumerate(reversed("1101")):
    total += int(digit) * 2 ** position
print(total)
# Output:
# 0b1101 00001101 13 13
# 255 15
# 13

bin(13) gives the text 0b1101. format(13, "08b") gives eight binary digits padded with zeros, which is the form we use to look at bits in this lesson. int("1101", 2) reads text as base 2. The loop is the place-value sum from the table. It walks the digits from the right and adds each digit times 2 to the power of its position.

Eight bits hold 2 to the power 8, which is 256 patterns, so the numbers 0 to 255. Each extra bit doubles the count. It is the halving game from the start of this part, run backwards.

#The Six Operators

Python has six bitwise operators. They work on every bit position of a number at the same time. First, the single-bit truth tables. A truth table lists the result for every possible input.

a	b	a & b (AND)	a \| b (OR)	a ^ b (XOR)
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

AND gives 1 only when both bits are 1. OR gives 1 when at least one is 1. XOR, short for exclusive or, gives 1 when the two bits differ. The cell prints the same table from code.

pythonrunnable cell

print("a b  &  |  ^")
for a in (0, 1):
    for b in (0, 1):
        print(a, b, "", a & b, a | b, a ^ b)
# Output:
# a b  &  |  ^
# 0 0  0 0 0
# 0 1  0 1 1
# 1 0  0 1 1
# 1 1  1 1 0

The other three operators are simpler. ~x flips every bit of x. x << k slides the bits of x left by k places and fills the right with zeros. x >> k slides them right by k places and drops the bits that fall off the end.

Now a hand trace, before any code. Take x = 12 and y = 10. Write both in four bits and work one column at a time.

	bit 3	bit 2	bit 1	value
x	1	1	0	12
y	1	0	1	10
x & y	1	0	0	8
x \| y	1	1	1	14
x ^ y	0	1	1	6

Look at bit 3: both are 1, so AND gives 1, OR gives 1 and XOR gives 0. Look at bit 2: only x has a 1, so AND gives 0, and OR and XOR give 1. That column method is the whole skill. For the shifts, 12 is 1100. Sliding left by 2 gives 110000, which is 48. Sliding right by 2 gives 0011, which is 3.

pythonrunnable cell

x, y = 12, 10
print(format(x, "04b"), format(y, "04b"))
print(format(x & y, "04b"), x & y)
print(format(x | y, "04b"), x | y)
print(format(x ^ y, "04b"), x ^ y)
print(format(x << 2, "06b"), x << 2, x * 4)
print(format(x >> 2, "04b"), x >> 2, x // 4)
# Output:
# 1100 1010
# 1000 8
# 1110 14
# 0110 6
# 110000 48 48
# 0011 3 3

The last two lines show a useful fact. Shifting left by k multiplies by 2^k. Shifting right by k divides by 2^k and rounds down. Each operator does a fixed amount of work per bit, so on a number of b bits it costs O(b) time. For a fixed width such as 32 bits, that is O(1).

#Python's Integers: No Overflow, and Negative Numbers

In many languages an integer has a fixed size, such as 32 bits. Add one to the biggest value and it wraps around to a negative one. That wrap is called overflow. Python integers have no fixed size. They grow as large as memory allows, so Python never overflows. This is a gift, but it changes how negative numbers behave with bit operators.

Before the explanation, predict.

What Do You Think?

What does ~5 give in Python? Remember that ~ flips every bit.

Here is how Python thinks. A positive number is its bits followed by endless zeros on the left: 5 is ...00000101. A negative number has endless ones on the left.

This scheme is called two's complement: the number -1 is all ones, forever, and the row of ones counts down from there. Flipping all the bits of x and adding x gives all ones, which is -1. So ~x + x == -1, and therefore ~x == -x - 1.

pythonrunnable cell

for v in (0, 5, -1, -6):
    print(v, ~v, -v - 1)

print(2 ** 100, (2 ** 100).bit_length())
print(bin(-5), (-5).bit_length())
# Output:
# 0 -1 -1
# 5 -6 -6
# -1 0 0
# -6 5 5
# 1267650600228229401496703205376 101
# -0b101 3

Python prints -5 as a minus sign and the bits of 5, but the operators use the endless-ones view underneath. To work with a fixed width, you mask. A mask is a number whose 1 bits mark the places you want to keep. & 0xFF keeps the lowest 8 bits and throws away the rest. That turns any integer into the 8-bit pattern a fixed-size language would hold.

pythonrunnable cell

print(-5 & 0xFF, format(-5 & 0xFF, "08b"))
print(200 & 0xFF, 300 & 0xFF, 256 & 0xFF)
print(-1 & 0xFFFFFFFF, hex(-1 & 0xFFFFFFFF))


def to_signed(u, bits):
    """Read the low `bits` bits of u as a signed number."""
    return u - (1 << bits) if u >> (bits - 1) else u


print(to_signed(0xFB, 8), to_signed(0x7F, 8), to_signed(0x80, 8))


def add32(a, b):
    """Add like a signed 32-bit machine integer that wraps on overflow."""
    return to_signed((a + b) & 0xFFFFFFFF, 32)


print(add32(2**31 - 1, 1), (2**31 - 1) + 1)
# Output:
# 251 11111011
# 200 44 0
# 4294967295 0xffffffff
# -5 127 -128
# -2147483648 2147483648

Read the first line: -5 masked to 8 bits is 11111011, which is 251. Reading it back, to_signed checks the top bit (the sign bit). If it is 1, the number is negative and we subtract 2^8. So 0xFB reads as -5. The add32 function shows what overflow means in a fixed-width language: 2147483647 plus 1 wraps to -2147483648. Python gives the true answer, 2147483648.

One more behavior to know. The right shift >> on a negative number keeps the sign. It fills the left with ones, so the number stays negative and rounds toward minus infinity. This is called an arithmetic shift. For example -7 >> 1 is -4, the same as -7 // 2.

#Test, Set, Clear and Toggle One Bit

Four jobs cover most of what you do with single bits. All four use a mask with one bit set, made by 1 << i. It is 1 followed by i zeros, so only bit i is on.

Test bit i: shift x right by i, then AND with 1. The answer is 0 or 1.
Set bit i (force it on): OR with the mask.
Clear bit i (force it off): AND with the flipped mask, ~(1 << i).
Toggle bit i (flip it): XOR with the mask.

The reasons come from the truth table. OR with 1 always gives 1, and OR with 0 changes nothing, so the mask turns on bit i and leaves the others. AND with 0 always gives 0, and AND with 1 changes nothing, so the flipped mask turns off bit i only. XOR with 1 flips a bit, and XOR with 0 changes nothing.

pythonrunnable cell

def test_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 toggle_bit(x, i):
    return x ^ (1 << i)


x = 0b101100
print(format(x, "06b"), test_bit(x, 2), test_bit(x, 0))
print(format(set_bit(x, 0), "06b"), format(clear_bit(x, 3), "06b"))
print(format(toggle_bit(x, 5), "06b"), format(toggle_bit(x, 1), "06b"))
# Output:
# 101100 1 0
# 101101 100100
# 001100 101110

Each function is O(1) for a fixed-width number, with O(1) extra space. The clear_bit function works on negative numbers too, because ~ gives an endless row of ones with one hole in it.

#Two Famous Tricks: x & (x - 1) and x & -x

Subtracting 1 from a binary number has a clean pattern. Take 101100. The lowest 1 turns into 0, and every 0 below it turns into 1. So 101100 minus 1 is 101011. Now predict what AND does to the pair.

What Do You Think?

Let x = 0b101100 (44). What is x & (x - 1) in binary?

Here is the reasoning. In x and x - 1, everything above the lowest 1 is identical, so AND keeps it. At the lowest 1 and below, the two numbers are opposites, so AND gives zeros there. The result is x with its lowest set bit removed.

For x & -x, remember that -x equals ~x + 1, which is the same as ~(x - 1). Flipping x - 1 makes everything above the lowest 1 opposite to x, and leaves the lowest 1 and the zeros below it equal to x. AND with x then keeps only the lowest set bit.

pythonrunnable cell

x = 0b101100
print(format(x - 1, "06b"), format(x & (x - 1), "06b"))
print(format(-x & 0xFF, "08b"), x & -x, format(x & -x, "06b"))


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


print([(v, is_power_of_two(v)) for v in (0, 1, 3, 4, 6, 64, 100, 1024)])
# Output:
# 101011 101000
# 11010100 4 000100
# [(0, False), (1, True), (3, False), (4, True), (6, False), (64, True), (100, False), (1024, True)]

A power of two has exactly one bit set, such as 1000. Removing that bit leaves 0, so n & (n - 1) == 0. The check n > 0 matters because 0 has no bits set and would pass the other test. Both tricks cost O(1) for a fixed width.

#Counting Set Bits and Parity

The popcount of a number is how many of its bits are 1. It is also called the Hamming weight. Here are three ways to compute it, from plain to clever.

The first checks the lowest bit, shifts right and repeats. It runs once per bit of the number, so O(b) time. The second uses the trick above: clear the lowest set bit and count how many times you can do it. It runs once per 1 bit, so O(k) time for k set bits, and it jumps over all the zeros. The third is the built-in int.bit_count(), added in Python 3.10, which does the work in C.

pythonrunnable cell

def popcount_loop(x):
    count = 0
    while x:
        count += x & 1
        x >>= 1
    return count


def popcount_kernighan(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count


for v in (0, 1, 7, 255, 1024, 2**64 - 1):
    print(v, popcount_loop(v), popcount_kernighan(v), v.bit_count())
print(all(popcount_loop(v) == v.bit_count() == popcount_kernighan(v) for v in range(5000)))
# Output:
# 0 0 0 0
# 1 1 1 1
# 7 3 3 3
# 255 8 8 8
# 1024 1 1 1
# 18446744073709551615 64 64 64
# True

All three use O(1) extra space. Both loops only work for non-negative numbers. A negative number has endless ones, so the shifting loop would never end. The loop on x & (x - 1) would run forever too. Take the absolute value, or mask first.

The parity of a number tells whether its popcount is odd or even. It is the XOR of all its bits. You can get it from the popcount with x.bit_count() & 1, or by flipping a flag once for every set bit.

pythonrunnable cell

def parity(x):
    p = 0
    while x:
        p ^= 1
        x &= x - 1
    return p


print([parity(v) for v in range(8)], [v.bit_count() & 1 for v in range(8)])
# Output:
# [0, 1, 1, 0, 1, 0, 0, 1] [0, 1, 1, 0, 1, 0, 0, 1]

#XOR: The Cancelling Operator

XOR has four properties that solve puzzles. First, a ^ a == 0: anything XORed with itself cancels. Second, a ^ 0 == a: zero changes nothing. Third, the order does not matter (commutative), and fourth, the grouping does not matter (associative). Together they say: in a long XOR, any value that appears twice vanishes, no matter where the copies sit.

Try it before reading the answer.

What Do You Think?

What is the value of 7 ^ 3 ^ 5 ^ 3 ^ 5 ^ 9 ^ 9?

That gives the classic single number problem. A list has every value twice except one. Find the one. The XOR of the whole list is the answer, in O(n) time and O(1) space. A dictionary would need O(n) space.

pythonrunnable cell

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result


print(single_number([4, 1, 2, 1, 2]), single_number([7, 3, 5, 3, 5, 9, 9]))
# Output:
# 4 7

XOR can also swap two variables without a third one. Starting from a and b: a ^= b stores the difference in a, b ^= a turns b into the old a, and a ^= b turns a into the old b. It is a famous trick.

Do not use it in Python, for three reasons. a, b = b, a is shorter and clear. The trick saves nothing here, because Python makes new integer objects anyway. And it breaks when both names point to the same place.

pythonrunnable cell

a, b = 5, 9
a ^= b
b ^= a
a ^= b
print(a, b)

values = [3, 4]
i = j = 0                      # the same slot twice
values[i] ^= values[j]
values[j] ^= values[i]
values[i] ^= values[j]
print(values)
# Output:
# 9 5
# [0, 4]

The second swap wiped out the 3. When i and j are the same, values[i] ^= values[j] is x ^ x, which is 0, and nothing can bring the value back.

#All Subsets with a Bitmask

A bitmask is a number used as a set of yes/no flags. Say you have n items. Give each item a bit position. A number from 0 to 2^n - 1 then picks a subset: bit i is 1 when item i is in. Counting from 0 up to 2^n - 1 visits every subset exactly once.

Hand trace for three items a, b and c. Mask 011 has bits 0 and 1 on, so it is the subset of a and b. Mask 100 is just c. The loop below prints all eight.

pythonrunnable cell

items = ["a", "b", "c"]
n = len(items)
for mask in range(1 << n):
    chosen = [items[i] for i in range(n) if (mask >> i) & 1]
    print(format(mask, "03b"), chosen)
# Output:
# 000 []
# 001 ['a']
# 010 ['b']
# 011 ['a', 'b']
# 100 ['c']
# 101 ['a', 'c']
# 110 ['b', 'c']
# 111 ['a', 'b', 'c']

There are 2^n masks, and decoding each takes O(n), so the time is O(n * 2^n). The extra space is O(n) for the one subset in hand. It matches the take-or-skip tree of backtracking, with no recursion. It is also easy to put in a loop or a comprehension. The method fits n up to about 20, since 2^20 is about a million masks.

A related loop visits every submask of a mask, meaning every subset of its on-bits: start at the mask and repeat sub = (sub - 1) & mask. Each subtraction steps down to the next smaller submask, and the AND throws away bits outside the mask. Running that for every mask of 4 bits makes exactly 3^4 = 81 steps, because each item is out of the mask, in the mask but not the submask, or in both.

#Subset Sum and the Bitmask DP Idea

Here is a neat use of one big integer as a row of flags.

The subset-sum question asks: which totals can you make by adding some of the numbers in a list? Keep a number reach whose bit s is 1 when sum s is possible. Sum 0 is always possible, so start with reach = 1. Adding a number v means every old sum s gives a new sum s + v, which is reach << v. Merge with OR.

pythonrunnable cell

def reachable(nums):
    reach = 1
    for v in nums:
        reach |= reach << v
    return reach


nums = [3, 34, 4, 12, 5, 2]
r = reachable(nums)
print([s for s in range(20) if (r >> s) & 1])
print((r >> 9) & 1, (r >> 30) & 1)

brute = {sum(nums[i] for i in range(len(nums)) if (m >> i) & 1) for m in range(1 << len(nums))}
print(brute == {s for s in range(sum(nums) + 1) if (r >> s) & 1})
# Output:
# [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19]
# 1 0
# True

Sum 9 is reachable (4 + 5) and sum 30 is not. The last line compares against the brute-force loop over all 64 subsets. With S the total of the list, one shift and OR touches S bits, so the time is O(n * S) bit operations. Python does many bits per machine step, so it is fast in practice. The space is O(S) bits. This is the dynamic programming table for subset sum, packed into one integer.

Bitmask DP goes further: the DP state includes a mask that records which items are used. The classic example is the travelling salesman problem (TSP), which asks for the shortest round trip through every city once. Checking every order costs (n - 1)! trips. A mask of visited cities plus the current city gives 2^n * n states, each with n choices, so O(2^n * n²) time and O(2^n * n) space.

pythonrunnable cell

from functools import lru_cache
from itertools import permutations

D = [[0, 10, 15, 20],
     [10, 0, 35, 25],
     [15, 35, 0, 30],
     [20, 25, 30, 0]]


def tsp(D):
    n = len(D)

    @lru_cache(maxsize=None)
    def best(mask, last):
        if mask == (1 << n) - 1:
            return D[last][0]                      # everyone visited: go home
        return min(D[last][nxt] + best(mask | (1 << nxt), nxt)
                   for nxt in range(n) if not (mask >> nxt) & 1)

    return best(1, 0)                              # start at city 0


def tsp_brute(D):
    n = len(D)
    costs = []
    for p in permutations(range(1, n)):
        route = (0,) + p + (0,)
        costs.append(sum(D[route[k]][route[k + 1]] for k in range(n)))
    return min(costs)


print(tsp(D), tsp_brute(D))
# Output:
# 80 80

Both give 80. The full treatment, with more state shapes, is in the Dynamic Programming Patterns, Part 2 lesson.

#Flags and Permissions

Many systems give each yes/no option its own bit. A flag is one such bit, and a number holding several is a flags field. Unix file permissions are the classic case: read is 4, write is 2 and execute is 1, and a mode like 0o755 holds three groups of those, for the owner, the group and everyone else.

pythonrunnable cell

READ, WRITE, EXEC = 4, 2, 1


def rwx(m):
    return "".join(ch if m & bit else "-" for ch, bit in (("r", 4), ("w", 2), ("x", 1)))


def mode_string(mode):
    return rwx(mode >> 6 & 7) + rwx(mode >> 3 & 7) + rwx(mode & 7)


print(mode_string(0o755), mode_string(0o644), format(0o755, "09b"))

p = READ | WRITE
print(p, bool(p & WRITE), bool(p & EXEC), p | EXEC, p & ~WRITE, p ^ READ)
# Output:
# rwxr-xr-x rw-r--r-- 111101101
# 6 True False 7 4 2

The last line shows the vocabulary: p | EXEC adds a flag, p & flag tests one, p & ~WRITE removes one and p ^ READ toggles one. Python's enum.IntFlag wraps this in names, so you can write Perm.W in q and still get the integer value.

pythonrunnable cell

from enum import IntFlag


class Perm(IntFlag):
    R = 4
    W = 2
    X = 1


q = Perm.R | Perm.W
print(q.value, Perm.W in q, Perm.X in q, (q | Perm.X).value, (q & ~Perm.W).value)
# Output:
# 6 True False 7 4

#Gray Code

Normal counting can change many bits at once: going from 3 (011) to 4 (100) flips all three. A Gray code is an ordering of the numbers where each step changes exactly one bit. The formula is n ^ (n >> 1). To undo it, XOR together the number and all its right shifts.

pythonrunnable cell

def gray(n):
    return n ^ (n >> 1)


def gray_inverse(g):
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n


for i in range(8):
    print(i, format(i, "03b"), format(gray(i), "03b"), gray_inverse(gray(i)))
print(all((gray(i) ^ gray(i + 1)).bit_count() == 1 for i in range(1000)))
# Output:
# 0 000 000 0
# 1 001 001 1
# 2 010 011 2
# 3 011 010 3
# 4 100 110 4
# 5 101 111 5
# 6 110 101 6
# 7 111 100 7
# True

Read the Gray column from top to bottom and only one digit changes each time. The last line checks that this holds for the first 1,001 codes: XOR of neighbours always has popcount 1. Each code costs O(1) for a fixed width, and the inverse costs O(b).

#Bit Packing

Packing means putting several small values into one integer. A colour has three channels from 0 to 255, each needing 8 bits, so together they fit in 24 bits. Shifts place each field, OR joins them, and shift plus mask takes them out again.

pythonrunnable cell

r, g, b = 255, 128, 7
colour = (r << 16) | (g << 8) | b
print(colour, hex(colour))
print((colour >> 16) & 0xFF, (colour >> 8) & 0xFF, colour & 0xFF)
# Output:
# 16744455 0xff8007
# 255 128 7

Always mask after you shift, as the code does. The shifted value carries every higher field with it, and & 0xFF cuts off all but the field you want. The same pattern, shift then mask, reads any field of any width.

#Bits in Machine Learning and Real Systems

Three places where these ideas show up. Each is a short sketch, and the code checks the claims.

#Int8 quantization

A trained model stores millions of weights.

A 32-bit float takes 4 bytes, and an 8-bit integer takes 1, so storing the weights as 8-bit integers needs a quarter of the space for the weights. To do it, pick a scale so the biggest weight maps to 127, divide, round and clip to the range -128 to 127. An 8-bit signed integer holds exactly 256 values, and its stored pattern is the two's complement you met above. The bigger the scale, the coarser the grid.

pythonrunnable cell

import struct

w = [0.42, -0.913, 0.077, 1.0, -0.31, 0.0, 0.55]
scale = max(abs(x) for x in w) / 127
q = [max(-128, min(127, round(x / scale))) for x in w]
back = [round(v * scale, 3) for v in q]
print(round(scale, 5), q)
print(back)
print(max(abs(a - v * scale) for a, v in zip(w, q)) <= scale / 2)
print([format(v & 0xFF, "08b") for v in q[:3]])
print(struct.calcsize("<f"), struct.calcsize("<b"))
# Output:
# 0.00787 [53, -116, 10, 127, -39, 0, 70]
# [0.417, -0.913, 0.079, 1.0, -0.307, 0.0, 0.551]
# True
# ['00110101', '10001100', '00001010']
# 4 1

The recovered weights are close but not exact, and the error is never more than half a step. The inference efficiency lesson in the Transformers track shows how one large outlier weight stretches the grid for everything else. The lab below shows both effects: each extra bit doubles the number of levels, and an outlier makes them coarse.

Quantization grid: more bits means more levelsInteractive

Change the number of bits and watch the grid of levels. Each bit doubles the levels, so 8 bits give 256. Then add one large outlier weight and see how the grid stretches and the error grows for all the other weights.

Loading visualization...

#Feature hashing

Suppose a model has an unknown number of text features, such as word=cat. The hashing trick turns each feature name into a number with a hash function, then keeps only the remainder after dividing by a fixed width. The model's input vector then has that fixed width, however many names appear.

Two names can land on the same slot, which is a collision. A sign bit taken from the hash lets collisions cancel on average, rather than always add. The library scikit-learn has this built in as FeatureHasher. In the code below we use zlib.crc32 because the built-in hash of a string changes on every run.

pythonrunnable cell

import zlib


def feature(name, n_features):
    h = zlib.crc32(name.encode())
    sign = 1 if h & 1 else -1               # one bit of the hash picks the sign
    return (h >> 1) % n_features, sign       # the other bits pick the slot


for name in ("word=cat", "word=dog", "city=Hyderabad", "len=5"):
    print(name, zlib.crc32(name.encode()), feature(name, 8))
# Output:
# word=cat 4149197933 (6, 1)
# word=dog 3896362680 (4, -1)
# city=Hyderabad 456704621 (6, 1)
# len=5 3892969687 (3, 1)

In this run word=cat and city=Hyderabad both land on slot 6 with width 8. That is a collision, and it is why the width is chosen large.

#Bitsets and Bloom filters

A bitset keeps a set of small whole numbers as one integer, with bit i on when i is in the set. Union is OR, intersection is AND, difference is a & ~b, and the size is the popcount.

A set of numbers below a billion would need a billion bits, which is 125,000,000 bytes, about 125 MB. A Bloom filter is a bitset plus a few hash functions, used to answer "have I seen this?" in small space. It gets its own lesson, Probabilistic Structures.

pythonrunnable cell

s = 0
for v in (1, 5, 9):
    s |= 1 << v
t = 0
for v in (5, 6, 9):
    t |= 1 << v


def members(m):
    return [i for i in range(m.bit_length()) if (m >> i) & 1]


print(members(s | t), members(s & t), members(s & ~t), (s | t).bit_count(), (s >> 5) & 1)
# Output:
# [1, 5, 6, 9] [5, 9] [1] 4 1

#Cost Summary

Here is every cost in the lesson in one place. Here b is the number of bits of the number, n is the number of items and k is the number of 1 bits.

Job	Time	Extra space	Why
`&`, `\|`, `^`, `~`, shifts	O(b), or O(1) at fixed width	O(b) for the new number	one step per bit
Test, set, clear, toggle bit i	O(1) at fixed width	O(1)	one mask, one operator
Popcount by shifting	O(b)	O(1)	one look per bit
Popcount with `x & (x - 1)`	O(k)	O(1)	one step per 1 bit
`int.bit_count()`	O(b), done in C	O(1)	same count, faster loop
Single number by XOR	O(n)	O(1)	pairs cancel
All subsets by bitmask	O(n * 2^n)	O(n)	2^n masks, n bits to decode
Subset sum as one integer	O(n * S) bit operations	O(S) bits	one shift and OR per number
Bitmask DP for TSP	O(2^n * n²)	O(2^n * n)	states times choices

#When Not to Use Bit Tricks

Bit tricks make code short, but not always clear. In everyday Python, x % 2 == 0 reads better than x & 1 == 0, and x // 2 reads better than x >> 1. Use the bit version when it states the idea (a mask, a flag, a power of two) or when you need the speed of a dense bitset.

A plain set of numbers is better when the numbers are sparse and large, because a bitset pays for every position up to the biggest value. Bit tricks also only work on integers. 1.5 & 1 is an error.

#Common Mistakes

Before the first mistake, predict what a right shift does to a negative number.

What Do You Think?

What does -9 >> 1 give in Python?

Watch Out

Forgetting that + binds tighter than the shift operators

Fix: Add brackets whenever you mix shifts with + or -. Write (1 << n) + 1 or 1 << (n + 1) so the reader sees which one you mean.

pythonrunnable cell

n = 3
print(1 << n + 1)
print((1 << n) + 1)
# Output:
# 16
# 9

Python gives + and - a higher priority than << and >>. So 1 << n + 1 means 1 << (n + 1), which is 16.

The order, from tightest to loosest, is ~, then * and //, then + and -, then the shifts, then &, then ^, then |, then comparisons such as ==.

A happy detail: comparisons are looser than &, so x & 1 == 0 does mean (x & 1) == 0 in Python. In C, Java and JavaScript it does not, which is why code from those languages is full of brackets. Keep the brackets anyway.

Watch Out

Using ^ as the power operator

Fix: Use ** for powers. The caret ^ is XOR in Python.

pythonrunnable cell

print(2 ^ 3)
print(2 ** 3)
# Output:
# 1
# 8

In mathematics a small caret means power, and in some tools it does too. In Python it is XOR: 2 is 10, 3 is 11, and the bits that differ give 01, which is 1. The code runs without an error and gives a wrong answer, so the bug is easy to miss.

Watch Out

Expecting fixed-width behavior from Python integers

Fix: Mask the result to the width you want. Use & 0xFFFFFFFF for 32 bits and then to_signed if you need a negative result.

pythonrunnable cell

print(~5, ~5 & 0xFF)
print(1 << 40)
try:
    print(1 << -1)
except ValueError as e:
    print("ValueError:", e)
# Output:
# -6 250
# 1099511627776
# ValueError: negative shift count

In C a 32-bit ~5 is a large positive number once the value is read as unsigned, and 1 << 40 overflows. In Python ~5 is -6 and 1 << 40 is a normal number. If your answer must match a fixed-width system, mask it. Also remember that a negative shift count is an error in Python and not a shift in the other direction.

#Try It: The Five-Problem Ladder

Five problems from easy to hard. Fill in each TODO and run. The expected output is in the tests note. Stuck for fifteen minutes on a rung? Open the solution, read only that function, close it and rewrite it.

Hamming distance: the number of bit positions where two numbers differ, using XOR and popcount.
The missing number: a list holds 0 to n except one value. XOR finds it with O(1) space.
Two singles: every value appears twice except two. XOR plus x & -x pulls them apart.
Find the bugs: three small helpers, each with one bug from this lesson.
Faster all-pairs Hamming distance: replace the O(n²) double loop with a count per bit.

pythonplayground.py · Pyodide

# Five problems, easy to hard. Fill in each TODO, then run.

# 1. Hamming distance: how many bit positions differ between a and b?
def hamming(a, b):
  # TODO: XOR marks the differing bits; count them with bit_count()
  pass

# 2. The list holds every number from 0 to n except one (n = len(nums)). Return the missing one.
#    Use XOR only: no sum, no set. Hint: XOR all the indexes 0..n together with all the values.
def missing_number(nums):
  # TODO
  pass

# 3. Every value appears twice except two different values. Return those two, sorted.
#    Hint: the XOR of the whole list is a ^ b. A set bit of a ^ b is a place where a and b differ.
#    Use x & -x to pick one such bit, then split the list into numbers with and without it.
def two_singles(nums):
  # TODO
  pass

# 4. Find the bugs. Each helper has one bug from the lesson.
def is_power_of_two(n):
  return n & (n - 1) == 0

def clear_bit(x, i):
  return x & (1 << i)

def set_bits_below(x, k):
  """Turn on bits 0..k-1 of x."""
  return x | (1 << k)

# 5. Total of hamming(a, b) over all pairs a before b in nums. Values are below 2**32.
#    The version below is O(n^2). Rewrite it to count, for each of the 32 bit positions,
#    how many numbers have that bit on (ones). That bit contributes ones * (n - ones). It is O(32 * n).
def total_hamming(nums):
  total = 0
  for i in range(len(nums)):
      for j in range(i + 1, len(nums)):
          total += (nums[i] ^ nums[j]).bit_count()
  return total

print(hamming(93, 73), hamming(0, 255), hamming(7, 7))
print(missing_number([3, 0, 1]), missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]), missing_number([0, 1]))
print(two_singles([1, 2, 1, 3, 2, 5]), two_singles([4, 9, 4, 7, 9, 12, 12, 30]))
print([is_power_of_two(v) for v in (0, 1, 6, 64)], clear_bit(0b1111, 2), format(set_bits_below(0b100000, 3), "06b"))
print(total_hamming([4, 14, 2, 4294967295, 12345, 0, 77]), total_hamming([4, 14, 2]))

Tests · Correct output, line by line: 2 8 0; 2 8 2; [3, 5] [7, 30]; [False, True, False, True] 11 100111; 236 6.

Costs for the ladder, with reasons. Problem 1 is O(1) at fixed width, since XOR and popcount do one step per bit. Problem 2 is O(n) time and O(1) space, one XOR per list item. Problem 3 is O(n) time and O(1) space, two passes. Problem 5 is O(32 * n), which is O(n), where the slow version is O(n²), and both use O(1) extra space.

#Recap

A bit is a switch, and a number is a row of them with place values 1, 2, 4, 8 and so on. The operators AND, OR and XOR work on every column at once, ~ flips, and the shifts multiply or divide by powers of two. Python integers never overflow, and negatives behave as if they had endless leading ones, so ~x equals -x - 1. Mask with & 0xFF or & 0xFFFFFFFF to get fixed-width answers.

Test, set, clear and toggle one bit with a single-bit mask and shift, AND, OR or XOR. The expression x & (x - 1) removes the lowest set bit, which gives the power-of-two test and a fast popcount. The expression x & -x keeps only the lowest set bit. XOR cancels pairs, which solves the single-number puzzle.

A bitmask lists all subsets in O(n * 2^n), packs a subset-sum table into one integer and carries state in bitmask DP. Flags, Gray code, packing, int8 weights, feature hashing and bitsets are the same toolkit at work.

Quick Check1 / 12

What is 0b1100 ^ 0b1010 written in binary?

Recap

Key Takeaways

A number is a row of bits with place values 1, 2, 4, 8 and so on, and the operators & | ^ work on every column at once
Python integers never overflow, and ~x equals -x - 1; mask with & 0xFF or & 0xFFFFFFFF to see a fixed-width result
Test, set, clear and toggle bit i with a one-bit mask (1 << i) and shift, OR, AND with the flipped mask, and XOR
x & (x - 1) clears the lowest set bit, x & -x isolates it, and n > 0 and n & (n - 1) == 0 tests for a power of two
XOR cancels equal pairs, so the XOR of a list finds the single number in O(n) time and O(1) space
A bitmask lists all subsets in O(n * 2^n), and one big integer can hold a whole subset-sum table
Mind precedence (+ before shifts), remember ^ is XOR and not a power, and expect >> on negatives to round down

Bit Manipulation: Working With Individual Bits

Learning Objectives

After this lesson, you will be able to:

Convert between decimal and binary by place value, and work out the result of & | ^ ~ << >> from a hand-drawn column table
Explain how Python models negative numbers (~x equals -x - 1, with an endless row of leading ones), and mask a value to 8 or 32 bits with & 0xFF
Test, set, clear and toggle bit i, and explain why x & (x - 1) clears the lowest set bit and x & -x isolates it
Count set bits with a loop, with the x & (x - 1) loop and with int.bit_count, and compute parity
Use the XOR properties to find the single number, and say why the XOR swap is not worth using
Enumerate all subsets with a bitmask in O(n * 2^n), and explain the subset-sum and bitmask DP ideas
Use flags, Gray code and bit packing, link bits to int8 quantization and bitsets, and avoid the common precedence, shift and negative-number mistakes

Prerequisites

Before You Start

Review

#Bits and Binary: Place Value You Already Know

Bit	3	2	1	0
Worth	8	4	2	1
Digit	1	1	0	1

pythonrunnable cell

print(bin(13), format(13, "08b"), int("1101", 2), 0b1101)
print(0xFF, 0o17)

total = 0
for position, digit in enumerate(reversed("1101")):
    total += int(digit) * 2 ** position
print(total)
# Output:
# 0b1101 00001101 13 13
# 255 15
# 13

Eight bits hold 2 to the power 8, which is 256 patterns, so the numbers 0 to 255. Each extra bit doubles the count. It is the halving game from the start of this part, run backwards.

#The Six Operators

Python has six bitwise operators. They work on every bit position of a number at the same time. First, the single-bit truth tables. A truth table lists the result for every possible input.

a	b	a & b (AND)	a \| b (OR)	a ^ b (XOR)
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

AND gives 1 only when both bits are 1. OR gives 1 when at least one is 1. XOR, short for exclusive or, gives 1 when the two bits differ. The cell prints the same table from code.

pythonrunnable cell

print("a b  &  |  ^")
for a in (0, 1):
    for b in (0, 1):
        print(a, b, "", a & b, a | b, a ^ b)
# Output:
# a b  &  |  ^
# 0 0  0 0 0
# 0 1  0 1 1
# 1 0  0 1 1
# 1 1  1 1 0

Now a hand trace, before any code. Take x = 12 and y = 10. Write both in four bits and work one column at a time.

	bit 3	bit 2	bit 1	value
x	1	1	0	12
y	1	0	1	10
x & y	1	0	0	8
x \| y	1	1	1	14
x ^ y	0	1	1	6

pythonrunnable cell

x, y = 12, 10
print(format(x, "04b"), format(y, "04b"))
print(format(x & y, "04b"), x & y)
print(format(x | y, "04b"), x | y)
print(format(x ^ y, "04b"), x ^ y)
print(format(x << 2, "06b"), x << 2, x * 4)
print(format(x >> 2, "04b"), x >> 2, x // 4)
# Output:
# 1100 1010
# 1000 8
# 1110 14
# 0110 6
# 110000 48 48
# 0011 3 3

#Python's Integers: No Overflow, and Negative Numbers

Before the explanation, predict.

What Do You Think?

What does ~5 give in Python? Remember that ~ flips every bit.

Here is how Python thinks. A positive number is its bits followed by endless zeros on the left: 5 is ...00000101. A negative number has endless ones on the left.

pythonrunnable cell

for v in (0, 5, -1, -6):
    print(v, ~v, -v - 1)

print(2 ** 100, (2 ** 100).bit_length())
print(bin(-5), (-5).bit_length())
# Output:
# 0 -1 -1
# 5 -6 -6
# -1 0 0
# -6 5 5
# 1267650600228229401496703205376 101
# -0b101 3

pythonrunnable cell

print(-5 & 0xFF, format(-5 & 0xFF, "08b"))
print(200 & 0xFF, 300 & 0xFF, 256 & 0xFF)
print(-1 & 0xFFFFFFFF, hex(-1 & 0xFFFFFFFF))


def to_signed(u, bits):
    """Read the low `bits` bits of u as a signed number."""
    return u - (1 << bits) if u >> (bits - 1) else u


print(to_signed(0xFB, 8), to_signed(0x7F, 8), to_signed(0x80, 8))


def add32(a, b):
    """Add like a signed 32-bit machine integer that wraps on overflow."""
    return to_signed((a + b) & 0xFFFFFFFF, 32)


print(add32(2**31 - 1, 1), (2**31 - 1) + 1)
# Output:
# 251 11111011
# 200 44 0
# 4294967295 0xffffffff
# -5 127 -128
# -2147483648 2147483648

#Test, Set, Clear and Toggle One Bit

Four jobs cover most of what you do with single bits. All four use a mask with one bit set, made by 1 << i. It is 1 followed by i zeros, so only bit i is on.

Test bit i: shift x right by i, then AND with 1. The answer is 0 or 1.
Set bit i (force it on): OR with the mask.
Clear bit i (force it off): AND with the flipped mask, ~(1 << i).
Toggle bit i (flip it): XOR with the mask.

pythonrunnable cell

def test_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 toggle_bit(x, i):
    return x ^ (1 << i)


x = 0b101100
print(format(x, "06b"), test_bit(x, 2), test_bit(x, 0))
print(format(set_bit(x, 0), "06b"), format(clear_bit(x, 3), "06b"))
print(format(toggle_bit(x, 5), "06b"), format(toggle_bit(x, 1), "06b"))
# Output:
# 101100 1 0
# 101101 100100
# 001100 101110

Each function is O(1) for a fixed-width number, with O(1) extra space. The clear_bit function works on negative numbers too, because ~ gives an endless row of ones with one hole in it.

#Two Famous Tricks: x & (x - 1) and x & -x

Subtracting 1 from a binary number has a clean pattern. Take 101100. The lowest 1 turns into 0, and every 0 below it turns into 1. So 101100 minus 1 is 101011. Now predict what AND does to the pair.

What Do You Think?

Let x = 0b101100 (44). What is x & (x - 1) in binary?

pythonrunnable cell

x = 0b101100
print(format(x - 1, "06b"), format(x & (x - 1), "06b"))
print(format(-x & 0xFF, "08b"), x & -x, format(x & -x, "06b"))


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


print([(v, is_power_of_two(v)) for v in (0, 1, 3, 4, 6, 64, 100, 1024)])
# Output:
# 101011 101000
# 11010100 4 000100
# [(0, False), (1, True), (3, False), (4, True), (6, False), (64, True), (100, False), (1024, True)]

#Counting Set Bits and Parity

The popcount of a number is how many of its bits are 1. It is also called the Hamming weight. Here are three ways to compute it, from plain to clever.

pythonrunnable cell

def popcount_loop(x):
    count = 0
    while x:
        count += x & 1
        x >>= 1
    return count


def popcount_kernighan(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count


for v in (0, 1, 7, 255, 1024, 2**64 - 1):
    print(v, popcount_loop(v), popcount_kernighan(v), v.bit_count())
print(all(popcount_loop(v) == v.bit_count() == popcount_kernighan(v) for v in range(5000)))
# Output:
# 0 0 0 0
# 1 1 1 1
# 7 3 3 3
# 255 8 8 8
# 1024 1 1 1
# 18446744073709551615 64 64 64
# True

pythonrunnable cell

def parity(x):
    p = 0
    while x:
        p ^= 1
        x &= x - 1
    return p


print([parity(v) for v in range(8)], [v.bit_count() & 1 for v in range(8)])
# Output:
# [0, 1, 1, 0, 1, 0, 0, 1] [0, 1, 1, 0, 1, 0, 0, 1]

#XOR: The Cancelling Operator

Try it before reading the answer.

What Do You Think?

What is the value of 7 ^ 3 ^ 5 ^ 3 ^ 5 ^ 9 ^ 9?

pythonrunnable cell

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result


print(single_number([4, 1, 2, 1, 2]), single_number([7, 3, 5, 3, 5, 9, 9]))
# Output:
# 4 7

pythonrunnable cell

a, b = 5, 9
a ^= b
b ^= a
a ^= b
print(a, b)

values = [3, 4]
i = j = 0                      # the same slot twice
values[i] ^= values[j]
values[j] ^= values[i]
values[i] ^= values[j]
print(values)
# Output:
# 9 5
# [0, 4]

The second swap wiped out the 3. When i and j are the same, values[i] ^= values[j] is x ^ x, which is 0, and nothing can bring the value back.

#All Subsets with a Bitmask

Hand trace for three items a, b and c. Mask 011 has bits 0 and 1 on, so it is the subset of a and b. Mask 100 is just c. The loop below prints all eight.

pythonrunnable cell

items = ["a", "b", "c"]
n = len(items)
for mask in range(1 << n):
    chosen = [items[i] for i in range(n) if (mask >> i) & 1]
    print(format(mask, "03b"), chosen)
# Output:
# 000 []
# 001 ['a']
# 010 ['b']
# 011 ['a', 'b']
# 100 ['c']
# 101 ['a', 'c']
# 110 ['b', 'c']
# 111 ['a', 'b', 'c']

#Subset Sum and the Bitmask DP Idea

Here is a neat use of one big integer as a row of flags.

pythonrunnable cell

def reachable(nums):
    reach = 1
    for v in nums:
        reach |= reach << v
    return reach


nums = [3, 34, 4, 12, 5, 2]
r = reachable(nums)
print([s for s in range(20) if (r >> s) & 1])
print((r >> 9) & 1, (r >> 30) & 1)

brute = {sum(nums[i] for i in range(len(nums)) if (m >> i) & 1) for m in range(1 << len(nums))}
print(brute == {s for s in range(sum(nums) + 1) if (r >> s) & 1})
# Output:
# [0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19]
# 1 0
# True

pythonrunnable cell

from functools import lru_cache
from itertools import permutations

D = [[0, 10, 15, 20],
     [10, 0, 35, 25],
     [15, 35, 0, 30],
     [20, 25, 30, 0]]


def tsp(D):
    n = len(D)

    @lru_cache(maxsize=None)
    def best(mask, last):
        if mask == (1 << n) - 1:
            return D[last][0]                      # everyone visited: go home
        return min(D[last][nxt] + best(mask | (1 << nxt), nxt)
                   for nxt in range(n) if not (mask >> nxt) & 1)

    return best(1, 0)                              # start at city 0


def tsp_brute(D):
    n = len(D)
    costs = []
    for p in permutations(range(1, n)):
        route = (0,) + p + (0,)
        costs.append(sum(D[route[k]][route[k + 1]] for k in range(n)))
    return min(costs)


print(tsp(D), tsp_brute(D))
# Output:
# 80 80

Both give 80. The full treatment, with more state shapes, is in the Dynamic Programming Patterns, Part 2 lesson.

#Flags and Permissions

pythonrunnable cell

READ, WRITE, EXEC = 4, 2, 1


def rwx(m):
    return "".join(ch if m & bit else "-" for ch, bit in (("r", 4), ("w", 2), ("x", 1)))


def mode_string(mode):
    return rwx(mode >> 6 & 7) + rwx(mode >> 3 & 7) + rwx(mode & 7)


print(mode_string(0o755), mode_string(0o644), format(0o755, "09b"))

p = READ | WRITE
print(p, bool(p & WRITE), bool(p & EXEC), p | EXEC, p & ~WRITE, p ^ READ)
# Output:
# rwxr-xr-x rw-r--r-- 111101101
# 6 True False 7 4 2

pythonrunnable cell

from enum import IntFlag


class Perm(IntFlag):
    R = 4
    W = 2
    X = 1


q = Perm.R | Perm.W
print(q.value, Perm.W in q, Perm.X in q, (q | Perm.X).value, (q & ~Perm.W).value)
# Output:
# 6 True False 7 4

#Gray Code

pythonrunnable cell

def gray(n):
    return n ^ (n >> 1)


def gray_inverse(g):
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n


for i in range(8):
    print(i, format(i, "03b"), format(gray(i), "03b"), gray_inverse(gray(i)))
print(all((gray(i) ^ gray(i + 1)).bit_count() == 1 for i in range(1000)))
# Output:
# 0 000 000 0
# 1 001 001 1
# 2 010 011 2
# 3 011 010 3
# 4 100 110 4
# 5 101 111 5
# 6 110 101 6
# 7 111 100 7
# True

#Bit Packing

pythonrunnable cell

r, g, b = 255, 128, 7
colour = (r << 16) | (g << 8) | b
print(colour, hex(colour))
print((colour >> 16) & 0xFF, (colour >> 8) & 0xFF, colour & 0xFF)
# Output:
# 16744455 0xff8007
# 255 128 7

#Bits in Machine Learning and Real Systems

Three places where these ideas show up. Each is a short sketch, and the code checks the claims.

#Int8 quantization

A trained model stores millions of weights.

pythonrunnable cell

import struct

w = [0.42, -0.913, 0.077, 1.0, -0.31, 0.0, 0.55]
scale = max(abs(x) for x in w) / 127
q = [max(-128, min(127, round(x / scale))) for x in w]
back = [round(v * scale, 3) for v in q]
print(round(scale, 5), q)
print(back)
print(max(abs(a - v * scale) for a, v in zip(w, q)) <= scale / 2)
print([format(v & 0xFF, "08b") for v in q[:3]])
print(struct.calcsize("<f"), struct.calcsize("<b"))
# Output:
# 0.00787 [53, -116, 10, 127, -39, 0, 70]
# [0.417, -0.913, 0.079, 1.0, -0.307, 0.0, 0.551]
# True
# ['00110101', '10001100', '00001010']
# 4 1

Quantization grid: more bits means more levelsInteractive

Loading visualization...

#Feature hashing

pythonrunnable cell

import zlib


def feature(name, n_features):
    h = zlib.crc32(name.encode())
    sign = 1 if h & 1 else -1               # one bit of the hash picks the sign
    return (h >> 1) % n_features, sign       # the other bits pick the slot


for name in ("word=cat", "word=dog", "city=Hyderabad", "len=5"):
    print(name, zlib.crc32(name.encode()), feature(name, 8))
# Output:
# word=cat 4149197933 (6, 1)
# word=dog 3896362680 (4, -1)
# city=Hyderabad 456704621 (6, 1)
# len=5 3892969687 (3, 1)

In this run word=cat and city=Hyderabad both land on slot 6 with width 8. That is a collision, and it is why the width is chosen large.

#Bitsets and Bloom filters

A bitset keeps a set of small whole numbers as one integer, with bit i on when i is in the set. Union is OR, intersection is AND, difference is a & ~b, and the size is the popcount.

pythonrunnable cell

s = 0
for v in (1, 5, 9):
    s |= 1 << v
t = 0
for v in (5, 6, 9):
    t |= 1 << v


def members(m):
    return [i for i in range(m.bit_length()) if (m >> i) & 1]


print(members(s | t), members(s & t), members(s & ~t), (s | t).bit_count(), (s >> 5) & 1)
# Output:
# [1, 5, 6, 9] [5, 9] [1] 4 1

#Cost Summary

Here is every cost in the lesson in one place. Here b is the number of bits of the number, n is the number of items and k is the number of 1 bits.

Job	Time	Extra space	Why
`&`, `\|`, `^`, `~`, shifts	O(b), or O(1) at fixed width	O(b) for the new number	one step per bit
Test, set, clear, toggle bit i	O(1) at fixed width	O(1)	one mask, one operator
Popcount by shifting	O(b)	O(1)	one look per bit
Popcount with `x & (x - 1)`	O(k)	O(1)	one step per 1 bit
`int.bit_count()`	O(b), done in C	O(1)	same count, faster loop
Single number by XOR	O(n)	O(1)	pairs cancel
All subsets by bitmask	O(n * 2^n)	O(n)	2^n masks, n bits to decode
Subset sum as one integer	O(n * S) bit operations	O(S) bits	one shift and OR per number
Bitmask DP for TSP	O(2^n * n²)	O(2^n * n)	states times choices

#When Not to Use Bit Tricks

#Common Mistakes

Before the first mistake, predict what a right shift does to a negative number.

What Do You Think?

What does -9 >> 1 give in Python?

Watch Out

Forgetting that + binds tighter than the shift operators

Fix: Add brackets whenever you mix shifts with + or -. Write (1 << n) + 1 or 1 << (n + 1) so the reader sees which one you mean.

pythonrunnable cell

n = 3
print(1 << n + 1)
print((1 << n) + 1)
# Output:
# 16
# 9

Python gives + and - a higher priority than << and >>. So 1 << n + 1 means 1 << (n + 1), which is 16.

The order, from tightest to loosest, is ~, then * and //, then + and -, then the shifts, then &, then ^, then |, then comparisons such as ==.

Watch Out

Using ^ as the power operator

Fix: Use ** for powers. The caret ^ is XOR in Python.

pythonrunnable cell

print(2 ^ 3)
print(2 ** 3)
# Output:
# 1
# 8

Watch Out

Expecting fixed-width behavior from Python integers

Fix: Mask the result to the width you want. Use & 0xFFFFFFFF for 32 bits and then to_signed if you need a negative result.

pythonrunnable cell

print(~5, ~5 & 0xFF)
print(1 << 40)
try:
    print(1 << -1)
except ValueError as e:
    print("ValueError:", e)
# Output:
# -6 250
# 1099511627776
# ValueError: negative shift count

#Try It: The Five-Problem Ladder

Hamming distance: the number of bit positions where two numbers differ, using XOR and popcount.
The missing number: a list holds 0 to n except one value. XOR finds it with O(1) space.
Two singles: every value appears twice except two. XOR plus x & -x pulls them apart.
Find the bugs: three small helpers, each with one bug from this lesson.
Faster all-pairs Hamming distance: replace the O(n²) double loop with a count per bit.

pythonplayground.py · Pyodide

# Five problems, easy to hard. Fill in each TODO, then run.

# 1. Hamming distance: how many bit positions differ between a and b?
def hamming(a, b):
  # TODO: XOR marks the differing bits; count them with bit_count()
  pass

# 4. Find the bugs. Each helper has one bug from the lesson.
def is_power_of_two(n):
  return n & (n - 1) == 0

def clear_bit(x, i):
  return x & (1 << i)

def set_bits_below(x, k):
  """Turn on bits 0..k-1 of x."""
  return x | (1 << k)

Tests · Correct output, line by line: 2 8 0; 2 8 2; [3, 5] [7, 30]; [False, True, False, True] 11 100111; 236 6.

#Recap

Quick Check1 / 12

What is 0b1100 ^ 0b1010 written in binary?

Recap

Key Takeaways

A number is a row of bits with place values 1, 2, 4, 8 and so on, and the operators & | ^ work on every column at once
Python integers never overflow, and ~x equals -x - 1; mask with & 0xFF or & 0xFFFFFFFF to see a fixed-width result
Test, set, clear and toggle bit i with a one-bit mask (1 << i) and shift, OR, AND with the flipped mask, and XOR
x & (x - 1) clears the lowest set bit, x & -x isolates it, and n > 0 and n & (n - 1) == 0 tests for a power of two
XOR cancels equal pairs, so the XOR of a list finds the single number in O(n) time and O(1) space
A bitmask lists all subsets in O(n * 2^n), and one big integer can hold a whole subset-sum table
Mind precedence (+ before shifts), remember ^ is XOR and not a power, and expect >> on negatives to round down

Bit Manipulation: Working With Individual Bits

#Bits and Binary: Place Value You Already Know

#The Six Operators

#Python's Integers: No Overflow, and Negative Numbers

#Test, Set, Clear and Toggle One Bit

#Two Famous Tricks: x & (x - 1) and x & -x

#Counting Set Bits and Parity

#XOR: The Cancelling Operator

#All Subsets with a Bitmask

#Subset Sum and the Bitmask DP Idea

#Flags and Permissions

#Gray Code

#Bit Packing

#Bits in Machine Learning and Real Systems

#Int8 quantization

#Feature hashing

#Bitsets and Bloom filters

#Cost Summary

#When Not to Use Bit Tricks

#Common Mistakes

#Try It: The Five-Problem Ladder

#Recap

Your Reflection

Continue Learning

Discussion

Bit Manipulation: Working With Individual Bits

#Bits and Binary: Place Value You Already Know

#The Six Operators

#Python's Integers: No Overflow, and Negative Numbers

#Test, Set, Clear and Toggle One Bit

#Two Famous Tricks: x & (x - 1) and x & -x

#Counting Set Bits and Parity

#XOR: The Cancelling Operator

#All Subsets with a Bitmask

#Subset Sum and the Bitmask DP Idea

#Flags and Permissions

#Gray Code

#Bit Packing

#Bits in Machine Learning and Real Systems

#Int8 quantization

#Feature hashing

#Bitsets and Bloom filters

#Cost Summary

#When Not to Use Bit Tricks

#Common Mistakes

#Try It: The Five-Problem Ladder

#Recap

Your Reflection

Continue Learning

Discussion