Bit Operators

On this page 16

Part I — Foundations · Interview reference

Bitwise operators manipulate individual bits of integer values. Seniors are expected to read flag-heavy APIs, reason about masks/shifts correctly (including sign and overflow), and know when bit tricks are justified versus premature cleverness.

Core operators (must know cold)

Operator	Name	Meaning	Typical use
`&`	AND	Bit set only if set in both	Mask / clear / test flags
`\|`	OR	Bit set if set in either	Combine / set flags
`^`	XOR	Bit set if different	Toggle; parity; swap without temp (rarely needed)
`~`	NOT	Flip all bits	Form masks; one’s complement pitfalls with signed types
`<<`	Left shift	Multiply by 2ⁿ (unsigned view)	Build masks; pack fields
`>>`	Arithmetic right shift	Sign-extends (most languages)	Signed division by 2ⁿ (careful with negatives)
`>>>`	Logical right shift	Zero-fills (Java/JS)	Treat value as unsigned bit pattern

Identity / algebra worth memorizing

x & 0 = 0, x | 0 = x, x ^{0 = x}, x x = 0
x & x = x, x | x = x
De Morgan: _{(a & b) (}a | _b), (a | b) (_{a &}b) (within fixed width)

Mental models

Flags and masks

Treat an integer as a set of independent booleans packed into bits.

flags |=  MASK;     // set bits in MASK
flags &= ~MASK;     // clear bits in MASK
flags ^=  MASK;     // toggle bits in MASK
bool on = (flags & MASK) != 0;  // test (any)
bool all = (flags & MASK) == MASK; // test (all)

Prefer named constants / enum bitfields over magic numbers. Document which bit means what and whether the API is additive (|) or exclusive.

Packing / unpacking fields

// pack: value in bits [lo, hi)
packed = (packed & ~mask) | ((field << shift) & mask);

// unpack
field = (packed >> shift) & ((1 << width) - 1);

Watch signed shift and width overflow when width == word_size.

Production case study (high volume)

Context: A multi-tenant SaaS API (~50M authz checks/day) packs role + resource-scope capabilities into a 64-bit bitfield carried on every request (similar to Discord’s permission integers or AWS IAM action bitsets in custom PDPs). Why seniors care: A wrong mask silently grants/denies at p99 scale; concurrent flags |= MASK without atomics loses updates under fan-out; signed >> on “unsigned” capability words corrupts high bits. Failure / symptom: Intermittent privilege escalation after a “toggle capability” deploy; metrics show CAS failure spikes on AtomicLong; dumps show plain int RMW on a shared session object. Resolution: Named static final long masks; AtomicLong.getAndUpdate for concurrent updates; property tests for set/clear/test; document MSB numbering and endianness for any cross-service packing. Seen at / similar to: Discord permission bitfields; game/anti-cheat flag packs; Redis BITFIELD / presence bitmaps at Twitter-scale timelines historically.

Two’s complement (interview trap)

Negation: -x == (~x) + 1
Sign bit is MSB; arithmetic >> preserves it
INT_MIN negation overflows in two’s complement; abs/min discussions fail here

Common idioms seniors should recognize

Idiom	Expression	Notes
Power of two?	`(x & (x - 1)) 0` (and `x > 0`)	Classic; fails for `x 0`
Isolate lowest set bit	`x & -x`	Two’s complement
Clear lowest set bit	`x & (x - 1)`	Trailing-zero / popcount loops
Round up to power of 2	bit-smear then `+1`	Off-by-one on already-power-of-2
Swap without temp	`a ^{= b; b}= a; a ^= b`	Avoid; hurts readability; fails if `a`/`b` alias same location poorly in some langs
Absolute value (branchless)	mask = `x >> 31`; `(x ^ mask) - mask`	Signed 32-bit; still breaks on `INT_MIN`
Endian / byte extract	shifts + `0xFF` masks	Network byte order conversions

Production case study (high volume)

Context: Ad-exchange / fraud pipeline (~billions of membership tests/day) uses Bloom filters and Roaring bitmaps for “seen device / creative ID” before hitting a KV store. Why seniors care: Wrong popcount/clear-lowest-bit loops on the hot path waste CPU; false-positive rate is a cost knob (extra origin fetches); bitset cardinality bugs show up as revenue leakage, not unit-test failures. Failure / symptom: CPU saturation on filter update threads; p99 spike when filters resized; elevated origin QPS from underestimated FPR after cardinality grew 10×. Resolution: Hardware popcnt / JDK Long.bitCount intrinsified paths; size filters from measured cardinality + target FPR; move presence sets to Roaring/Guava; load-test membership + update together. Seen at / similar to: Ad platforms (Google/Meta-style edge filters); CDN/WAF IP reputation sets; Cassandra/HBase-style Bloom use in LSM read paths.

Language / platform gotchas

Topic	Expectation
Signed vs unsigned	C/C++: promotion and shift of signed negatives are easy UB/implementation-defined traps. Prefer unsigned for bit ops.
Java	No unsigned types historically; use `>>>`, `Integer.toUnsignedLong`, mask with `0xffffffffL`.
Width	Shifting by ≥ word size is UB in C; Java masks shift count (`& 0x1f` / `& 0x3f`).
Floats	Bit ops on floats require reinterpretation (`memcpy` / bit cast); NaN/endian issues.
SIMD / popcount	Prefer hardware `popcnt`, `tzcnt`, `lzcnt` / language intrinsics over hand loops when performance matters.

Java under the hood

Tool	What it is underneath
Shift count	JVM masks: `int` shifts `& 0x1f`, `long` `& 0x3f` — no UB, but surprising wrap
`Integer` / `Long` helpers	`bitCount`, `numberOfLeadingZeros`, `numberOfTrailingZeros`, `rotateLeft/Right`, `highestOneBit` — HotSpot often intrinsifies to `popcnt` / `lzcnt` / `tzcnt`
Unsigned view	`Integer.toUnsignedLong`, `Integer.divideUnsigned`, `>>>` for logical right shift
`BitSet`	Packed `long[]` words; grow on demand; good for sparse-ish flag sets over large domains
`EnumSet`	Bit vector indexed by enum ordinal — extremely cheap membership for small enums
Concurrent flags	`AtomicInteger` / `AtomicLong` bitwise `getAndUpdate` / `updateAndGet` (CAS loop) — plain `\|` on a shared `int` is not thread-safe
Wide integers	`BigInteger` for arbitrary-width bits (heap-backed magnitude array; not a substitute for hot-path masks)
Float bits	`Float.floatToIntBits` / `Double.doubleToLongBits` (and raw variants) for reinterpretation

Prefer named static final int masks or EnumSet over magic numbers. For concurrent bitfields, use atomics — see thread safety.

Production case study (high volume)

Context: Payments risk service on HotSpot evaluates millions of rule flags/sec using EnumSet for rule categories and BitSet for sparse “rule fired” vectors exported to analytics. Why seniors care: EnumSet is a bit vector — seniors must know why it beats HashSet<Enum> under allocation pressure; concurrent plain BitSet is not safe; GC/alloc from boxing kills p99. Failure / symptom: Young-gen thrash and elevated TLAB refill rate after switching flags to HashSet; intermittent lost flag bits under parallel rule evaluation. Resolution: Keep hot-path flags as EnumSet/BitSet copies per request (confine), merge with atomics or thread-local builders; JFR allocation samples confirm the win. Seen at / similar to: Stripe/Adyen-style rules engines; feature-flag packs in large JVM monoliths (Shopify Core historically).

When bit operators belong in production

Use when

Protocol / file formats with packed fields
Permission / capability flags
Bloom filters, bitsets, succinct structures
Low-level hashing, CRC, crypto primitives (usually via library)
Cache-friendly presence sets (Roaring bitmaps, etc.)

Avoid when

Business logic that is clearer with EnumSet, booleans, or small structs
“Clever” optimizations without measured hotspots
Cross-language APIs without a documented bit layout and endianness

Complexity & performance notes

Bit ops are O(1) on machine words; bitsets over n bits are O(n/word_size)
Branchless bit tricks can beat branches or lose (branch predictors are good; data dependencies hurt)
False clarity cost often exceeds CPU savings — interviewers notice judgment here

What interviewers probe

Explain (n & (n - 1)) and edge cases (0, negatives).
Signed right shift vs logical — and which language you are in.
Set / clear / toggle / test a flag correctly without clobbering others.
Endianness when packing multi-byte fields for the network.
Why bit packing might be wrong for a mutable concurrent flags field (atomicity of RMW, visibility) — link to thread safety.
Count set bits — naive loop vs Kernighan vs hardware popcount; complexity.
Production bitset/Bloom — how FPR and concurrent updates show up in cost and correctness SLOs.

Senior-level expectation: Correctness + clear naming + knowing when not to use bit tricks. Being able to whiteboard a permission mask API and discuss concurrent updates (AtomicInteger bit CAS loops). Tie bit packing to blast radius of authz bugs at millions of checks/day.

Pitfalls checklist

Testing flags with == MASK when you meant “any bit”
Using ~ without masking back to intended width
Arithmetic shift on values you thought were unsigned
Shifting into / through the sign bit unexpectedly
Assuming left shift cannot overflow silently
Documenting bit 0 as “first” without saying MSB vs LSB numbering
Using XOR swap or branchless abs in interview code when clarity matters more
Plain | / &= on shared flags under concurrency (need atomics)
Shipping Bloom filters without sizing for actual cardinality growth

Cross-references

CPU architecture — word size, cache lines, popcount throughput
Data structures — bitsets, Bloom filters
Thread safety — concurrent flag updates need atomics, not plain |