LeetCode 201. 数字范围按位与

题目描述

✅ 201. 数字范围按位与

思路分析

解法一：公共前缀（推荐）

核心思路：

  • 同时右移 left 和 right，直到两者相等。
  • 统计右移次数 shift，最后再左移回去。
  • 相等部分即为公共前缀。


复杂度分析：

  • 时间复杂度：O(log n)，其中 n 表示数值大小。
  • 空间复杂度：O(1)。
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}

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

相似题目

题目 难度 考察点
201. 数字范围按位与 中等 位运算
190. 颠倒二进制位 简单 位运算
338. 比特位计数 简单 位运算
231. 2 的幂 简单 位运算
461. 汉明距离 简单 位运算
本文作者:
本文链接: https://hgnulb.github.io/blog/2021/99987536
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！