Interview Prep Zoneby CuriouserLabs

Question 5 of 5 · senior level

Bit manipulation in practice: masks, shifts, and why hashCode, HashMap and bitsets look the way they do.

🎤 Say this first

Bit operations are the cheapest instructions the CPU has, and a handful of idioms cover almost all production use: masking (x & 0xFF — extract/clear fields), flags (flags | WRITE, flags & ~WRITE, (flags & WRITE) != 0), power-of-two modulo (hash & (n-1) — HashMap's bucket index), unsigned shift (>>> — the overflow-free midpoint), and mixing (h ^ (h >>> 16) — HashMap spreading high bits into the index). Plus the intrinsics that turn loops into single instructions: Integer.bitCount (popcount), numberOfTrailingZeros, highestOneBit. Bitsets pack 64 booleans per long — the memory/bandwidth win behind roaring bitmaps, Bloom filters and GC mark words.

The full picture

The idioms you'll actually read in real code
// HashMap internals, decoded:
int h = key.hashCode();
h = h ^ (h >>> 16);              // fold high bits down (index uses low bits only)
int bucket = h & (table.length - 1);   // n is power of 2 -> & == % but 5x cheaper

// Flags (java.lang.reflect.Modifier, file permissions, feature masks):
int m = mods | Modifier.FINAL;         // set
boolean isFinal = (m & Modifier.FINAL) != 0;  // test
m &= ~Modifier.FINAL;                  // clear

// Round up to next power of two (ArrayDeque, HashMap sizing):
n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);  // JDK's actual code

// BitSet economics: 1M booleans = 1MB as boolean[], 125KB as long[]
long[] seen = new long[(n + 63) >>> 6];
seen[i >>> 6] |= 1L << (i & 63);       // set bit i — index/offset split
  • Why `& (n-1)` requires power-of-two: n−1 is then all-ones below n — the AND keeps exactly the low bits, a perfect cheap modulo. Non-power-of-two n makes it wrong, which is why HashMap forces capacities to powers of two (and why the high-bit spreading step exists at all).
  • `>>` vs `>>>` is a real bug source: arithmetic shift drags the sign bit — (-8) >> 1 == -4 but (-8) >>> 1 is huge-positive; hash and midpoint code wants >>>, arithmetic-on-negatives wants >>. Java needed both because it lacks unsigned types.
  • Hardware sympathy: popcount/CTZ/CLZ are single instructions — Long.bitCount over a bitmap scans set members orders of magnitude faster than boolean arrays (this is roaring bitmaps' and analytics engines' whole trick, plus cardinality sketches like HLL underneath).
  • Honest scope: interview-grade fluency = read the idioms instantly + know why the JDK uses them. Writing XOR-swap party tricks in application code is a review comment, not a skill.

🔄 Likely follow-up questions

  • Why does HashMap spread hashes with h ^ (h >>> 16) instead of using % on a prime table?
  • How do Bloom filters use bit arrays + multiple hashes, and what's the false-positive math?
  • When would you reach for BitSet/roaring bitmaps in a backend service?