# 2 line Solution with detailed explanation

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

The key point: reduce n by removing the rightest '1' bit until n<=m;

(1)if n>m,suppose m = yyyzzz, n = xxx100, because m is less than n, m can be equal to three cases:

``````(a) xxx011 (if yyy==xxx)
(b) less than xxx011 (if yyy==xxx)
(c) yyyzzz (if yyy<xxx)
``````

for case (a), and (b), xxx011 will always be ANDed to the result, which results in xxx011 & xxx100 = uuu000(uuu == yyy&xxx == xxx);

for case (c), xxx000/xxx011 will always be ANDed to the result, which results in yyyzzz & xxx000 & xxx011 & xxx100 = uuu000 (uuu <= yyy & xxx)

=> for any case, you will notice that: rangBitWiseAnd(vvvzzz,xxx100) == uuu000 == rangBitWiseAnd(vvvzzz,xxx000), (not matter what the value of"uuu" will be, the last three digits will be all zero)

=> This is why the rightest '1' bit can be removed by : n = n & (n-1);

(2)when n==m, obviously n is the result.

(3)when n < m, suppose we reduce n from rangBitWiseAnd(yyyzzz,xxx100) to rangBitWiseAnd(yyyzzz,xxx000);

i) xxx100 >yyyzzz => xxx >= yyy;

ii) xxx000 < yyyzzz => xxx <= yyy;

=> xxx == yyy;

=> rangBitWiseAnd(yyyzzz,xxx000) == rangeBitWiseAnd(xxxzzz,xxx000);

=>result is xxx000, which is also n;

• This post is deleted!

• Thanks for the clear explanation.

• Really nice solution!!

May I summarize the idea/intuition as follow?

``````// given m < n
m := common bits + 0 + remaining bits of m
n := common bits + 1 + remaining bits of n.
// thus repeatedly clear last bit of n, until n <= m``````

• Hard to understand how it is working

• If someone can please explain this solution in an
easy way, will be greatly appreciated!

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