How to produce all the numbers in a range [0,1,...,n] for which if 0<=k<=n, then for a positive integer x, the expression: k & x = k?

I am trying to figure out an efficient way to produce all the numbers in a given range for which, their bitwise AND with a positive integer (say x) gives the same number; that means k & x = k.

Is there a better way to do it so that I do not need to go through all the numbers from 0 to n and check for it?

• Hint: Which bits are actually variable? Jan 14, 2018 at 14:17
• Those which are set in k must also be set in x, rest can either be set or reset. I need to know if there can be a procedure to determine all of them in given range. Jan 14, 2018 at 14:27
• There you go; iterate over free bits, not the range. Go from LSB to MSB and stop if you exceed n (assuming you start with all free bits being zero). Jan 14, 2018 at 14:46
• @Raphael Thanks, I got your point. This may be a very trivial thing but I am having trouble to do that. Can you please write a more explainatory answer of how to actually perform that iteration. That would be a great help. Jan 14, 2018 at 15:04

This answer shows how to find all values of $x$ satisfying the equation for fixed $k$. The OP asked for all values of $k$ satisfying the equation for fixed $x$, but the same methods work for both problems.

First of all, we have $k \& x = k$ if $x_i = 1$ whenever $k_i = 1$. If we think of $k,x$ as sets whose elements are the 1 bits, then the equation becomes $k \cap x = k$, which is equivalent to $k \subseteq x$, and so if $i \in k$ (i.e., $k_i=1$) then $i \in x$ (i.e., $x_i=1$).

In order to generate all solutions $x$ in the range $0,\ldots,n$, it suffices to generate all solutions in increasing order; we can stop once reaching a solution which is larger than $n$. How do all solutions look like? Let the 0 bits of $k$ be $i_0 < i_1 < \cdots < i_\ell$. Then the solutions are $$k + \sum_{j=0}^\ell b_j 2^{i_j},$$ where $b_j \in \{0,1\}$; we can replace addition equivalently with bitwise OR. Moreover, if we think of $b_\ell\ldots b_0$ as a binary number, then the mapping from $b_\ell \ldots b_0$ to $k + \sum_j b_j 2^{i_j}$ is monotone: as we go over all values of $b_\ell \ldots b_0$ in increasing order, the values of $k + \sum_j b_j 2^{i_j}$ appear in increasing order. This leads to the following algorithm:

1. Let $b \gets 0$.
2. Compute $x = k + \sum_j b_j 2^{i_j}$, where $b_j$ is the $j$th bit of $b$.
3. If $x \leq n$, output $x$, increase $b$ by 1, and go back to 2. Otherwise, halt.
• Thanks a lot. I think your solution gives all values of x for a fixed k, but I actually have asked for all the values of k for a fixed value of x, (sorry if the language of question is vague). Can I compute it by the similar process with some modifications? Jan 14, 2018 at 17:20
• Yes, a similar idea should work for the other question as well, using the condition "$x_i = 0$ implies $k_i = 0$", which is equivalent to the condition used in the answer ($k_i = 1$ implies $x_i = 1$). Jan 14, 2018 at 17:22
• Ok, now it is clear to me, thanks again. Jan 14, 2018 at 17:27
• @YuvalFilmus Can you explain the b(j) part.Like what it is and how it is constructed? Jan 14, 2018 at 19:27
• It's bitwise manipulation. It's probably easier to understand it on your own than me explaining it. Try a few examples. Jan 14, 2018 at 19:30