Part 11 of 14

Bit Manipulation

Bit tricks, XOR techniques, bitmask enumeration, single-number patterns.

Chapters
4
Hours
1
Difficulty
Intermediate
  1. 11.0intermediate

    Bit operations cookbook

    The two identities the rest of Part 11 stands on: x & -x for the lowest set bit, x & (x-1) to clear it. Plus popcount, set/clear/flip/test, and subset iteration.

    15 min
  2. 11.1intermediate

    XOR patterns

    XOR patterns: pair-cancellation as a bit-vector group law, and the family of LC problems it solves in O(n) time and O(1) space.

    15 min
  3. 11.2intermediate

    Bitmask techniques

    Encode a small set as an integer; iterate every subset; walk the submasks of a mask. The substrate behind bitmask DP.

    15 min
  4. 11.3advanced

    Bit tricks for performance

    A toolkit of bit-pattern identities — Brian Kernighan's loop, x & -x, SWAR popcount, de Bruijn bit-scan — and the hardware intrinsics that have made most of them obsolete in production.

    15 min