How to find Bitwise AND of all numbers for a given range?

Question

How can I find Bitwise AND of all numbers for a given range say from A to B, including both?

I found a beautiful answer for finding XOR for such range. https://stackoverflow.com/a/10670524/2046703

How to do this to find AND?

Answer 1

The only bits that will be $1$ will be bits that are common to the upper bits of $A$ and $B$. Everything else will have at least one instance of a $0$ in that range. So just start from the high order bit downwards. Output the matching bits. As soon as you hit a disagreement between the binaries of $A$ and $B$ (which will be $0$ in $A$ and $1$ in $B$) output zeros until you get to the length of $B$.

Answer 2

One way of doing it:

long long and(long long a, long long b) {
    long long x = a^b;
    long long s = x>>1;

    while (s) {
        x = x|s;
        s >>= 1;
    }
    return a&b&~x;
}

First, the idea is exactly Ross'; starting from the highest bit, check if $\operatorname{bit}_k(a) = \operatorname{bit}_k(b)$ in which case the corresponding bit in the answer will be $\operatorname{bit}_k(a)$. If we hit an index where $\operatorname{bit}_k(a) \neq \operatorname{bit}_k(b)$, then all bits $k,k-1,k-2,...$ will be zero.

Then the value $a\&b$ is almost the answer, except the relevant lower bits need to be zeroed.

The variable $x$ will either be 0 (in which case the answer is zero) or the highest '1' bit of $x$ will be the first index at which $\operatorname{bit}_k(a) \neq \operatorname{bit}_k(b)$. Then $s$ computes the value $x | (x\gg 1) | (x\gg2) | \cdots $, which will have ones in bits $k,k-1,k-2,...$. Then $\sim x$ will have ones everywhere except for bits $k,k-1,k-2,...$.

Answer 3

Another solution is to find the common "left header" of m and n. Bitwise AND of this common left header definitely results in 1, while the remaining right part results in 0 since at least 1 bit in a number between m and n is 0. Below is the Python code:

def rangeBitwiseAnd(self, m, n):
    shift = 0
    #find the common left header (or, same prefix) of m and n
    while m != n:
        m >>= 1 #shift to right by 1 bit
        n >>= 1
        shift += 1
    #then shift back to left to form the final result
    #(the remaining bits are not the same, so definitely result in 0 after AND)
    return m << shift

Answer 4

For searching leetcode "Bitwise AND of Numbers Range" I reached here, use a long long or python integer doesn't have integer overflowing problem, while if you want to try to use C with regular 32bit signed integer, you've chosen the hard way

I got finally figured out a solution, wonderful for embedded board running environment, this uses the least storage and also runs fast (leetcode says Runtime: 33 ms):

int rangeBitwiseAnd(int m, int n) {
    int x = 0;
    while ((m|x) < n)
       x = (x<<1) | 1;

    return m & ~x;
}