DSA problem
Bitwise AND of Numbers Range
Given two integers left and right that represent the inclusive range [left, right], return the bitwise AND of all numbers in this range.
Computing the AND by iterating over every number would be far too slow when the range is large. The key observation is that the bitwise AND of a contiguous range equals the common binary prefix shared by left and right, with all trailing bits set to zero.
Intuitively, any bit position that changes at least once across the range will be 0 for some number, forcing the AND of that position to 0. Only the leading bits that are identical in both left and right (and therefore in every number between them) survive.
So the answer is found by stripping away the differing low-order bits until left and right become equal; the resulting common value, shifted back into place, is the result.
Examples
left = 5, right = 74left = 0, right = 00left = 1, right = 21474836470Constraints
- 0 <= left <= right <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.