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

Question

How to efficiently generate all numbers within 0,1,2...n .
(large n ).
Thus, for fixed x and varying k (0 <= k < n) , k & x = k .
It is easy to see that all bits with a value of 1 in k also 1 in x .
But I can’t figure them out.
I used DP to find all the sums of a subset of the set bits in x to get all possible solutions.

But this method is ineffective in several such cases, requesting another x .

Do I have to consider every bit that needs to be changed in order to get all the features? Any other effective way? Also I do not want to check all n .

Answer 1

There is a clear way to do this.

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

Pay attention to the condition i = x & (i - 1) make sure that i always decreases and contains only bits in x

See running java code in here

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

Answer 2

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

These combinations are best created using something like Gray code , because then you can move from one bit pattern to the next in constant time.

Example:

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

The values ​​generated for k (in the order of the sulfur 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) 

Due to the use of the Gray code scheme, only one bit changes from one combination to the next. This means that numbers are not generated in order, and some may be too large (> n). This drawback is worth whatever it does, since generating them in order would require more bit-by-bit changes.

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 (due to the Gray code sequence used). If you need to order them, apply some sort of radix sorting (or hashing).

JavaScript is pretty simple to implement such a radix sort, given that 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 is repeated once per position bit in n, i.e. log (n) times, while the inner loop approximately doubles each time with its number of iterations. Therefore, in the worst case (when x is 0, and the inner loop is always executed), we get the total number of innermost operations in the order of 2 ^{log (n)} times, giving time O (n) complexity.

Since x is fixed, complexity must also be expressed in x. Let them say that x has b 1 bits, then the time complexity is O (b + 2 ^b ).

Answer 3

Imagine we have x in binary representation, for example:

 x = 00001010110 

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

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

where ? - either 0 or 1 . Therefore, we must get all indices 1 in x ( [1, 2, 4, 6] in the above example) and generate all combinations ( 16 in the example) 0 and 1 in the corresponding indices:

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))); 

Result (please note that the solutions are parsed):

 0, 1, 4, 5 

If you want to limit the created solutions, you can change 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; } }