数字范围按位与

发表于
本文字数： 853 阅读时长 ≈ 1 分钟

LeetCode题目，201. Construct Binary Tree from Inorder and Postorder Treversal

先看题目描述

大意就是给定两个数表示一个范围，让我们返回该范围内所有数按位与的结果

算法和思路

刚看到这道题的时候，基本思毫无头绪，不知道怎么做，后来看题解，发现这个应该算是个数学题，只要看出题目本质就很好做

统计最长公共前缀

假设两个数在第 i 位及之前都相同，那么必定一个第 i + 1 位为 0，一个第 i + 1 位为 1，则这两个数之间一定存在一个数，这个数的第 i + 1 位为 1，且后面全都是 0，这样按位与以后第 i + 1 位以及之后全都为 0 了

例如 m 和 n 的最长公共前缀为 00101，假设 m > n，那么 m 可以表示为 001011XXXX，n表示为 001010XXXX，这两个数之间一定存在一个数为 0010110000，这样按位与以后的结果就为 0010100000

所以求两个数的公共前缀即可，通过两个数不断右移，直到两个数相等，再左移相应位数。例如 m 和 n 一起右移 5 位后得到两个数相等为 00101，那么再将这个数左移 5 位得到 0010100000，这个数转成十进制就是要返回的结果

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if (m == n) return m;
        int shift = 0;
        while (m != n) {
            m = m >> 1;
            n = n >> 1;
            shift++;
        }
        return m << shift;
    }
}