I'm trying to find a way to, given a number of bits that need to be set, and a few indexes of bits that should remain fixed, generate the next higher number with the same number of set bits, that has all the fixed bits in place. This is closely related to https://www.chessprogramming.org/Traversing_Subsets_of_a_Set#Snoobing_the_Universe

The difference is that I want to keep some of the bits unchanged, and I'm trying to do this as efficiently as possible / something close to the snoob function, that given a number and the conditions, bithacks its way into the next one (So I'm trying to avoid iterating through all the smaller subsets and seeing which ones contain the required bits, for example).

For example, if I have the universe of numbers {1,2,...,20}, I'd like to, given a number with bits {2,5,6} set, generate the smallest number with 6 set bits that has bit {2,5,6} set, and then the number after that etc

CodePudding user response：

Solution 1 (based on "Snoobing the Universe")

One solution is to define a value corresponding to the "fixed bits" and one corresponding to the "variable bits".

E.g. for bits {2, 5, 6}, the "fixed bits" value would be 0x64 (assuming bits are counted starting from 0).

The "variable bits" is initialized with the smallest value having the remaining number of bits. E.g. if we want a total of 6 bits and have 3 fixed bits, the remaining number of bits is 6-3=3, so the "variable bits" starting value is 0x7.

Now the resulting value is calculated by "blending" the two bit sets by inserting the "variable bits" into the places where the "fixed bits" are 0 (see the function blend() below).

To get the next value, the "variable bits" are modified using the linked "Snoobing the Universe" function (snoob() below) and the result is again obtained by "blending" the fixed and variable bits.

All in all, a solution is as follows (prints the first 10 numbers as an example):

#include<stdio.h>
#include<stdint.h>

uint64_t snoob (uint64_t x) {
   uint64_t smallest, ripple, ones;
   smallest = x & -x;
   ripple = x   smallest;
   ones = x ^ ripple;
   ones = (ones >> 2) / smallest;
   return ripple | ones;
}

uint64_t blend(uint64_t fixed, uint64_t var)
{
    uint64_t result = fixed;
    uint64_t maskResult = 1;
    while(var != 0)
    {
        if((result & maskResult) == 0)
        {
            if((var & 1) != 0)
            {
                result |= maskResult;
            }
            var >>= 1;
        }
        maskResult <<= 1;
    }
    return result;
}

int main(void)
{
    const uint64_t fixedBits = 0x64;  // Bits 2, 5, 6 must be set
    const int additionalBits = 3;
    uint64_t varBits = ((uint64_t)1 << additionalBits) - 1;
    uint64_t value;
    for(unsigned i = 0; i < 10; i  )
    {
        value = blend(fixedBits, varBits);
        printf("%u: decimal=%llu hex=0xllx\n", i, value, value);
        varBits = snoob(varBits);  // Get next value for variable bits
    }
}

Solution 2 (based on "Snoobing any Sets")

Another solution based on the linked "Snoobing any Sets" (function snoobSubset()below) is to define the "variale set" as the bits which are not fixed and then initialize the "variable bits" as the n least significant of these bits (see function getLsbOnes() below). In the example case, n=3.

This solution is as follows:

#include<stdio.h>
#include<stdint.h>

uint64_t getLsbOnes(uint64_t value, unsigned count)
{
    uint64_t mask = 1;
    while(mask != 0)
    {
        if(count > 0)
        {
            if((mask & value) != 0)
            {
                count--;
            }
        }
        else
        {
            value &= ~mask;
        }
        mask <<= 1;
    }
    return value;
}

// get next greater subset of set with same number of one bits
uint64_t snoobSubset (uint64_t sub, uint64_t set) {
   uint64_t tmp = sub-1;
   uint64_t rip = set & (tmp   (sub & (0-sub)) - set);
   for(sub = (tmp & sub) ^ rip; sub &= sub-1; rip ^= tmp, set ^= tmp)
       tmp = set & (0-set);
   return rip;
}

int main(void)
{
    const uint64_t fixedBits = 0x64;
    const int additionalBits = 3;
    const uint64_t varSet = ~fixedBits;
    uint64_t varBits = getLsbOnes(varSet, additionalBits);
    uint64_t value;
    for(unsigned i = 0; i < 10; i  )
    {
        value = fixedBits | varBits;
        printf("%u: decimal=%llu hex=0xllx\n", i, value, value);
        varBits = snoobSubset(varBits, varSet);
    }
}

Example output

The output for both solutions should be:

0: decimal=111 hex=0x006f
1: decimal=119 hex=0x0077
2: decimal=125 hex=0x007d
3: decimal=126 hex=0x007e
4: decimal=231 hex=0x00e7
5: decimal=237 hex=0x00ed
6: decimal=238 hex=0x00ee
7: decimal=245 hex=0x00f5
8: decimal=246 hex=0x00f6
9: decimal=252 hex=0x00fc