LeetCode 201 - Bitwise AND of Numbers Range

https://leetcode.com/problems/bitwise-and-of-numbers-range/
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.
http://www.cnblogs.com/grandyang/p/4431646.html

又是一道考察位操作Bit Operation的题，相似的题目在LeetCode中还真不少，比如Repeated DNA Sequences 求重复的DNA序列， Single Number 单独的数字,   Single Number II 单独的数字之二 ， Grey Code 格雷码，和 Reverse Bits 翻转位 等等，那么这道题其实并不难，我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果，代码如下：

    int rangeBitwiseAnd(int m, int n) {
        int d = INT_MAX;
        while ((m & d) != (n & d)) {
            d <<= 1;
        }
        return m & d;
    }

此题还有另一种解法，不需要用mask，直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果

    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++i;
        }
        return (m << i);
    }

下面这种方法有点叼，就一行搞定了，通过递归来做的，如果n大于m，那么就对m和n分别除以2，并且调用递归函数，对结果再乘以2，一定要乘回来，不然就不对了，就举一个最简单的例子，m = 10, n = 11，注意这里是二进制表示的，然后各自除以2，都变成了1，调用递归返回1，这时候要乘以2，才能变回10

    int rangeBitwiseAnd(int m, int n) {
        return (n > m) ? (rangeBitwiseAnd(m / 2, n / 2) << 1) : m;
    }

下面这种方法也不错，也很简单，如果m小于n就进行循环，n与上n-1，那么为什么要这样与呢，举个简单的例子呗，110与上(110-1)，得到100，这不就相当于去掉最低位的1么，n就这样每次去掉最低位的1，如果小于等于m了，返回此时的n即可

    int rangeBitwiseAnd(int m, int n) {
        while (m < n) n &= (n - 1);
        return n;
    }

http://buttercola.blogspot.com/2015/08/leetcode-bitwise-and-of-numbers-range.html
We could take several examples, e.g. 5 6 7
101
110
111
-------
100

We could find out that the trick of the problem is when compare bit-by-bit for each number, once they are the same, e.g. bit 1 for the most significant bit, they start to be the same. 

9 10 11 12
1001
1010
1011
1100
---------
1000
So the solution is shift both m and n to the right until they are the equal, count the number of steps it shifted. Then shift m left to the number of steps. 

    public int rangeBitwiseAnd(int m, int n) {

        int shift = 0;

         

        while (m != n) {

            shift++;

            m = m >> 1;

            n = n >> 1;

        }

         

        return m << shift;

    }

    public int rangeBitwiseAnd(int m, int n) {
        if(m == 0){
            return 0;
        }
        int moveFactor = 1;
        while(m != n){
            m >>= 1;
            n >>= 1;
            moveFactor <<= 1;
        }
        return m * moveFactor;
    }

https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/56721/2-line-Solution-with-detailed-explanation

 public int rangeBitwiseAnd(int m, int n) {
        while(m<n) n = n & (n-1);
        return n;
    }

The key point: reduce n by removing the rightest '1' bit until n<=m;

(1)if n>m,suppose m = yyyzzz, n = xxx100, because m is less than n, m can be equal to three cases:

(a) xxx011 (if yyy==xxx)
(b) less than xxx011 (if yyy==xxx)
(c) yyyzzz (if yyy<xxx)

for case (a), and (b), xxx011 will always be ANDed to the result, which results in xxx011 & xxx100 = uuu000(uuu == yyy&xxx == xxx);

for case (c), xxx000/xxx011 will always be ANDed to the result, which results in yyyzzz & xxx000 & xxx011 & xxx100 = uuu000 (uuu <= yyy & xxx)

=> for any case, you will notice that: rangBitWiseAnd(vvvzzz,xxx100) == uuu000 == rangBitWiseAnd(vvvzzz,xxx000), (not matter what the value of"uuu" will be, the last three digits will be all zero)

=> This is why the rightest '1' bit can be removed by : n = n & (n-1);

(2)when n==m, obviously n is the result.

(3)when n < m, suppose we reduce n from rangBitWiseAnd(yyyzzz,xxx100) to rangBitWiseAnd(yyyzzz,xxx000);

i) xxx100 >yyyzzz => xxx >= yyy;

ii) xxx000 < yyyzzz => xxx <= yyy;

=> xxx == yyy;

=> rangBitWiseAnd(yyyzzz,xxx000) == rangeBitWiseAnd(xxxzzz,xxx000);

=>result is xxx000, which is also n;

https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/56729/Bit-operation-solution(JAVA)

1. last bit of (odd number & even number) is 0.
2. when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
3. Move m and n rigth a position.

Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.

http://www.programcreek.com/2014/04/leetcode-bitwise-and-of-numbers-range-java/

The key to solve this problem is bitwise AND consecutive numbers. You can use the following example to walk through the code.

    8  4  2  1
---------------
5 | 0  1  0  1
6 | 0  1  1  0
7 | 0  1  1  1

X.  http://yucoding.blogspot.com/2015/06/leetcode-question-bitwise-and-of.html
At the first glance, looping from m to n seems straightforward but obviously time-consuming.
Looping from number to number seems unavailable, but we can considering looping from bit to bit.
Let's first write down some binary numbers:

1    000001
2    000010
3    000011
4    000100
5    000101
6    000110
7    000111
8    001000

Let's consider each bit from low to high, we can observe that the lowest bit, is either 1 or 0 after a number of AND operation. In this problem, because the range is continuous, the only case that lowest bit will become 1 is when m==n, and the lowest bit is 1. In other words,  for the range [m, n], if n > m, the lowest bit is always 0. Why? Because either the lowest bit of m is 0 or 1, the lowest bit of (m AND m+1) must be 0.

Now we have get the lowest bit for final result, next step is to check the 2nd lowest bit. How to do it? Just using bit shifting!  m >> 1 and n >> 1 is all we need.

When to stop looping? Consider the case that:
m =  01000
n =   01011

(1)   01011 > 01000  ->  lowest bit = 0
(2)   0101 > 0100      ->  2nd lowest bit  = 0
(3)   010 = 010          ->  3rd lowest bit = current lowest bit  0
(4)   01 = 01              ->  4th lowest bit = current lowest bit   1
(5)   0 = 0                  ->  5th lowest bit = current lowest bit   0

Final result:   01000
We can see that step (3)-(5) is unnecessary, when m=n, the other bits are just the same as current m (or n), then we can easily get the final result.

    int rangeBitwiseAnd(int m, int n) {

        int k=0;

        while (1) {

            if (n>m){

               k = k + 1; 

            }else{

                return m << k;

            }

            m = m >> 1;

            n = n >> 1;

        }

        return m;

    }

    def rangeBitwiseAnd(self, m, n):

        if n > m:

            return self.rangeBitwiseAnd(m>>1, n>>1) << 1

        else:

            return m

http://siyang2leetcode.blogspot.com/2015/05/bitwise-and-of-numbers-range.html
The result of AND operation is just left most consecutive common part of n and m (just two numbers, no need of numbers in between). 

 public int rangeBitwiseAnd(int m, int n) {  
     int count = 0;  
     while(m != n){  
       m >>= 1;  
       n >>= 1;  
       count++;  
     }  
     return m<<=count;  
   } 

https://leetcode.com/discuss/32017/my-simple-java-solution-3-lines
public int rangeBitwiseAnd(int m, int n) { int r=Integer.MAX_VALUE; while((m&r)!=(n&r)) r=r<<1; return n&r; }
http://pisxw.com/algorithm/Bitwise-AND-of-Numbers-Range.html
结果其实就是m和n公共头部。例子中5的二进制为101,7的二进制位111，其公共头部为100。再如，若计算3到5的按位或，3的二进制位11，5的二进制位101，没有公共头部，返回0。
public int rangeBitwiseAnd(int m, int n) { if(m>n) return 0; int i=0; //通过移位寻找公共的头 while(m!=n && m!=0) { m=m>>1; n=n>>1; i++; } return m<<i; }

X. keep comparing from lower bits to higher bits can do the trick.
http://siyang2leetcode.blogspot.com/2015/05/bitwise-and-of-numbers-range.html
http://www.jiuzhang.com/solutions/bitwise-and-of-numbers-range/

    public int rangeBitwiseAnd(int m, int n) {
        if (n == m) {
            return n;
        }
        if (n - m == 1) {
            return n & m;
        }
        return rangeBitwiseAnd(m / 2, n / 2) << 1;
    }

X. Notes: n&(n-1) 清掉最后一位1。
http://www.hihuyue.com/hihuyue/codepractise/leetcode/leetcode179-bitwise-and-of-numbers-range
http://www.shuatiblog.com/blog/2015/05/10/Bitwise-AND-of-Numbers-Range/

public int rangeBitwiseAnd(int m, int n) { while (n > m) { n = n & n - 1; } return m & n; }

X. http://likesky3.iteye.com/blog/2235945

1.     public int rangeBitwiseAnd(int m, int n) {  
2.         int mask = -1;  
3.         while ((m & mask) != (n & mask)) {  
4.             mask <<= 1;  
5.         }  
6.         return m & mask;  
7.     } 

X.  https://miafish.wordpress.com/2015/04/18/leetcode-ojc-bitwise-and-of-numbers-range/
find highest bits of two numbers, if they are not same, return 0; otherwise add that to the final result. two numbers remove the highest bits and recursively check again.

public int RangeBitwiseAnd(int m, int n)
        {
            var res = 0;
            while (m > 0 && n > 0)
            {
                var highestBitsM = (int)Math.Log(m, 2);
                var highestBitsN = (int)Math.Log(n, 2);

                if (highestBitsM != highestBitsN)
                {
                    return res;
                }

                var highestValue = (int) Math.Pow(2, highestBitsM);

                res += highestValue;
                m = m - highestValue;
                n = n - highestValue;
            }

            return res;
        }

http://blog.csdn.net/kangrydotnet/article/details/45099051
计算[m, n]的非负整数的按位异或。一种解法非常巧妙

1. long long f(long long a) {  
2.      long long res[] = {a,1,a+1,0};  
3.      return res[a%4];  
4. }  
5.   
6. long long getXor(long long a, long long b) {  
7.      return f(b)^f(a-1);  
8. }  

为什么这个代码能够工作呢？让我们先看看4位二进制的从0到a的按位异或。

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

上述代码中，我们看到，f函数其实就是返回[0, a]的按位异或。对于主体函数，f(b)表示从[0, b]的异或，f(a-1)表示[0, a-1]的异或，f(b)^f(a-1)则等于[a, b]的异或。因为任何数异或自身都为0。

X.
https://leetcode.com/discuss/32520/my-2-line-java-solution
public int rangeBitwiseAnd(int m, int n) { for(int i=0;i<31;i++) if((m>>(30-i))!=(n>>(30-i))) return (n>>(31-i)) << (31-i); return m; }
https://leetcode.com/discuss/56100/easy-to-understand-java-solution
public int rangeBitwiseAnd(int m, int n) { //The whole point is to find the first bit where and m and n is different; long i = 1L<<31; long res = 0; while(i>0){ if((m&i) == (n&i)){ res |= m & i; } else{ break; } i = i>>>1; } return (int)res; }
X. Math
https://leetcode.com/discuss/35297/a-math-solution
public int rangeBitwiseAnd(int m, int n) { if (m == n){ return m; } //The highest bit of 1 in diff is the highest changed bit. int diff = m ^ n; //Index is the index of the highest changed bit. Starting at 1. int index = (int)(Math.log(diff) / Math.log(2)) + 1; //Eliminate the changed part. m = m >> index; return m << index; }

def rangeBitwiseAnd(self, m, n): b = (m ^ n).bit_length() return m >> b << b
https://leetcode.com/discuss/34415/my-o-1-solution-using-bitwise-xor-and

int rangeBitwiseAnd(int m, int n) {
            int xmask = m ^ n;
            int mlen = 0;
            int mask;

            if ((xmask >> (mlen + 16)) > 0) mlen += 16;
            if ((xmask >> (mlen + 8)) > 0) mlen += 8;
            if ((xmask >> (mlen + 4)) > 0) mlen += 4;
            if ((xmask >> (mlen + 2)) > 0) mlen += 2;
            if ((xmask >> (mlen + 1)) > 0) mlen ++;

            mask = ~0 << mlen;

            return m & mask;
    }

https://leetcode.com/discuss/83738/java-8-ms-one-liner-o-1-no-loop-no-log

public int rangeBitwiseAnd(int m, int n) {
    return m == n ? m : m & ~((Integer.highestOneBit(m ^ n) << 1) - 1);
}

The idea here is pretty simple: when we go from m to n some higher part may remain the same. The lower part changes. If we take the highest bit that is different, then it must be true that it is 1in n and 0 in m, simply because n is larger than m. That means that at some point it went from 0 to 1, and at that very point the lower digits must have all turned to zeroes, just like it happens in decimal when we go up to 1000 from 999. That means that all lower bits will be zero in the result. The differing bit will also be zero for obvious reasons. The higher part (if any) will remain as it is because it didn't change at all.

Therefore, we take that differing bit (Integer.highestOneBit(m ^ n)) and then create a mask that fills the whole thing with 1 to the right, including that bit. We achieve that by shifting that bit left (we can do it because we know that n < Integer.MAX_VALUE), then we subtract 1 so that bit goes to zero and everything to the right turns into ones. Then we bit-reverse the mask and apply it either to m or to n, doesn't matter because the higher part is identical.

Unfortunately, that doesn't quite work when m == n because then m ^ n will be zero and we'll end up zeroing the whole thing.

In case anyone feels like using Integer.highestOneBit is cheating, here is it's code, from the standard Java library:

    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);

Doesn't look that complicated, does it? (If you think it does, look at Integer.reverse or something.)

What happens here is that we first OR bit pair-wise. If any bit was 1 to begin with or had 1 to the left, it will now be 1. Then we do the same thing with resulting pairs. Now every bit will be 1if at least one of the following is true:

• it was 1 to begin with;
• its left neighbor was 1 (so it became 1 on the previous step);
• its next left neighbor was 1 (because now we OR exactly with this next neighbor);
• its next-next left neighbor was 1 (because now we OR exactly with this next neighbor and that neighbor was ORed with its neighbor on the previous step).

So each ith bit will be 1 if at least of the bits i + 1, i + 2, i + 3 was 1. Note that the code uses signed shifting, but it doesn't really matter because if i is negative we'll fill everything with1 anyway.

By repeating this process we finally have a mask that fills everything with 1 from the highest bit and to the right. By shifting it and subtracting we get the highest bit. Speaking of which, looks like we can use this code directly to solve our problem, although it won't be a one-liner any more:

public int rangeBitwiseAnd(int m, int n) {
    if (m == n) {
        return m;
    }
    int i = m ^ n;
    i |= (i >>> 1);
    i |= (i >>> 2);
    i |= (i >>> 4);
    i |= (i >>> 8);
    i |= (i >>> 16);
    return m & ~i;
}

Read full article from LeetCode[179]: Bitwise AND of Numbers Range | 形&影