Algorithms / Bit Mixed Interview

Least You Need to Know: Bit Reasoning Depth and Mixed Interview Drills

This tranche pushes bit reasoning one step further, then mixes it with asymptotics, graphs, and invariants the way interview questions often do.

The least you need to know

For positive integers, `x & (x-1)` clears the lowest set bit and becomes 0 exactly for powers of two.
The mask `1 << k` isolates bit position `k` and is the standard building block for set, test, and clear operations.
Good interview answers first choose the right lens: bit trick, graph model, asymptotic simplification, or invariant.
BFS correctness depends on distance-layer reasoning, which behaves like an invariant over the search frontier.
Binary search combines an interval invariant with logarithmic shrinkage.

x & (x-1) clear lowest set bit

1 << k mask with only bit k set

[lo, hi] current candidate interval

For positive `x=16`, the binary form is `10000`.
Then `x-1 = 01111`, so `x & (x-1) = 0`.
That is why the trick detects powers of two.
In the same interview round, you might also need to explain why binary search is logarithmic or why BFS discovers shortest paths layer by layer.

Students often apply the power-of-two bit trick without excluding `x=0`.
Students often confuse setting a bit with toggling a bit.
Students often give only the runtime and forget the invariant or graph idea that makes the algorithm correct.

If the prompt talks about flags or individual positions, think masks and shifts.
If it asks for fewest edges in an unweighted graph, think BFS and distance layers.
If the candidate search space halves each step, think logarithmic growth plus an interval invariant.