0%

数字范围按位与

数字范围按位与

题目

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;
}
}