Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
解題思路
這道題的意思是將[m,n]之間的數(shù)全部進(jìn)行&操作蔗衡，求最后的值。我們不妨設(shè)m和n這兩個(gè)數(shù)字前k位二進(jìn)制數(shù)相同后雷，即：
m=a1a2...ak0ak+2...a32 n=a1a2...ak1ak+2...a32
對于第k+2位二進(jìn)制數(shù)到第32位鸣个，我們總可以找到一個(gè)[m榛斯，n]之間的數(shù)绊汹，使得該數(shù)位上的二進(jìn)制數(shù)值為0
所以我們要求的值為
ans = a1a2...ak00...0（32-k個(gè)0）
我們來看具體的求法：
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
while (n > m){
n &= (n-1);
}
return n;
}
};
n &= (n-1)這行代碼的含義是將n的二進(jìn)制數(shù)最低位的1變?yōu)?，所以整段代碼是不斷將n的二進(jìn)制數(shù)最低位的1變?yōu)?直到n <= m,也就求出了我們要求的ans奖慌。
舉個(gè)栗子
初始
7 = 1011, 5 = 1001，可知我們要求的ans = 1000
循環(huán)過程
7 -> 1011 -> 1010 -> 1000 <= 5 所以ans = 1000 = 4
