Handbooks / Data Structures & Algorithms / Chapter 9

Bit Manipulation

7 pages · ~5 min✓ Reviewed

Builds on Dynamic Programming and Greedy. Next up: Math and Number Theory.

Data Structures & AlgorithmsPage 1

Bits and Binary Representation

1. Place Values

Bit i has weight 2^i, counted from 0 at the right (the LSB)
n bits hold 0 to 2^n - 1 unsigned
An integer is a row of on/off switches
Bit tricks flip the switches directly, not via arithmetic

13 to binary: divide by 2, read remainders bottom-up

113 / 2 = 6r 1
26 / 2 = 3r 0
33 / 2 = 1r 1
41 / 2 = 0r 1
513 = 11018+4+0+1

Data Structures & AlgorithmsPage 2

Operators: AND, OR, XOR, NOT and Shifts

1. The Bitwise Operators

Data Structures & AlgorithmsPage 3

Two's Complement and Negative Numbers

1. The Encoding

Data Structures & AlgorithmsPage 4

Check, Set, Clear, Toggle and x & (x-1)

1. Bit i Operations

Data Structures & AlgorithmsPage 5

XOR Tricks, Counting Bits and Bitmask Subsets

1. XOR Tricks

Data Structures & AlgorithmsPage 6

Bit Manipulation Cheat Sheet

1. Operators and bit i

Data Structures & AlgorithmsPage 7

Hex	Binary	Use
`0xF`	1111	one digit = 4 bits
`0xFF`	1111 1111	low 8-bit mask
`0x80000000`	1 then 31 zeros	32-bit top bit

Language	Binary literal	Show binary
Python	`0b1101`	`bin(x)`
C++14	`0b1101`	`std::bitset`
Java 7	`0b1101`	`Integer.toBinaryString(x)`

Op	Bit is 1 when	Use	Identities
`&`	both are 1	mask, test bits	x & 0 = 0, x & x = x
`\|`	either is 1	set bits	x \| 0 = x
`^`	bits differ	toggle, cancel	x ^ x = 0, x ^ 0 = x

Shift	Effect	Fill
`x << k`	x times 2^k	zeros on the right
`x >> k`	floor of x / 2^k	keeps the sign bit
`x >>> k` (Java, JS)	unsigned shift	fills zeros

Op	Expression
Check	`(x >> i) & 1`
Check (mask)	`(x & (1 << i)) != 0`
Set	`x \| (1 << i)`
Clear	`x & ~(1 << i)`
Toggle	`x ^ (1 << i)`

Bit Manipulation

Bits and Binary Representation

1. Place Values

Operators: AND, OR, XOR, NOT and Shifts

1. The Bitwise Operators

Two's Complement and Negative Numbers

1. The Encoding

Check, Set, Clear, Toggle and x & (x-1)

1. Bit i Operations

XOR Tricks, Counting Bits and Bitmask Subsets

1. XOR Tricks

Bit Manipulation Cheat Sheet

1. Operators and bit i

Check yourself

2. Hex

3. Literals and Printing

2. NOT

3. Shifts

2. Range and Hardware

3. Lowest Bit and Gotchas

2. x & (x-1)

3. Mistakes

2. Counting Bits

3. Subsets by Bitmask

2. Tricks and XOR

3. Subsets and traps

Op	Use
`&`	mask / test
`\|`	set
`^`	toggle / cancel
`~`	flip every bit
`<<`	multiply by 2^k
`>>`	divide by 2^k (floor)

Bit i	Expression
Check	`(x>>i)&1`
Set	`x\|(1<<i)`
Clear	`x&~(1<<i)`
Toggle	`x^(1<<i)`