使用增量和多值2生成任意数字

Question

我正在寻找在循环中工作的算法，它将生成任意自然数n，只使用2好的增量和乘法，平凡的方式是已知的(增量数n倍)，但是我正在寻找更快的方法。老实说我甚至不知道该怎么开始这件事。

Answer 1

基本上，你想要做的是从右边移动数字的位数，从MSB开始。

例如，如果您的数字为70，则其二进制数为0b1000110。因此，您希望“在”位中“移动”1、0、0、0、1、1、0。

要在零中移动，只需将数字加倍。要移动一个数字，你要加倍，然后增加它。

if (bit_to_be_shifted_in != 0)
    x = (x * 2) + 1;
else
    x = x * 2;

因此，如果给您一个从MSB到LSB (即从左到右)的位数组，则C代码如下所示：

x = 0;
for (i = 0; i < number_of_bits; i++)
{
    if (bits[i] != 0)
        x = x * 2 + 1;
    else
        x = x * 2;
}

Answer 2

这样做的一种方法是倒退。如果是奇数，减去一个。如果是偶数，除以2。

while(n > 0) {
   n & 1 ? n &= ~1 : n >>= 1;
}