Unit 3: Bits

Every number is already binary underneath

A computer stores 13 as switches: 1101. The places are worth 8, 4, 2 and 1, and 8 + 4 + 1 is 13.

Python will show you, and the 0b in front just means "this is binary".

Python

for n in [1, 2, 5, 13, 255]:
    print(n, bin(n))

It prints

1 0b1
2 0b10
5 0b101
13 0b1101
255 0b11111111

Reading one switch

Shifting right by i slides bit number i down to the bottom, and & 1 keeps only the bottom one. So (x >> i) & 1 is bit i, and it is the most-used line in this unit.

Bit 0 is the ones place, bit 1 the twos, bit 2 the fours.

Python

x = 13
for i in range(4):
    print(i, (x >> i) & 1)

It prints

0 1
1 0
2 1
3 1

And building one back up

Going the other way, each new bit doubles what you had and adds itself. Same idea as reading a decimal number left to right, with 2 instead of 10.

Python

bits = [1, 1, 0, 1]

value = 0
for b in bits:
    value = value * 2 + b
print(value)

It prints

13

Four operators that work on every switch at once

& keeps a bit only when both numbers have it. | keeps it when either does. ^ — xor — keeps it when exactly one does.

One machine instruction, sixty-four switches, no loop.

Python

a = 12
b = 10
print(bin(a), bin(b))
print(a & b, a | b, a ^ b)

It prints

0b1100 0b1010
8 14 6

Shifting is multiplying and dividing by two

x << 1 slides every bit up one place, which doubles it. x >> 2 slides down two places, which quarters it and throws the leftovers away — exactly like //.

1 << n is the fastest way to write two to the power of n, and you will see it everywhere from here on.

Python

x = 5
print(x << 1, x << 3, 40 >> 2, 41 >> 2)
print(1 << 10, 2 ** 10)

It prints

10 40 10 10
1024 1024

Two tricks worth memorising

x & (x - 1) switches off the lowest bit that is on. Do it until nothing is left and you have counted the ones.

x & -x gives you that lowest bit on its own, as a number.

Python

x = 44
print(bin(x))
print(bin(x & (x - 1)))
print(x & -x)

count = 0
while x > 0:
    x &= x - 1
    count += 1
print(count)

It prints

0b101100
0b101000
4
3

Xor is its own undo

Xor a number with the same thing twice and you are back where you started, because every switch got flipped and flipped again.

And x ^ 0 is x. Hold on to both — the boss lesson is built entirely out of them.

Python

print(7 ^ 7, 7 ^ 0, (3 ^ 5) ^ 5)

It prints

0 7 3

Bit i means "item i is in the group"

Three animals, so three bits. The number 5 is 101, so the group is the ant and the cat.

A whole subset, stored as one small number. This is called a bitmask.

Python

items = ["ant", "bee", "cat"]
mask = 5

chosen = []
for i in range(3):
    if (mask >> i) & 1:
        chosen.append(items[i])

print(mask, bin(mask), chosen)

It prints

5 0b101 ['ant', 'cat']

So every subset is just a number to count up to

Unit 2 walked the subsets with recursion. With masks it is a plain for loop from 0 to 2 ** n — and the numbers come out in a fixed, easy-to-reason-about order.

1 << n is 2 ** n, and it is what everybody writes.

Python

items = [1, 2, 3]

for mask in range(1 << len(items)):
    chosen = [items[i] for i in range(len(items)) if (mask >> i) & 1]
    print(mask, chosen)

It prints

0 []
1 [1]
2 [2]
3 [1, 2]
4 [3]
5 [1, 3]
6 [2, 3]
7 [1, 2, 3]

The set operations come free

Union is |. Intersection is &. "In a but not in b" is a & ~b. Adding item i is mask | (1 << i), and asking whether it is in is mask & (1 << i).

Every one of those is a single instruction, which is why a bitmask beats a real set in a contest.

Python

a = 0b1011
b = 0b0110
print(bin(a | b), bin(a & b), bin(a & ~b))
print(bin(a | (1 << 2)), (a & (1 << 2)) != 0)

It prints

0b1111 0b10 0b1001
0b1111 False

A million numbers, all in pairs but one

Everyone at the party came with a partner, except one person. Find them.

The obvious plan is to count how many times each number appears. That works, and it costs memory the problem may not give you. There is a way with no memory at all.

Xor everything together

Xor undoes itself, and it does not care what order things arrive in. So every pair cancels to 0, and 0 xor the lonely number is the lonely number.

One pass, one variable. This is the trick that makes people love bits.

Python

numbers = [4, 7, 1, 4, 7]

answer = 0
for x in numbers:
    answer ^= x

print(answer)

It prints

1

Why the order cannot matter

Xor works bit by bit, and each bit of the answer is simply "was this bit on an odd number of times?". Shuffling the list does not change that count.

So the pairs cancel wherever they are, even split up across the list.

Python

a = [4, 7, 1, 4, 7]
b = [7, 4, 4, 1, 7]

def fold(numbers):
    answer = 0
    for x in numbers:
        answer ^= x
    return answer

print(fold(a), fold(b))

It prints

1 1

One more, because it turns up constantly

A number is a power of two exactly when it has a single bit on — and knocking that bit off with x & (x - 1) leaves nothing.

Contest code is full of one-line tests like this. They are worth recognising even when you would write the slow version yourself.

Python

for x in [1, 2, 3, 8, 12, 64]:
    print(x, x & (x - 1) == 0)

It prints

1 True
2 True
3 False
8 True
12 False
64 True