Skip to content

Topic 19 of 20

Bit Manipulation

XOR tricks, masks and counting bits: short, fast solutions that impress.

10 problems6 Easy4 Medium0 Hard

The concept

Computers store integers in binary, and operating on those bits directly gives very fast solutions with O(1) extra space. The core operators are AND (&), OR (|), XOR (^), NOT (~) and the shifts (<<, >>). A few identities do most of the work: x ^ x = 0 and x ^ 0 = x (so XOR cancels out pairs), x & (x − 1) clears the lowest set bit, and x & −x isolates it.

Most interview questions here are one of three types. XOR cancellation: find the element that appears an odd number of times. Bit counting: count set bits, or build a table of counts with DP. Masks: test, set or clear the i-th bit, or treat an integer as a set of up to 32 items, which is also what bitmask DP relies on.

Be careful with signed integers and language differences. Python integers are unbounded, while Java and C++ use fixed-width two's complement, so shifts and negative numbers behave differently.

Patterns you will learn

Problems, in order

  1. 1

    XOR cancels pairs; the most famous bit trick.

    XOR CancellationReported at: AmazonMicrosoftGoogle+6
  2. 2

    Brian Kernighan's x & (x − 1) trick.

    Bit CountingReported at: MetaAmazonGoogle+2
  3. 3

    dp[i] = dp[i >> 1] + (i & 1).

    Bit Counting + DPReported at: AmazonGoogleBloomberg+1
  4. 4

    Bit-by-bit reversal with shifts.

    Masks & ShiftsReported at: MetaAppleGoogle+1
  5. 5

    XOR of indices and values, or Gauss's sum.

    XOR CancellationReported at: MicrosoftAmazonMeta+5
  6. 6

    XOR then count bits.

    XOR + Bit CountingReported at: Google
  7. 7

    Addition with XOR and carry, without '+'.

    Bitwise ArithmeticReported at: Meta
  8. 8

    Count each bit position modulo 3.

    Bit Counting per PositionReported at: Amazon
  9. 9

    Split the numbers by one differing bit.

  10. 10

    The AND of a range is the common binary prefix.

    Common Prefix of BitsReported at: Adobe