Bit operations

201. Bitwise AND of Numbers Range

0000000000
0000000001
0000000010
0000000011
0000000100
0000000101
0000000110
0000000111
0000001000
0000001001

Above giving the output of 0 to 9. We can have two basic observations:

1. if m==n, then m and n = m
2. if m!=n, then the rightmost bit of m and n will be 0. As 1 bit can only distinguish two numbers, if m!=n, then it means we have at least two numbers, then the rightmost will contain at least one 0 and one 1. Then rightmost of m and n must be 0

Base on 2, we can get rightmost as 0 and pop right the last bit of both m and n then do it again until m==n.

Here is the code.

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        res = 0
        while m!=n:
            res += 1
            m = m>>1
            n = n>>1
        return m<<res