LeetCode 201: Bitwise AND of Numbers Range (Common Prefix by Right Shift)

2026-03-26 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 201Bit ManipulationCommon Prefix

Today we solve LeetCode 201 - Bitwise AND of Numbers Range.

Source: https://leetcode.com/problems/bitwise-and-of-numbers-range/

LeetCode 201 common bit prefix right shift diagram

English

Problem Summary

Given two integers left and right, compute the bitwise AND of every number in the inclusive range [left, right].

Key Insight

Only the common high-bit prefix shared by left and right can survive. Any bit position that changes within the range will eventually become 0 in the AND result.

Optimal Algorithm Steps (Shift to Common Prefix)

1) While left < right, right-shift both by one bit.
2) Count how many shifts were applied.
3) When they become equal, that value is the common prefix.
4) Left-shift back by the same count to restore position.

Why This Works

If left and right differ at some bit, the range crosses both 0 and 1 at that bit, so AND there must be 0. Repeated right shifts remove unstable low bits until only the stable prefix remains.

Complexity Analysis

Time: O(1) in fixed-width integer model (at most 31/32 shifts).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shifts = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shifts++;
        }
        return left << shifts;
    }
}

func rangeBitwiseAnd(left int, right int) int {
    shifts := 0
    for left < right {
        left >>= 1
        right >>= 1
        shifts++
    }
    return left << shifts
}

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shifts = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            ++shifts;
        }
        return left << shifts;
    }
};

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shifts = 0
        while left < right:
            left >>= 1
            right >>= 1
            shifts += 1
        return left << shifts

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeBitwiseAnd = function(left, right) {
  let shifts = 0;
  while (left < right) {
    left >>= 1;
    right >>= 1;
    shifts++;
  }
  return left << shifts;
};

中文

题目概述

给定整数 left 和 right，求区间 [left, right] 内所有整数按位与的结果。

核心思路

结果只可能保留 left 与 right 的公共高位前缀。凡是在区间中会发生 0/1 变化的位，最终按位与必为 0。

最优算法步骤（右移收敛到公共前缀）

1）当 left < right 时，同时右移一位。
2）记录右移次数。
3）两者相等时，得到公共前缀。
4）再左移回去，补回被移除的位数。

正确性解释

若某一位在 left 与 right 间不同，说明这个区间覆盖了该位为 0 和 1 的数，该位按位与一定为 0。不断右移就是逐步去掉这些不稳定低位，直到只剩稳定前缀。

复杂度分析

时间复杂度：O(1)（固定整型位宽下最多移位 31/32 次）。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shifts = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shifts++;
        }
        return left << shifts;
    }
}

func rangeBitwiseAnd(left int, right int) int {
    shifts := 0
    for left < right {
        left >>= 1
        right >>= 1
        shifts++
    }
    return left << shifts
}

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shifts = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            ++shifts;
        }
        return left << shifts;
    }
};

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        shifts = 0
        while left < right:
            left >>= 1
            right >>= 1
            shifts += 1
        return left << shifts

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeBitwiseAnd = function(left, right) {
  let shifts = 0;
  while (left < right) {
    left >>= 1;
    right >>= 1;
    shifts++;
  }
  return left << shifts;
};