Consider two integers a and b. The objective is to find all the integers c < a such that c & b = c. Apart from the naive O(a) solution, where we check all the integers, is there an efficient way of doing this.
Ex:
a = 9 , b = 12
c = {0,4,8} [ 0 & 12 = 0, 4 & 12 = 4, 8 & 12 = 8 ]
PS: a is expected to be smaller in degree than b, if it can help in some way.
For each bit, if that bit in $b$ is $0$ you must have that bit in $c$ be zero. If that bit in $b$ is $1$, that bit in $c$ can be either $0$ or $1$. If $b \gt a$ you can ignore any bits that are too bit to fit in $a$. You can find the bits of interest in something like $\log a$ time as there are $\log_2 a$ of them. Assuming half the bits of interest are $1$s the final list will be about $\sqrt{\min (a,b)}$ in size, while if $b$ has all $1$s in the length of $a$ your list will be all the numbers less than $a$. This gives a worst case time of $O(a)$ and an expected time of $O(\sqrt a)$