17 MIN GUIDE · INTERMEDIATE · BIT MANIPULATION

Bit Manipulation and Bitmask Patterns

Read, set, clear and toggle bits; use XOR cancellation; encode subsets as masks; and recognise when binary structure removes extra memory.

Integers are bit strings

Computers store non-negative integers in binary. Each bit position represents a power of two:

position     4 3 2 1 0
power      16 8 4 2 1
13          0 1 1 0 1

The bitwise operators work position by position:

Operation	Symbol	Result bit is 1 when
AND	`a & b`	both bits are 1
OR	`a ∣ b`	at least one bit is 1
XOR	`a ^ b`	the bits are different
NOT	`~a`	the bit is flipped
Left shift	`a << k`	bits move k places left
Right shift	`a >> k`	bits move k places right

Left-shifting a non-negative integer by k multiplies it by 2ᵏ when no overflow occurs. Right-shifting by k performs integer division by 2ᵏ.

Working with one bit

The mask 1 << k has only bit k set.

Read: (x >> k) & 1, or test whether (x & (1 << k)) != 0.
Set: x ∣ (1 << k).
Clear: x & ~(1 << k).
Toggle: x ^ (1 << k).

Parentheses matter because shift and comparison precedence differs across languages.

XOR cancellation

XOR has three crucial properties:

x ^ x = 0,
x ^ 0 = x,
order and grouping do not change the result.

Therefore, if every value appears twice except one, XORing the entire array cancels every pair and leaves the singleton. Similar algebra can separate two unpaired values or compute parity.

Find the singleton in [4, 1, 2, 1, 2]

Start
answer = 0

answer

XOR identity

Combining with zero leaves a value unchanged.

Counting set bits

Two useful recurrences are:

bits[x] = bits[x >> 1] + (x & 1), which reuses the count after removing the last bit,
x & (x - 1), which clears the lowest set bit.

The second identity counts the 1 bits in one number using one iteration per set bit. The first builds counts for every number from 0 through n in linear time.

Bitmasks as sets

When a universe contains at most a few dozen items, bit k can represent whether item k is present.

empty set: 0,
membership of k: mask & (1 << k),
add k: mask ∣ (1 << k),
remove k: mask & ~(1 << k),
iterate all subsets: masks from 0 to (1 << n) - 1.

Bitmasks make subset DP, state compression, permissions and visited-state keys compact. Their limit is the integer width: JavaScript bitwise operators use signed 32-bit values, while Python integers grow as needed.

A small bit toolkit

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


def single_number(values):
    answer = 0
    for value in values:
        answer ^= value
    return answer


print("bits in 13:", popcount(13))
print("singleton:", single_number([4, 1, 2, 1, 2]))
print("subsets of 3 items:", 1 << 3)

Output

bits in 13: 3
singleton: 4
subsets of 3 items: 8

Signed values and overflow

Fixed-width languages store negative integers using two's complement. Right shift may copy the sign bit, and left shift can overflow. Use unsigned types or unsigned shifts when the problem treats bits as a raw word. Also avoid 1 << k when k may equal or exceed the type width.

Practice XOR cancellation in Single Number, bit recurrence in Count Bits from 0 to N, and high-to-low greedy bit choice in Maximum XOR Pair.