Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: [5,7] Output: 4
Example 2:
Input: [0,1] Output: 0
A:
其实就是挨个查看,该位是否在为全1.
class Solution { public: int rangeBitwiseAnd(int m, int n) { int res = 0; for(int i = 31;i>=0;i--){ long mask = 1<<i; if( m>=mask && n <=mask+mask-1){ res += (int)mask; m -= mask; n -= mask; } } return res; } };
Mistakes:
1: 当时,感觉,如果高位不在全1 区间。就可以break了。
但是,没有考虑,还可能是 全0 , 因此不能break。
**********************************************
我们先从题目中给的例子来分析,[5, 7]里共有三个数字,分别写出它们的二进制为:
101 110 111
相与后的结果为100,仔细观察我们可以得出,最后的数是该数字范围内所有的数的左边共同的部分,如果上面那个例子不太明显,我们再来看一个范围[26, 30],它们的二进制如下:
11010 11011 11100 11101 11110
发现了规律后,我们只要写代码找到左边公共的部分即可,我们可以从建立一个32位都是1的mask,然后每次向左移一位,比较m和n是否相同,不同再继续左移一位,直至相同,然后把m和mask相与就是最终结果,代码如下:
public class Solution { public int rangeBitwiseAnd(int m, int n) { int mask = Integer.MAX_VALUE; for(int i =0;i<31;i++){ if( (mask & m) == (mask&n)) break; mask = mask << 1; } return mask & m; } }
No comments:
Post a Comment