Idea: recursively locate the leftmost positions where all numbers in range has 1.

Two observations:

- If m == 0, result must be 0
- If the largest power of 2 of m and n are not equal, return 0. Eg.,

m = 0 0 1 x x x x

n = 1 x x x x x x

Then there must exists a number p in the sequence where:

p = 1 0 0 0 0 0 0

Thus, result must be 0.

Recursively locate the leftmost 1, add the power of 2 to result, subtract this number from m and n, and continue to find the next 1.

Code:

class Solution {

public:

int largestK(int num ) {

int k = 0;

while (num > 1) {

num = num >>1;

k++;

}

return pow(2,k);

}

```
int rangeBitwiseAnd(int m, int n) {
if ( m == 0 ) return 0;
int k1 = largestK(m); int k2 = largestK(n);
if (k1 != k2 ) return 0;
int result = k1 + rangeBitwiseAnd(m-k1,n-k1);
return result;
}
```

};