Java 8 ms one-liner, O(1), no loop, no log


  • 13
    public int rangeBitwiseAnd(int m, int n) {
        return m == n ? m : m & ~((Integer.highestOneBit(m ^ n) << 1) - 1);
    }
    

    The idea here is pretty simple: when we go from m to n some higher part may remain the same. The lower part changes. If we take the highest bit that is different, then it must be true that it is 1 in n and 0 in m, simply because n is larger than m. That means that at some point it went from 0 to 1, and at that very point the lower digits must have all turned to zeroes, just like it happens in decimal when we go up to 1000 from 999. That means that all lower bits will be zero in the result. The differing bit will also be zero for obvious reasons. The higher part (if any) will remain as it is because it didn't change at all.

    Therefore, we take that differing bit (Integer.highestOneBit(m ^ n)) and then create a mask that fills the whole thing with 1 to the right, including that bit. We achieve that by shifting that bit left (we can do it because we know that n < Integer.MAX_VALUE), then we subtract 1 so that bit goes to zero and everything to the right turns into ones. Then we bit-reverse the mask and apply it either to m or to n, doesn't matter because the higher part is identical.

    Unfortunately, that doesn't quite work when m == n because then m ^ n will be zero and we'll end up zeroing the whole thing.

    But it doesn't end here. As noted by @gorokhovsky in a comment below, we don't even have to shift the mask at all, but then we'll have to apply it to m. We can do this because we know that the highest differing bit is zero in m, so it doesn't really matter whether it's zero or one in the mask. This leads to the following solution:

    public int rangeBitwiseAnd(int m, int n) {
        return m == n ? m : m & ~(Integer.highestOneBit(m ^ n) - 1);
    }
    

    Now, if you have a good understanding of two's complement, you should instantly recognize that ~(something - 1) is just something negated, which leads us to @gorokhovsky's solution, refactored into one-liner:

    public int rangeBitwiseAnd(int m, int n) {
        return m == n ? m : m & -Integer.highestOneBit(m ^ n);
    }
    

    In case anyone feels like using Integer.highestOneBit is cheating, here is it's code, from the standard Java library:

        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    

    Doesn't look that complicated, does it? (If you think it does, look at Integer.reverse or something.)

    What happens here is that we first OR bit pair-wise. If any bit was 1 to begin with or had 1 to the left, it will now be 1. Then we do the same thing with resulting pairs. Now every bit will be 1 if at least one of the following is true:

    • it was 1 to begin with;
    • its left neighbor was 1 (so it became 1 on the previous step);
    • its next left neighbor was 1 (because now we OR exactly with this next neighbor);
    • its next-next left neighbor was 1 (because now we OR exactly with this next neighbor and that neighbor was ORed with its neighbor on the previous step).

    So each ith bit will be 1 if at least of the bits i + 1, i + 2, i + 3 was 1. Note that the code uses signed shifting, but it doesn't really matter because if i is negative we'll fill everything with 1 anyway.

    By repeating this process we finally have a mask that fills everything with 1 from the highest bit and to the right. By shifting it and subtracting we get the highest bit. Speaking of which, looks like we can use this code directly to solve our problem, although it won't be a one-liner any more:

    public int rangeBitwiseAnd(int m, int n) {
        if (m == n) {
            return m;
        }
        int i = m ^ n;
        i |= (i >>> 1);
        i |= (i >>> 2);
        i |= (i >>> 4);
        i |= (i >>> 8);
        i |= (i >>> 16);
        return m & ~i;
    }

  • 1

    There is an implicit log when you do such OR operations.


  • 0

    @jedihy Naturally, I meant no floating-point log.


  • 0
    G

    I've done the same idea, but my version was easier a bit

         if(m==n) return m;
         return m & (-Integer.highestOneBit(m^n));
    

  • 0

    @gorokhovsky Oh my, I haven't realized at all that it doesn't matter whether the highest-differing bit is zero or one in the mask because it's zero anyway in m. That certainly simplifies the solution!


Log in to reply
 

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