NeetCode #871LC-201MediumBit ManipulationNC 250
← Back to All Problems#871 · #201 · Bitwise AND of Numbers Range(数字范围按位与)
📌 Problem Statement & Constraints
Given two integers
left and right representing the inclusive range [left, right], return the bitwise AND of every number in that range. Constraints: 0 <= left <= right <= 2^31 - 1.💡 Core Algorithmic Approaches
- The AND of a range keeps only the bits that are identical in every number of the range.
- Two numbers in the range that differ at some bit position guarantee that position is cleared, so only the common prefix of
leftandrightsurvives. - Shift both numbers right until they become equal, counting the shifts; the equal value is the common prefix.
- Shift the prefix back left by the same count to restore its position.
💻 Benchmark Python3 Implementation
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
shift = 0
while left < right:
left >>= 1
right >>= 1
shift += 1
return left << shift # restore the common prefix⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log right): at most 32 shift steps.
💾 Space Complexity
O(1): two scalars.
⚠️ Interview Pitfalls & Follow-ups
- AND-ing only the endpoints: the AND of the range is not
left & right; for[5, 7]the answer is 4 while5 & 7is 5. - Looping over every value in the range: up to 2^31 iterations, which times out.
- Forgetting the shift back: the loop strips the low differing bits, so
left << shiftis required. - Using
left <= rightas the loop condition: the loop must stop as soon as the two prefixes coincide, i.e. onleft == right.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.