leetcode-and-of-numbers-range

发表于   |   分类于 ，   |  

题目大意

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

　　给你整数区间[m,n]， 0 <= m <= n <= 2147483647，求这个区间所有数字并运算的结果。

题目分析

　　不要暴力求解，要逐位去考虑。参考discuss区做法，首先对每一位来说，如果最后结果为1，那么这个区间的所有整数在这一位上都是1，结果为0，证明至少有一个数字在此位为0。又注意到是一个连续区间。其实连续区间上的并运算的结果就是区间上所有数字二进制表示的公共首部，也就是区间最小和最大的公共首部，因此移位计算一下就好了。

代码

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