获取基于 (-2) 二进制位的算法

Question

我想知道为特定数字获取基于 (-2) 的二进制位的好算法。

那么让我来定义基于 (-2) 的二进制位。bits是1或0的二进制元素数组。此N 长度位A 表示的数字K 计算如下:

K = A[0] * (-2 ^ 0) + A[1] * (-2 ^ 1) + A[2] * (-2 ^ 2) + ... +  + A[N-1] * (-2 ^ (N-1))

例如，位 00011 表示数字 8 因为

1*(-2^4) + 1*(-2^3) + 0*(-2^2) + 0*(-2^1) + 0*(-2^0)

所以问题是当定义数字时，计算上面解释的最短位的好算法是什么。

Answer 1

Wikipedia展示了这个令人惊讶的方法:

unsigned int toNegaBinary(unsigned int value) // input in standard binary
{
    unsigned int Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010
    return (value + Schroeppel2) ^ Schroeppel2; // eXclusive OR
    // resulting unsigned int to be interpreted as string of elements ε {0,1} (bits)
}