GESP 八级 · GESP 202412 C++ 八级 第 9 题

在下面的程序中，使用整数表示一种组合。整数二进制表示的某一位为 1，表示该位对应的数被选中，反之为 0 表示未选中。例如，从 0 - 5 这 6 个数中选出 3 个，则 0b111000 代表选中 3, 4, 5 三个数，0b011001 代表选中 0, 3, 4 三个数。zuhe_next 函数按组合对应的整数由大到小的顺序，求出组合 c 的下一个组合。横线处可以填入的是（ ）。

int intlow2(int c) {
    return _______;  // 在此处填入选项
}

int zuhe_next_incur(int c, int n, int l) {
    if (n == 1) return c;
    if ((c & (1 << l)) == 0) {
        int d = intlow2(c);
        c = (c & ~d);
        c = (c | (d >> 1));
    } else {
        c = (c & ~(1 << l));
        c = zuhe_next_incur(c, n - 1, l + 1);
        int d = intlow2(c);
        c = (c | (d >> 1));
    }
    return c;
}

// 从n个数中选m个，当前组合为c
int zuhe_next(int c, int n, int m) {
    return zuhe_next_incur(c, n, 0);
}

看到组合枚举→先找最低0位

误选C：认为返回最低1位；忽略+1后需右移降位，否则d多一位破坏清零逻辑。

考点：二进制组合枚举｜位运算技巧｜组合数学

解析

组合枚举本质是“找到最低0位，翻成1，并重置更高位的1”。intlow2 必须返回最低0位对应的值，这样后续 c = (c & ~d) | (d >> 1) 才能把 d 位清零、d‑1 位置1。