HARD Bit Manipulation
201. Bitwise AND of Numbers Range
📖 Problem
Given two integers left and right, return the bitwise AND of all numbers in the range [left, right] inclusive.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •In-place array updates
- •Sorted array traversal
- •Boundary condition checks
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply Two Pointers reasoning pattern
💡 Approach
- → Common prefix of left and right binary representations is the answer
- → Keep right shifting left and right until they become equal
- → Count shifts, then left shift back by that amount
- → All changing bits become 0 in AND result
- → Time: O(log(max(left, right))), Space: O(1)
- → m), Bit manipulation trick with n & (n-1)
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •Common prefix of left and right binary representations is the answer
- •Keep right shifting left and right until they become equal
- •Count shifts, then left shift back by that amount
Common Pitfalls
- •All changing bits become 0 in AND result
- •Time: O(log(max(left, right))), Space: O(1)
- •m), Bit manipulation trick with n & (n-1)
🧪 Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
rangeBitwiseAnd(5, 7); Expected:
4 Test Case 2
Not run Input:
rangeBitwiseAnd(0, 1); Expected:
0 Test Case 3
Not run Input:
rangeBitwiseAnd(1, 2147483647); Expected:
0 📝 Code Editor
📤 Output