LeetCode 201. Digit range bitwise AND

201. Digital range bitwise AND

difficulty secondary

Here are two integers left and right , Indicates the interval [left, right] , Returns all numbers in this range Bitwise AND Result （ contain left 、right Endpoint ）.

Example 1：

 Input ：left = 5, right = 7
 Output ：4

Example 2：

 Input ：left = 0, right = 0
 Output ：0

Example 3：

 Input ：left = 1, right = 2147483647
 Output ：0

Tips ：

• 0 <= left <= right <= 231 - 1

Answer key

​ When I first saw it , I think it's a math problem , Just go and see what the rules are , Then I found a rule , Is that if left One shift to the right is less than right Words , Be sure to return 0.（ abbreviation Straddle and ）

	2^3	2^2	2^1	2^0
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
8	1	0	0	0
9	1	0	0	1

When 5 & 6 & 7 = 4 when ,4 Binary bit of 100

	2^3	2^2	2^1	2^0
4	0	1	0	0
8	1	0	0	0
9	1	0	0	1

4 & 8 = 0, It's easy to find out , If right（9） Greater than left（5） The left one （right > left << 1） when , Whatever's behind it , The return must be 0.

​ Another thing you may want to pay attention to is left When moving left, it will overflow （ It becomes negative ）, Lead to right Must be greater than left << 1, So we still need to judge left Is it greater than 2^30.

​ If it is greater than , It will overflow , however right Less than 2^31-1, Two conditions limit left and right The highest position is the same , There will be no Straddle and The situation of ;

​ If it is less than , It won't spill , Then judge whether there is Straddle and

class Solution {
    
    public int rangeBitwiseAnd(int left, int right) {
    
        if(left < (1 << 30) && right > (left << 1)){
    //left Is less than 1 << 30, And judge whether there is cross position and 
            return 0;
        }else{
    // No straddle and , Return directly to bitwise AND 
            int ans = left;
            while(left < right){
    
                ans &= ++left;
            }
            return ans;
        }
    }
}

displacement

	2^3	2^2	2^1	2^0
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
8	1	0	0	0
9	1	0	0	1

​ Or this form , We can find out , When 5 & 6 & 7 When , The return is 4, Is their public prefix , They are all in the same position , then 1 * 2^2 = 4. When we 5 & 6 & 7 & 8 & 9 When , The return is 0, Because the public prefix is in 5,6,7 There is 0.

​ All we ask for is their public prefix , How to solve the public prefix efficiently , That's the shift , By moving left , When moving left to the same value , Just stop , such as 5 Follow 7 Move two bits to the left to become 1,8 Follow 9 Move two bits to the left to become 1. Then we count how many bits have been shifted to the left , Move back to the right , You get the answer you want , such as 5 Follow 7 Shift left two bits to 1 after ,1 Move two bits to the right to become 4,.

class Solution {
    
    public int rangeBitwiseAnd(int left, int right) {
    
        int shift = 0;// Count how many bits have been moved 
        while(left < right){
    // Will move all the way to right == left perhaps right and left All for 0
            left >>= 1;
            right >>= 1;
            ++shift;
        }
        return left << shift;// Right shift recovery 
    }
}