Bit operation solution(JAVA)


  • 190

    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;
        }
    }

  • 0
    I

    nice solution!


  • 0

    Thank you, happy to hear that!


  • 0
    Z

    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);
    }
    

    }


  • 1
    Z

    you don't need to check

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

  • 0

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


  • 11
    H

    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;
    }
    

    }


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

  • 0
    S

    So Brillant!


  • 0
    S

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


  • 4
    C

    Further improvement. Just return n is ok.

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

  • 0

    Thank you so much!


  • -2
    A

    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


  • 0
    A
    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;
        }

  • 0

    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

  • 20
    M

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


  • 0
    O

    this code does not pass:

    253

    234

    try it


  • 1
    C

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


  • 0

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


  • 0
    Y

    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);
        }
    
    

Log in to reply
 

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