No Loop! 1 Line of Bit Operations [Java]


  • 0
    J

    My solution relies on the bit patterns of consecutive integers.
    Consider the bit patterns from m = 17 to n = 27

    17 | 010001
    18 | 010010
    19 | 010011
    20 | 010100
    21 | 010101
    22 | 010110
    23 | 010111
    24 | 011000
    25 | 011001
    26 | 011010
    27 | 011011
    

    As you can see, the 1-bit flips every subsequent integer value, while the 2-bit bit flips every 2 consecutive integer values. All bit positions follow this pattern with the 4-bit place flipping every 4 integer values, 8-bit place flipping every 8, and so on. Since these bits flip every x consecutive integers, they will always be zeros if n and m have a difference greater than x.

    In other words, if (n - m >= 2^x), the lowest x+1 bits will be zero after ANDing all the integers in between. Using the n and m values from above: 27-17 = 10. Since 10 is greater than 8 (2^3), the lowest 4 bits will always be zero after ANDing the integers from [17,27].

    Once we know what bits will be zero-ed out during the ANDing of a range, we can simply AND n & m before setting all bits invalidated by the process above to 0.

    17 & 27:
      010001
      011011
    ----------
      010001
    

    Now we have to set the lowest x bits to 0. We do this in my function by ANDing this result with a bit mask that has the lowest x bits set to 0. In this case, we'd AND it with the integer value 11111111111111111111111111110000. The easiest way I found to get this mask was to get the highest one-bit in n-m, shift it up one place, and subtract 1. Finally, after all that, take the complement of this value to create the bitmask.

    m = 17; n = 27
    001010 // n - m = 10
    001000 // highest bit = 8
    010000 // shifted up 1 place (aka x2) = 16
    001111 // subtract 1
    [26 one bits]...110000 // take the complement 
    
    Final Bitmask :  11111111111111111111111111110000
    

    Our return value is the bitwise AND of n, m, and our bitmask.

    00000000000000000000000000010001  // m = 17
    00000000000000000000000000011011  // n = 27
    11111111111111111111111111110000  // bitmask
    ------&---------&---------&------
    00000000000000000000000000010000
    
    public class Solution {
        public int rangeBitwiseAnd(int m, int n) {
            if(m == n) return n;
            return m & n & ~((Integer.highestOneBit(n - m) * 2) - 1);
        }
    }
    

    Slightly more readable:

    public class Solution {
        public int rangeBitwiseAnd(int m, int n) {
            if(m == n) return n;
            int nmDiff = n - m;
            int validBits = ~((Integer.highestOneBit(nmDiff) * 2) - 1);
            return m & n & validBits;
        }
    }
    

    Another Solution for Generating the mask :

    public class Solution {
        public int rangeBitwiseAnd(int m, int n) {
            if(m == n) return n;
            return m & n & (Integer.MAX_VALUE << (32-Integer.numberOfLeadingZeros(n-m)));
        }
    }
    

Log in to reply
 

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