1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Hint: Which bits are actually variable? $\endgroup$
    – Raphael
    Jan 14, 2018 at 14:17
  • $\begingroup$ 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. $\endgroup$ Jan 14, 2018 at 14:27
  • 1
    $\begingroup$ 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). $\endgroup$
    – Raphael
    Jan 14, 2018 at 14:46
  • $\begingroup$ @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. $\endgroup$ Jan 14, 2018 at 15:04

1 Answer 1

1
$\begingroup$

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.
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Jan 14, 2018 at 17:20
  • $\begingroup$ 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$). $\endgroup$ Jan 14, 2018 at 17:22
  • $\begingroup$ Ok, now it is clear to me, thanks again. $\endgroup$ Jan 14, 2018 at 17:27
  • $\begingroup$ @YuvalFilmus Can you explain the b(j) part.Like what it is and how it is constructed? $\endgroup$
    – Sathyaram
    Jan 14, 2018 at 19:27
  • $\begingroup$ It's bitwise manipulation. It's probably easier to understand it on your own than me explaining it. Try a few examples. $\endgroup$ Jan 14, 2018 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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