# No Loop! 1 Line of Bit Operations [Java]

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

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