Produce solutions of k & x = k in range (0,n)

Question

How to efficiently generate all numbers within 0,1,2...n.
(large n).
Such that for a fixed x and varying k (0 <= k < n), k & x = k.
It is easily found out that all the bits with value 1 in k is also 1 in x.
But I have trouble computing all of them.
I used DP to find all the subset sums of set bit in x,to arrive at all the possible solutions.

But this method proves inefficient over multiple such cases requesting for a different x.

Do I have to consider each and every bit which needs to be changed to get all the possibilities?Any other efficient way? Also I certainly dont want to check with all of n.

Answer 1

There is a neat way to do that

for(int i = x ;; i = x & (i - 1)){
     print i;
     if(i == 0)
        break;
}

Notice the condition i = x & (i - 1) make sure i always decreasing and only contains bits in x

See running Java code in here

In case x > n, so i should start with i = min(x, n - 1) & x

Answer 2

First note that the 0-bits in x denote the bits that must be 0 in k, while the 1-bits in x can be either 0 or 1 in k. The algorithm should thus iterate over all possible bit combinations in k for where x has a 1 bit and the resulting number (k) is not greater than n.

These combinations can best be produced by using something like a Grey code sequence, since one can then step from one bit pattern to the next in constant time.

Example:

x = 0b011010 (26)
n = 0b010000 (16)

The values to generate for k are (in order of Grey code sequence):

    0b000000 ( =  0)
    0b000010 ( =  2)
    0b001010 ( = 10)
    0b001000 ( =  8)
    0b011000 ( = 24) too large: exclude
    0b011010 ( = 26) too large: exclude
    0b010010 ( = 18) too large: exclude
    0b010000 ( = 16)

Because of using a Grey code scheme, only one bit changes from one combination to the next. This means that numbers are not generated in order and some can be too large (> n). This downside is worth it still, as generating them in order would involve more bit changes per step.

Here is a snippet that implements this idea in JavaScript:

function get_nums(n, x) {
    // Solution array. Add zero as it is always a solution (assuming non-negative n)
    let result = [0], 
        k = 0,
        arr = [];  // Helper to follow Grey code sequence
    for (let i = 1; i <= n && i <= x; i <<= 1) { // Shift bit to the left
        if (x & i) { // This bit is set to 1 in x
            arr.push(i);
            k += i; // Set this bit in k
            if (k <= n) result.push(k); // Add k to solution array
            // Produce other matches following Grey code sequence
            for (let j = arr.length-2; j >= 0; j--) {
                arr.push(-arr[j]);
                k -= arr[j]; // Toggle a bit in k
                if (k <= n) result.push(k);
            }
        }
    }
    return result;
}

console.log(get_nums(16, 26));

Note that the output is not ordered (because of the Grey code sequence used). If you need them ordered, apply some radix sort (or hashing).

In JavaScript it is quite easy to implement such a radix sort, given the values are unique. But in other languages you could implement a more explicit, simplified radix sort. Here is the JavaScript function for it:

function radix_sort_uniques(arr) {
    let result = {};
    // Add a property to the object for each value in the array
    for (let i of arr) result[i] = true;
    // Get those properties and convert them back to numeric data type (via map)
    // JavaScript will produce them in ascending order:
    return Object.keys(result).map(Number);
}

console.log(radix_sort_uniques([0, 2, 10, 8, 16]));

Complexity:

The outer loop iterates once per bit position in n, i.e. log(n) times, while the inner loop approximately doubles each time its number of iterations. So in the worst case (when x is 0 and the inner loop always executes) we get a total number of innermost operations in the order of 2^log(n) times, giving a O(n) time complexity.

As x is fixed, the complexity should be expressed in x too. Let's say x has b 1-bits, then the time complexity is O(b+2^b).

Answer 3

Imagine, that we have x in binary representation, like this:

x = 00001010110

In this case all k such that k & x = k should be in form

x = 00001010110
k = 0000?0?0??0

where ? is either 0 or 1. So we have to obtain all indexes 1 in x ([1, 2, 4, 6] in the example above) and generate all combinations (16 in the example) of 0 and 1s at the corresponding indexes:

C# implementation:

private static IEnumerable<int> MySolution(int x) {
  int[] indexes = Enumerable
    .Range(0, 32)
    .Where(i => (x >> i) % 2 != 0)
    .ToArray();

  for (int value = 0; value < 1 << indexes.Length; ++value) 
    yield return indexes
      .Select((v, i) => ((value >> i) % 2) * (1 << v))
      .Sum();
}

Test:

Console.WriteLine(String.Join(", ", MySolution(5)));

Outcome (please, notice that the solutions are sorted out):

0, 1, 4, 5

If you want to restrict solutions generated, you can modify the loop:

private static IEnumerable<int> MySolution(int x, int n = -1) {
  int[] indexes = Enumerable
    .Range(0, 32)
    .Where(i => (x >> i) % 2 != 0)
    .ToArray();

  for (int value = 0; value < 1 << indexes.Length; ++value) {
    int result = indexes
      .Select((v, i) => ((value >> i) % 2) * (1 << v))
      .Sum();

    if (n < 0 || result <= n)  
      yield return;
    else
      break; 
  }
}