下一个更高的数字，具有相同数量的设置位和固定的一些位

Question

我正在尝试找到一种方法，给定需要设置的位的数量，以及一些应该保持固定的位索引，生成具有相同数量的设置位的下一个更高的数字，具有所有固定位。这与https://www.chessprogramming.org/Traversing_Subsets_of_a_Set#Snoobing_the_Universe

密切相关

不同之处在于我想保持某些位不变，并且我正在尝试尽可能高效地执行此操作/一些接近 snoob 函数的东西，给定一个数字和条件，bithacks 它的方式进入下一个（例如，我试图避免遍历所有较小的子集并查看哪些包含所需的位）。

例如，如果我有数字 {1,2,...,20} 的宇宙，我想给定一个位为 {2,5,6} 的数字，生成最小的设置了位 {2,5,6} 的 6 个设置位的数字，然后是之后的数字等

Answer 1

解决方案 1（基于“窥探宇宙”）

一种解决方案是定义一个对应于“固定位”的值和一个对应于“可变位”的值。

例如对于位 {2、5、6}，“固定位”值将为 0x64（假设位从 0 开始计数）。

“可变位”用具有剩余位数的最小值初始化。例如。如果我们一共想要6位，有3个固定位，剩下的位数是6-3=3，所以“可变位”起始值为0x7.

现在，通过将“可变位”插入“固定位”为 0 的位置来“混合”两个位集来计算结果值（参见下面的函数 blend()）。

为了获得下一个值，使用链接的“Snoobing the Universe”函数（下面的 snoob()）修改“可变位”，然后通过“混合”固定位和可变位再次获得结果.

综上，解决方法如下（以打印前10个数为例）：

#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=0x%04llx\n", i, value, value);
        varBits = snoob(varBits);  // Get next value for variable bits
    }
}

解决方案 2（基于“Snoobing any Sets”）

另一个基于链接的“Snoobing any Sets”（函数snoobSubset()below）的解决方案是将“variale set”定义为不固定的位，然后将“可变位”初始化为n 这些位中的最低位（参见下面的函数 getLsbOnes()）。在示例中，n=3.

解决方法如下：

#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=0x%04llx\n", i, value, value);
        varBits = snoobSubset(varBits, varSet);
    }
}

示例输出

两种解决方案的输出应为：

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

下一个更高的数字，具有相同数量的设置位和固定的一些位

Next higher number with same number of set bits and some bits fixed

c++

bit-manipulation

combinatorics

discrete-mathematics

解决方案 1（基于“窥探宇宙”）

解决方案 2（基于“Snoobing any Sets”）

示例输出