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.


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.

  • $\begingroup$ @user8734617 yeah, i will update it :) $\endgroup$ – yobro97 Jan 10 '18 at 21:11
  • $\begingroup$ 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?) $\endgroup$ – user491874 Jan 10 '18 at 21:22
  • $\begingroup$ 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. $\endgroup$ – hardmath Jan 10 '18 at 21:23
  • $\begingroup$ @hardmath i meant log(a) < log(b) to the base 10. $\endgroup$ – yobro97 Jan 11 '18 at 3:18
  • $\begingroup$ @hardmath added a simple example. $\endgroup$ – 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)$

  • $\begingroup$ 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. $\endgroup$ – yobro97 Jan 11 '18 at 3:24
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 11 '18 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.