# [java/9ms] Inspired from BIT to find prefix, also explains the highly voted code.

• The method is to find the same prefix, that is, the biggest number (a)(b) <= m, in which (b) are all zeroes and the last digit of (a) is one, and then return it.

explanation: m and n has same prefix, then the result should be the prefix with trailing zeroes.

Suppose, m = a0b, n = a1c, and `a` is the same prefix followed by `the 1`, thus a10..0 <= n, will set all digits behind `the 1` to zero. Then we can use m to set `the 1` to zero. That's how the highly voted code does.

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

But here, I use a different way.

idx -= (idx & -idx). In this way, it will replace the last '1' to '0'.

For instance `[101010, 101101]`, we find the same `prefix 101xxx` and the range must contain `101100`, which will set the `last two` digits to zero after AND. Also, since we have `101010` to set the `third` digit to zero, then we should return the `prefix 101000`.

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

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