0

f_k(n)产生小于 的所有整数的生成函数是什么2^k，按设置的位数排序，然后按值排序？

的预期输出k = 4：

f_4( 0) = b0000 =  0
--------------------
f_4( 1) = b0001 =  1
f_4( 2) = b0010 =  2
f_4( 3) = b0100 =  4
f_4( 4) = b1000 =  8
--------------------
f_4( 5) = b0011 =  3
f_4( 6) = b0101 =  5
f_4( 7) = b0110 =  6
f_4( 8) = b1001 =  9
f_4( 9) = b1010 = 10
f_4(10) = b1100 = 12
--------------------
f_4(11) = b0111 =  7
f_4(12) = b1011 = 11
f_4(13) = b1101 = 13
f_4(14) = b1110 = 14
--------------------
f_4(15) = b1111 = 15

我观察到二项式系数C(k,x)预测存在多少x位设置的整数：

C(4,0) = 1
C(4,1) = 4
C(4,2) = 6
C(4,3) = 4
C(4,4) = 1

我还找到了一种方法来生成所有带有位设置的整数x。

基于此，我想出了一个解决方案。

int f(int k, int n) {
    int x = 0;
    int c = binomial(k, x);
    while (n >= c) {
        n -= c;
        ++x;
        c = binomial(k, x);
    }

    int v = (1 << x) - 1;  // v is exactly x many one bits
    for (int i = 0; i != n; ++i) {
        // next integer with x bits set
        int t = (v | (v - 1)) + 1;
        v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
    }

    return v;
}

然而，我的解决方案让我觉得效率低下，尤其是考虑到while循环。我有直觉，对此有更优化的解决方案，包括位魔法。

查找函数的奖励积分返回列表中的下一个/上一个元素，给定前面/后面的元素。

4

1 回答 1

0

我找到了返回下一个元素的函数的有效解决方案：

int next(int n, int v) {
    if (v == 0)
        return 1;

    int x = bitCount(v);
    // next integer with x bits set
    int t = (v | (v - 1)) + 1;
    v = t | ((((t & -t) / (v & -v)) >> 1) - 1);

    int m = ((1 << x) - 1) << (n - x);
    if (v > m)
        v = (1 << (x + 1)) - 1;
    if (v > (1 << n) - 1)
        v = 0;
    return v;
}
于 2015-02-03T23:30:38.280 回答