Bit Manipulation

Every number is a row of on/off switches. Bit tricks flip those switches directly.

The idea (a row of light switches)

Inside the computer a number is stored in binary: a row of switches, each either 0 (off) or 1 (on). Each switch has a place value: from the right they are 1, 2, 4, 8, 16, 32, 64, 128. Add up the values of the switches that are on. For example 00001100 is 8 + 4 = 12. This page uses 8 switches (Go’s uint8, numbers 0 to 255).

Watch it work

Try it

Common mistakes

Complexity, in plain English: AND, OR, XOR and shifts are single machine instructions (O(1)). Counting bits with n & (n-1) loops once per 1 bit, not once per bit position. The single-number trick scans the list once and needs no extra memory.