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**