[Leetcode] 201. Bitwise AND of Numbers Range

201. 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.
Credits:Special thanks to @amrsaqr for adding this problem and creating all test cases.

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if(m == n) return m;
        return (int)restBits(n,m,30);
    }
    
    private long restBits(long upper,long lower,int idx){
        if(idx < 0) return 0;
        if(upper == lower) return lower;
        long h1 = (upper >>> idx) & 1;
        long h2 = (lower >>> idx) & 1;
        long r1 = upper & (0xFFFFFFFF>>>(31-idx+1));
        long r2 = lower & (0xFFFFFFFF>>>(31-idx+1));
        if((h1 & h2) == 1){
            return (1<<idx) + restBits(r1,r2,idx-1);
        }
        else if((h1 ^ h2) == 1){
            return 0;
        }
        else{
            return restBits(r1,r2,idx-1);
        }
    }
}