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; }};新闻热点
疑难解答
