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.
s思路： 1. 簡單粗暴的做法，就是把所有數都遍歷一遍做and。這肯定不是題目要求的做法 2. 需要根據and的特點，如果所有數全1，and結果才為1，只要有一個0，結果都是0.也就是說，and運算是不精確的運算！ 3. 仔細看了一下，總結規律。例如：[5,7]
5:1016:1107:111把5和7做AND可以得到101，即：高位是正確的，但是低位由于沒有and中間變化的值，所以不正確；把7-5得到010，其中1表示從這一位有翻轉，由于這一位有翻轉，那么1右邊的都應該有翻轉，即：看到的是從右往左第2位翻轉了，由于高位翻轉是因為低位翻轉引起的，所以低位也必然翻轉，所以看到1，說明這個1和之后的所有數位都翻轉過，所以只需要找到這個差值最左邊1的位置，然后把5和7的and結果從這個位置往右所有數都置零！ 4. 另外還在網上看到方法2，也很妙！妙在哪兒呢？從m==n這個極限條件出發：當m==n,說明m就是結果，但是大部分情況m!=n。這個解法有意思的地方，就是把m!=n的普遍情況想辦法變成m==n的邊界情況。如何變？有一個基本事實是這樣的：如果n>m,最低位必然是翻轉過的。因此，我們設置一個變量pos來記錄翻轉的bit位，然后m和n都往右移一位，繼續比較m和n，這個過程是iterative,直到m==n,此時我們也知道有多少位是翻轉過的，因此把這些位置零即可！ 5. 這中思路可以推廣：從極限情況出發，這里就是m==n就是極限情況，把其他的情況移位得到極限情況。
//方法1：按bit一位一位的處理。detail-oriented。bottom-up思路class Solution {public: int rangeBitwiseAnd(int m, int n) { // int res=m&n; int diff=n-m; int pos=0; while(diff){ diff>>=1; if(res&1<<pos) res=res^1<<pos; pos++; } return res; }};//方法1.1：還是一位一位的移動，優化了一下，不用在中間用mask,最后用一次mask就可以了！29msclass Solution {public: int rangeBitwiseAnd(int m, int n) { // int res=m&n; int diff=n-m; int pos=0; while(diff){ diff>>=1; pos++; } res=res&~((1<<pos)-1); return res; }};//方法2：抓住邊界條件！這個思路也很好，就是慢點！52msclass Solution {public: int rangeBitwiseAnd(int m, int n) { // int pos=0; while(m!=n){ ++pos; m>>=1; n>>=1; } return m<<pos; }};新聞熱點
疑難解答
