Sign in to watch this lesson
Algorithms - Bits and Number Theory · 4:44
Binary Representation and Bit Tricks
An integer is a row of bits you can edit in one instruction: place values, two's complement (-13 = 1111 0011), shifts as multiplying and dividing by powers of two (and why -13 >> 1 is -7 but -13 / 2 is -6), and the mask idioms that set, clear, flip and test a bit. Then the trick behind most bit hacks, n & (n - 1), which clears the lowest set bit and gives the power-of-two test and Kernighan's popcount, plus C++20's <bit> functions and the pitfalls of 1 << 31 and __builtin_popcount on 64-bit values. It ends by counting the ones in 1..n in O(log n) by peeling off the top bit.
You will learn
- Read and write integers in binary, including negative numbers in two's complement, and use shifts as multiplication and floor division by powers of two.
- Set, clear, flip and test a single bit with masks, and build 64-bit masks with 1ULL << x instead of 1 << x.
- Explain why n & (n - 1) clears the lowest set bit and use it for the power-of-two test and Kernighan's popcount; use n & -n to isolate the lowest set bit.
- Count the set bits of all numbers 1..n in O(log n) from the fact that numbers below 2^x hold x * 2^(x-1) ones.