What a humbling experience. Picked up at random a challenge at LeetCode (https://leetcode.com/problems/bitwise-and-of-numbers-range/)
The requirements are quite brief and one can easily determine what is required:
“Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4”.
I got a piece of paper and jotted down the following:
5 = 1 0 1
6 = 1 1 0
& = 1 0 0
7 = 1 1 1
& = 1 0 0
The last number in binary represents number 4 in decimal.
I came up with the following test code written in Java using the Eclipse IDE:
public static void main(String[] args) {
int bf, m, n, r, s, maxVal, T;
// **** initialize a random number generator ****
Random rand = new Random(System.currentTimeMillis());
// **** ****
maxVal = Integer.MAX_VALUE;
T = 100;
// **** ****
for (int t = 0; t < T; t++) {
// **** assign values to m and n ****
m = Math.abs(rand.nextInt(maxVal));
for (n = Math.abs(rand.nextInt(maxVal)); n < m; ) {
n = Math.abs(rand.nextInt(maxVal));
}
// **** override values ****
// m = 20000;
// n = Integer.MAX_VALUE;
//
// m = 5;
// n = 7;
//
// m = 1;
// n = 2;
//
// m = 7;
// n = 7;
//
// m = 12;
// n = 12;
//
// m = Integer.MAX_VALUE;
// n = Integer.MAX_VALUE;
System.out.println(“<<< m: ” + m + ” n: ” + n);
// **** perform computation ****
long start = System.nanoTime();
s = rangeBitwiseAndTwo(m, n);
long end = System.nanoTime();
long delta = end – start;
System.out.printf(“<<< s: 0x%08X time: %10d ns\n”, s, delta);
start = System.nanoTime();
r = rangeBitwiseAnd(m, n);
end = System.nanoTime();
delta = end – start;
System.out.printf(“<<< r: 0x%08X time: %10d ns\n”, r, delta);
start = System.nanoTime();
bf = bruteForce(m, n);
end = System.nanoTime();
delta = end – start;
System.out.printf(“<<< bf: 0x%08X time: %10d ns\n”, bf, delta);
// **** check if the values do NOT match ****
if ((s != r) || (r != bf)) {
System.out.println(“<<< VALUES DO NOT MATCH !!!”);
break;
}
System.out.println();
}
System.out.println(“<<< ALL DONE :o)”);
}
The first method is the best solution. Please ignore it for now. The second 
method call (rangeBitwiseAnd()) is part of my solution. The last method call (bruteForce()) is the brute force implementation. I used it to verify my solution while I was working on it.
Following is the output of a single pass:
<<< m: 509361521 n: 1926568703
<<< s: 0x00000000 time: 5774 ns
<<< r: 0x00000000 time: 21409705 ns
<<< bf: 0x00000000 time: 821333963 ns
My solution passed the 8,266 test cases. As you can see is faster that the brute force approach but not even close to the best solution.
The brute force static method follows:
static int bruteForce(int m, int n) {
// ***** special case(s) ****
if (m == n) {
return m;
}
// **** ****
int value = m;
for (int i = m; (i > 0) && (i <= n); i++) {
value &= i;
}
/* ****
*
*/
return value;
}
My solution follows:
static int rangeBitwiseAnd(int m, int n) {
// ***** special case(s) ****
if (m == n) {
return m;
}
// **** ****
long pow;
for (pow = 1; (pow = pow * 2) <= m; ){}
// **** set the value of end ****
int end = n;
if (pow < n) {
end = (int)pow;
}
// **** perform AND operation ****
int r = 0;
int i = 0;
for (i = r = m; i < end; i++) {
r &= i;
}
r &= i;
// **** ****
return r;
}
Following is the best method from the LeetCode web site:
static int rangeBitwiseAndTwo(int m, int n) {
// **** ****
if(m == 0) {
return 0;
}
// **** ****
int moveFactor = 1;
while(m != n){
m >>= 1;
n >>= 1;
moveFactor <<= 1;
}
// **** ****
return m * moveFactor;
}
After reading about it and experimenting with it I was able to appreciate the insight and performance. This challenge was a good learning experience.
If you have comments / questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa