Bit Manipulation

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A Java int is 32 bits in two's complement. &, |, ^, ~, <<, >>, >>> work on all 32 at once, in O(1).

   #1
2. { }template

   With m = 1 << k: check (x & m) != 0 · set x | m · clear x & ~m · toggle x ^ m.

   #2
3. ✦pro tip

   x & (x − 1) erases the lowest 1-bit (popcount, power of two). x & -x keeps only the lowest 1-bit (Single Number III).

   #3
4. ↯use it when

   "Twice except one", "missing from 0..n", "without + or −", "power of two", "all subsets" with n ≤ 20 → think bits.

   #4
5. ✦pro tip

   XOR: a ^ a = 0, a ^ 0 = a, any order. XOR everything and every pair cancels, in O(1) space.

   #5
6. O( )cost

   One operator: O(1). A loop over a value's bits: O(log V) ≤ 32. All subsets by mask: O(n·2ⁿ). Every submask of every mask: O(3ⁿ).

   #6
7. !trap

   == binds tighter than &: write (x & m) != 0. And (x & m) == 1 is only right for bit 0.

   #7
8. !trap

   1 << 32 == 1 (the shift is taken mod 32): use 1L << k for long masks. >> keeps the sign; use >>> for raw bits.

   #8
9. !trap

   One extra negative: -Integer.MIN_VALUE == Integer.MIN_VALUE. A power-of-two test needs n > 0 first.

   #9
10. ✦pro tip

    Binary numbers as long strings: add column by column from the right with a carry. Integer.parseInt(s, 2) overflows past 31 digits.

    #10

Shaky on a card? Open the chapter or flip its recall cards.