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.


  • 4
    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


Log in to reply
 

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