⚡Flashcard Drill➔
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

  1. The AND of a range keeps only the bits that are identical in every number of the range.
  2. Two numbers in the range that differ at some bit position guarantee that position is cleared, so only the common prefix of left and right survives.
  3. Shift both numbers right until they become equal, counting the shifts; the equal value is the common prefix.
  4. 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 while 5 & 7 is 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 << shift is required.
  • Using left <= right as the loop condition: the loop must stop as soon as the two prefixes coincide, i.e. on left == right.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems