logo标签列表

计算给定数字的负二进制表示，但不使用循环。

algorithmbinarylanguage-agnosticbit-manipulationbase-conversion
7

你能提供令人信服的解释或数学证明，说明以下函数如何计算给定数字的负二进制表示法吗？

function quickNegabinary(number) {
  var mask = 0xAAAAAAAA;
  return ((number + mask) ^ mask).toString(2);
}
你有没有注意到维基百科页面上的版本（包括C语言版本）有实际的注释，至少部分地解释了它。你为什么要删除这些注释？这是个谜吗？ - GolezTrol
@GolezTrol 我觉得那里的评论并没有真正解释这是如何工作的。我正在寻找更详细的解释。 - Misha Moroshko
2个回答
16

负二进制表示法

负二进制表示法使用-2为基数。这意味着，与任何带有负基数的数字系统一样，每个其他位都有一个负值。

position:    ...     7    6    5    4    3    2    1    0  

binary:      ...   128   64   32   16    8    4    2    1  
negabinary:  ...  -128  +64  -32  +16   -8   +4   -2   +1

快速转换方法

快速的二进制→ 负二进制转化方法是将一个数字与0xAAAAAAAA或二进制...10101010进行加和之后再执行异或操作（这个掩码表示在负二进制表示法中具有负值的奇数位），例如对于值82：

binary:               01010010  =  82 (binary: 64 + 16 + 2)  
mask:                 10101010  = 170  
bin+mask              11111100  = 252  
(bin+mask) XOR mask:  01010110  =  82 (negabinary: 64 + 16 + 4 - 2)

如何工作：一位设置位

如果您以二进制记数法表示的数字中只有一个设置位，那么可以很容易地看出该方法是如何工作的。如果设置位处于偶数位置，则不会发生任何改变：

binary:               00000100  =   4 (binary: 4)  
mask:                 10101010  = 170  
bin+mask              10101110  = 174  
(bin+mask) XOR mask:  00000100  =   4 (negabinary: 4)

然而，如果所设位于奇数位置：

binary:               00001000  =   8 (binary: 8)  
mask:                 10101010  = 170  
bin+mask              10110010  = 178  
(bin+mask) XOR mask:  00011000  =   8 (negabinary: 16 - 8)

将设置的位向左移（通过添加1），然后与其原始值的负数（通过异或掩码）组合，以便将值为2n 的位替换为2n+1 - 2n。因此，您可以简单地将快速转换方法视为：“将每个2替换为4-2，每个8替换为16-8，每个32替换为64-32，依此类推”。

工作原理：多个设置的位

当转换具有几个设置位的数字时，可以将描述如上的具有一个设置位的数字的结果简单地相加。例如，将4和8的单个设置位示例（请参见上文）组合成12：

binary:               00001100  =  12 (binary: 8 + 4)  
mask:                 10101010  = 170  
bin+mask              10110110  = 182  
(bin+mask) XOR mask:  00011100  =  12 (negabinary: 16 - 8 + 4)

或者，对于一个更复杂的例子，在该例中某些数字被进位：

binary:               00111110  =  62 (binary: 32 + 16 + 8 + 4 + 2)  
mask:                 10101010  = 170  
bin+mask              11101000  = 232  
(bin+mask) XOR mask:  01000010  =  62 (negabinary: 64 - 2)

在描述二进制数的求和公式中，以下发生了变化：

32 + 16 + 8 + 4 + 2

其中32变成64-32，8变成16-8，2变成4-2，所以求和公式变成了：

64 - 32 + 16 + 16 - 8 + 4 + 4 - 2

其中两个16相加得到32，两个4相加得到8：

64 - 32 + 32 - 8 + 8 - 2

然后-32和+32互相抵消，-8和+8也互相抵消，所以得到：

64 - 2

或者，使用负二进制算术：

          +1    +1                 (carry)
     0  1 -1  0  0  0  0  0  =  32 (negabinary: 64 - 32)  
     0  0  0  1  0  0  0  0  =  16 (negabinary: 16)  
     0  0  0  1 -1  0  0  0  =   8 (negabinary: 16 - 8)  
     0  0  0  0  0  1  0  0  =   4 (negabinary: 4)  
  +  0  0  0  0  0  1 -1  0  =   2 (negabinary: 4 - 2)  
     ----------------------  
  =  0  1  0  0  0  0 -1  0  =  62 (negabinary: 64 - 2)

负数值

快速转换方法同样适用于采用二进制补码表示法的负数，例如：

binary:                       11011010  =    -38 (two's complement)  
mask:                         10101010  =    -86 (two's complement)  
bin+mask                      10000100  =   -124 (two's complement)  
(bin+mask) XOR mask:          00101110  =    -38 (negabinary: -32 - 8 + 4 - 2)  

binary:              11111111 11011010  =    -38 (two's complement)  
mask:                10101010 10101010  = -21846 (two's complement)  
bin+mask             10101010 10000100  = -21884 (two's complement)   
(bin+mask) XOR mask: 00000000 00101110  =    -38 (negabinary: -32 - 8 + 4 - 2)

范围和溢出

一个包含n位（其中n为偶数）的负二进制数字的范围是：

-2/3 × (2n-1) → 1/3 × (2n-1)

或者，对于常见的位深度：

 8-bit:            -170  ~             85  
16-bit:         -43,690  ~         21,845  
32-bit:  -2,863,311,530  ~  1,431,655,765  
64-bit:       -1.23e+19  ~       6.15e+18  
80-bit:       -8.06e+23  ~       4.03e+23

这个范围比具有相同位深度的有符号和无符号标准整数表示低，因此有符号和无符号整数都可能因为位深度相同而无法用负二进制表示。

虽然快速转换方法似乎在负值小于-1/6 × (2n-4)时会遇到溢出，但转换的结果仍然是正确的：

binary:                       11010011 =    -45 (two's complement)  
mask:                         10101010 =    -86 (two's complement)  
bin+mask             11111111 01111101 =   -131 (two's complement)  
overflow truncated:           01111101 =    125 (two's complement)  
(bin+mask) XOR mask:          11010111 =    -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1)

binary:              11111111 11010011 =    -45 (two's complement)  
mask:                10101010 10101010 = -21846 (two's complement)  
bin+mask             10101010 01111101 = -21891 (two's complement)  
(bin+mask) XOR mask: 00000000 11010111 =    -45 (negabinary: -128 + 64 + 16 + 4 - 2 + 1)

反转函数

负二进制数可以通过反向加法和掩码XOR转换回标准整数值，例如：

uint64_t negabinary(int64_t bin) {
    if (bin > 0x5555555555555555) throw std::overflow_error("value out of range");
    const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
    return (mask + bin) ^ mask;
}

int64_t revnegabin(uint64_t neg) {
    // const uint64_t even = 0x2AAAAAAAAAAAAAAA, odd = 0x5555555555555555;
    // if ((neg & even) > (neg & odd)) throw std::overflow_error("value out of range");
    const uint64_t mask = 0xAAAAAAAAAAAAAAAA;
    return (mask ^ neg) - mask;
}

(如果仅在由negabinary()函数创建的负二进制数上调用reverse函数，则不存在溢出的风险。但是，来自其他来源的64位负二进制数可能具有低于int64_t范围的值，因此需要进行溢出检查。)

哇！感谢您提供如此详细和全面的答案。我非常感激您的努力！您的回答开头非常简单且有说服力，但是“连续设置位”部分并不像我希望的那样直截了当。无论如何还是非常感谢！ - Misha Moroshko
1
@MishaMoroshko 最基本的解释是：“对于每个即将变成-2或-8或...的2或8或...，都会添加4或16或...，以便2变成4-2，8变成16-8，...”。 “连续位”部分只是演示了这可以累加多个位，因此例如8 + 4 + 2变成16-8 + 4 + 4-2，然后两个4被带过去并成为一个8，然后-8和8相互抵消，剩下16-2。也许我应该添加这个十进制版本的解释以获得更清晰的说明？ - m69 ''snarky and unwelcoming''
我认为现在更好了。再次感谢你的所有努力！ - Misha Moroshko
-1
"

\"0xAAAAAAAA\"是其中一个包含10个二进制模式的魔数。这被用作掩码，因为您正在执行按位异或操作。当您将数字添加到此掩码并进行异或运算时，结果仅受数字提供的那些位的影响，其余位在结果中为0。[由于两个相同位的异或结果为0]。最后，toString（2）将结果转换为二进制

例如： ->假设3是您的数字。将3添加到2863311530 [即0xAAAAAAAA的十进制表示]。 ->将总和（掩码+3）与0xAAAAAAAA进行异或运算，即....101010101101 ^ ....10101010。这会给您111（因为掩码和总和中的最后3个对应位不同） ->将111转换为二进制，即7

"
2
抱歉，但我在你的回答中找不到令人信服的论据来解释为什么给定的函数计算负二进制（而不是其他什么）。 - Misha Moroshko
为什么你要对答案进行负评？你的问题最初并没有要求任何数学证明。我解释了这个函数如何计算给定数字的负二进制表示法。我没有提到任何错误，所以不明白为什么要进行负评。 - vinay hegde
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接