Interview OS
Back to Algorithms & Data Structures

Library

Bit manipulation

XOR tricks and bit masks.

Math

Overview

Bit manipulation uses AND, OR, XOR, and shifts to pack flags, toggle state, and compute in constant time. It enables elegant tricks — like finding a lone number with XOR — and compact set representations.

How it works

Math
BitsMaskShiftOutputBinary view0b1010AND/OR/XORx&(x−1)<< and >>x>>kResult
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Binary view

    • Treat the number as its bits.
  2. 2

    AND/OR/XOR

    • Set, clear, or toggle bits.
  3. 3

    << and >>

    • Multiply/divide by 2 or extract bits.
  4. 4

    Result

    • Return the bit-level answer.
    • Example: count set bits

Overview

Use bitwise ops for sets, parity, and O(1) state encoding.

Reference

x & (x-1)   // drop lowest set bit
x & -x      // isolate lowest set bit
a ^ b ^ a = b // XOR cancels pairs

Common pitfalls

  • Signed-shift surprises
  • Operator precedence with & | vs ==
  • Overflow on 32-bit assumptions

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides