使用增量和乘以 2 生成任意数字

Question

我正在寻找在循环中工作的算法，它将生成任何自然数 n，仅使用递增和乘以 2 微不足道的方式是已知的（递增数 n 次），但我正在寻找快一点的东西。老实说，我什至不知道该如何开始。

Answer 1

基本上，您要做的是从 MSB 开始向右移动数字的位。

比如你的数字是70，那么它的二进制就是0b1000110。所以，你想要 "shift in" 位 1, 0, 0, 0, 1, 1, 0.

要移入零，只需将数字加倍即可。要移入 1，请将数字加倍，然后递增。

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;
}

Generate any number using Incrementation and mult by 2