2 line Solution with detailed explanation


  • 63
    C
     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;


  • 0
    This post is deleted!

  • 0
    X

    Thanks for the clear explanation.


  • 5
    Q

    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

  • 0
    S

    Hard to understand how it is working


  • 0
    K

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


Log in to reply
 

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