什么是最好的算法,只用一个设置位找到数字,其总和等于给定的数字？

假设我有一个号码0b10110010,

我想用不同的数字解析它的总和等于上面的数字,所有解析的数字应该只有一个单位设置.

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

什么是最好的算法呢？

基本上,这样的事情:

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不稀疏,则应使用第一种方法.