A Java solution different than finding the left most common bit

• My solution is to scan n from the first bit to last bit. A certain bit can only remain 1 if and only if you can meet the following situation:

for xx1xxxx, if xx0xxxx exists in the range [m, n], that 1 will always set to 0 at the Range AND. Only if xx01111 < m, we can make sure that the 1 can be remained.

Take a short example, [5, 7] which represented as 101, 110, 111. If we scan 111:

1. for the 1st one, we check if 011 is in range [5, 7], that is check(4 < 5). It is not in range [5, 7], so we remain the 1st one.
2. for the 2nd one, we check if 101 is in range [5, 7], that is check(5 < 5). It is in range [5, 7], so the 2nd one will disappear at the process of AND. Discard that one.
3. for the 3rd one, we check if 110 is in range [5, 7], that is check(6 < 6). It is in range [5, 7], discard that one.

``````public class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m == 0 || m == n) return m;

int res = 0;
for(int i = 31; i >= 0; i--) {
int x = 1 << i;
if((x & n) > 0 && ((n & ~x) | (x - 1)) < m)
res |= x;
}
return res;
}
}
``````

(n & ~x) is to set i th position 0, like dealing with 2nd one above, you have to construct 101 from 111. (n & ~x) | (x - 1) is to mask the 0xxx to 0111.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.