# How efficiently can the bitwise and operation of two numbers be done?

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.

• @user8734617 yeah, i will update it :) – yobro97 Jan 10 '18 at 21:11
• In the worst case you will still need to output all numbers $\lt a$, that is, if $b$ is all-ones, so you cannot escape the worst case to be $O(a)$. (BTW isn't it $O(a\log a)$ because you need to output every digit of every number?) – user491874 Jan 10 '18 at 21:22
• Probably a short example would help to illustrate your problem. In particular I'm not sure what $a$ is smaller "in drgree" than $b$ is intended to mean. – hardmath Jan 10 '18 at 21:23
• @hardmath i meant log(a) < log(b) to the base 10. – yobro97 Jan 11 '18 at 3:18
• @hardmath added a simple example. – yobro97 Jan 11 '18 at 3:30

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)$
• Thanks Ross. I was trying on similar lines, but I was wondering if some property or pattern can be generalized for the set of numbers c & b = c given b. It would be helpful if you could suggest any similar approaches. – yobro97 Jan 11 '18 at 3:24
• I described the pattern. Take the binary of $b$ and replace each $1$ with a star, meaning you can have either a $0$ or a $1$ in that bit. When you said "find all integers" it sounded to me like you wanted a list. The thing that takes all the time is making that list. If $a$ has a million bits, there will be something like $2^{500,000}$ numbers in the list. Coming up with the description is fast, but turning that into a list will take forever. – Ross Millikan Jan 11 '18 at 6:39