algorithm - k 的下一个字典排列，约束为 'greater than or equal to number g'

Question

我有一个位掩码 k，例如 01100011。我有一个索引 j，表示我要保存的最高有效位，例如在 01100011 ==> j=2 中取 011。我想用一点操作公式找到大于 g = ((k >>(k.len-1-j))+1)<<(k.len-1-j) 的最小字典排列，其中 k.len 是位掩码的长度(示例中为 8)。

例子，

k = 01100011
for j = 2 ==> g = 10000000 because k>>(k.len-1-j) is 011
solution is 10000111
--------------------------------
k = 01100011
for j = 4 ==> g = 01101000 because k>>(k.len-1-j) is 01100
solution is 01101001
--------------------------------
k = 01100011
for j = 7 ==> g = 01100100 because k>>(k.len-1-j) is 01100011
solution is 01100101

我想知道这个公式，如果可能的话，我想知道这个公式是如何构建的。

我在 http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation 中找到数字 k 的下一个字典顺序排列的公式，我正在寻找类似的东西。

如果只使用位运算符而不使用编译器/体系结构相关指令(我使用的是 java)会很好，但不是必需的。

Answer 1

这是一个基于此问题的答案从 C 改编为 Java 的解决方案:Calculate the smallest integer with k bits set that is greater than another integer x?

public static int smallestIntGreaterOrEqualToXwithKBitsSet(int x, int k)
{
    while (Integer.bitCount(x) > k)
    {
        // Substitute the least-significant group of bits
        // with single bit to the left of them
        x |= x-1;
        ++x;
    }

    for (int i = k - Integer.bitCount(x); i != 0; --i)
    {
        // Set the lowest non-set bit
        x |= x+1;
    }
    return x;
}

我通过删除 x 的第一个增量将逻辑从“大于”更改为“大于或等于”。

要使用它来解决您的问题，您可以将 g 的值作为第一个参数传递，将 k 的位数作为第二个参数传递:

public static int nextPerm(int k, int j, int len)
{
    int g = ((k >>(len-1-j))+1)<<(len-1-j);
    return smallestIntGreaterOrEqualToXwithKBitsSet(g, Integer.bitCount(k));
}

测试:

System.out.println(Integer.toBinaryString(nextPerm(0b01100011, 2, 8)));
System.out.println(Integer.toBinaryString(nextPerm(0b01100011, 4, 8)));
System.out.println(Integer.toBinaryString(nextPerm(0b01100011, 7, 8)));

输出:

10000111
1101001
1100101