Bit operation solution(JAVA)

• The idea is very simple:

1. last bit of (odd number & even number) is 0.
2. when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
3. Move m and n rigth a position.

Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.

``````public class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m == 0){
return 0;
}
int moveFactor = 1;
while(m != n){
m >>= 1;
n >>= 1;
moveFactor <<= 1;
}
return m * moveFactor;
}
}``````

• nice solution!

• Thank you, happy to hear that!

• Here is my solution , its not perfect , but also work.

``````public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int result=0;
for(int i=0;i<32;++i){
if( dist(m,n,i)&& check(m+1,i) && check(n+1,i)){
result|=(1<<i);
}
}
return result;
}
//check value at  special bit postition whether is 1
boolean check(int value,int position){
if((value%(1<<position))==0)
return ((value>>position)%2)==0;
return ((value>>position)%2)!=0;
}
boolean dist(int x,int y,int i){
return y-x < (1<<i);
}
``````

}

• you don't need to check

``````if (m == 0) {
return 0;
}``````

• yes, we get the same result no matter check or not check

• I have almost the same idea here.

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

}

• ``````def rangeBitwiseAnd2(self, m, n):
"""
By using Brian Kernighan's Algorithm
"""
while n > m:
n &= (n-1);
print n
return m & n;
``````

• So Brillant!

• Actually it works if m==0 even if you do not test it.

• Further improvement. Just return n is ok.

``````while n > m:
n &= (n-1);
return n;``````

• Thank you so much!

• Please explain to me, am I wrong? I think: BOTH recursive and iterative methods, do not consider, if m has an extra digit in binary, the answer is 0. This should help to ends the loop much faster.

For example: if m = 5, n = 8

• ``````here is the code:

int rangeBitwiseAnd(int m, int n) {
int tempm = m & ~(m-1);
int tempn = n & ~(n-1);
if (tempm & tempn == 0) return 0;

int moveFactor = 1;
while(m != n){
m >>= 1;
n >>= 1;
moveFactor <<= 1;
}
return m * moveFactor;
}``````

• Inspired by this post and @moonwon 's solution.

``````def rangeBitwiseAnd(self, m, n):
l = len(str(bin(m ^ n))) - 2
return m if m == n else m >> l << l``````

• In one word, this problem is asking us to find the common prefix of m and n 's binary code.

• this code does not pass:

253

234

try it

• though the result is same, it avoids unnecessary division loop when range starts from 0

• Both your solution and Brian Kernighan's Algorithm are cool! Thanks for sharing!

• My solution

``````    public int rangeBitwiseAnd(long m, long n) {
// because  n&(n-1)=0 if n is power 2
if (m == 0 || n == 0 || n / m > 1) return 0;
long result = 1;
while (m != n) {
m >>= 1;
n >>= 1;
result <<= 1;
}
return (int) (m*result);
}

``````

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