c - 查找仅具有单个设置位且总和等于给定数字的数字的最佳算法是什么？

Question

假设我有一个号码0b10110010,

我想用总和等于上述数字的不同数字来解析它，所有解析的数字应该只设置一位。

 10000000  <-- num1
 + 100000  <-- num2
 +  10000  <-- num3
 +     10  <-- num4
----------
 10110010  <-- num1 + num2 + num3 + num4

最好的算法是什么？

Answer 1

基本上，是这样的:

int i;
for (i = 1; i <= num && i != 0; i <<= 1) {
    if ((i & num) == 0)
        continue;

    /* i is part of the decomposition, do something with it */
    printf("0x%4x\n", i);
}

这会遍历所有可能的数字并设置一位并忽略那些未设置 num 中相应位的数字。复杂度为 O(log num)。还有一个 O(k) 的解决方案，其中 k 是 num 中 1 的位数，算法是这样的:

int i, n = num;
while (n != 0) {
    i = ((n - 1) & ~n) + 1;
    /* i is part of the decomposition */
    printf("%4x\n", i);
    n &= n - 1;
}

考虑下图以了解其工作原理:

n             101101101010100000000
n - 1         101101101010011111111
~n            010010010101011111111
~n & (n - 1)  000000000000011111111
i             000000000000100000000
n & (n - 1)   101101101010000000000

在最后一行中，也可以使用 n &= ~i 但这会强制编译器保留 i 变量的时间比需要的时间长一点，这可能速度不太理想。有疑问时作为基准。

我个人的猜测是，如果 num 是稀疏的，即 num 中只设置了很少的位，则第二种方法会更快。 由于其操作次数较少，您如果已知 num 不是稀疏的，则应使用第一种方法。