数字范围按位与

数字范围按位与

题目

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

思路

最容易想到的就是暴力做，但肯定会超时。需要想有没有什么规律算法？

2进制的数字每一个都是在前一个基础上变动而来的，那么他们应该是从某一位之前是相同的。而这一位的位置应该随着两个数的距离而向前移动，所以我们可以将问题简化求为最左端与最右端的这个数的位置，在这个数之前每个位都是相同的，也就是and之后不影响结果，而之后因为两个数之间多个数and导致为0，所以只需要保留前面相同的位置，后面的取0即可。

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