计算给定数量的negabinary重新presentation没有循环 [英] Calculating the negabinary representation of a given number without loops

问题描述

您可以提供一个令人信服的解释，或者一个数学证明，为什么下面的函数计算 negabinary 重新给定数量的presentation？

 函数quickNegabinary（数字）{
  VAR面膜= 0xAAAAAAAA;
  返回（（数+掩模）^掩模）的ToString（2）;
}
 

解决方案

Negabinary符号

Negabinary符号使用-2基数。这意味着，作为在带有负碱每个数字系统，每隔一个比特具有负值

位置：... 7 6 5 4 3 2 1 0二：... 128 64 32 16 8 4 2 1
negabinary：... -128 +64 -32 +16 -8 +4 -2 +1


快速转换方法

快速二元RARR; negabinary转换方法添加，然后XOR与 0xAAAAAAAA 一个数字，或二进制 ... 10101010 （掩模表示具有在negabinary符号负值奇数位置），例如对于价值82：

二进制：01010010 = 82（二进制：64 + 16 + 2）
面膜：10101010 = 170
滨+面膜11111100 = 252
（斌+面膜）XOR面膜：01010110 = 82（negabinary：64 + 16 + 4 - 2）


它是如何工作：一组位

这是很容易看到该方法是如何工作的，如果你把一个数字的例子，在二进制表示法中只有一组比特。如果设定位为偶数位置，没有什么变化：

二进制：00000100 = 4（二进制：4）
面膜：10101010 = 170
滨+面膜10101110 = 174
（斌+面膜）XOR面膜：00000100 = 4（negabinary：4）


但是，如果该组位是在奇数位置：

二进制：00001000 = 8（二进制：8）
面膜：10101010 = 170
滨+面膜10110010 = 178
（斌+面膜）XOR面膜：00011000 = 8（negabinary：16 - 8）


的组位被向左移位（通过加入1至它），然后用负其原始值的组合（通过用掩模-ING XOR）​​，从而使一个位与值2 ^N 被替换成了2 ^{N + 1} - 2 ^N 。

所以，你能想到的快速转换方法简单为：每2 4更换 - 16 2，每隔8 - 8日，每32个64 - 32，等等。

工作原理：多套位

当转换一个号码与几个比特集，转换一个数字与一组位的结果，如上所述，可简单地一起加入。例如结合的4和8单组位的例子（见上文），使12：

二进制：00001100 = 12（二进制：8 + 4）
面膜：10101010 = 170
滨+面膜10110110 = 182
（斌+面膜）XOR面膜：00011100 = 12（negabinary：16 - 8 + 4）


或者，对于更为复杂的例子，其中有些数字都进行：

二进制：00111110 = 62（二进制：32 + 16 + 8 + 4 + 2）
面膜：10101010 = 170
滨+面膜11101000 = 232
（斌+面膜）XOR面膜：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

或者，使用negabinary算术：

+1 +1（进）
     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）


负值

快速转换方法也适用于负数在二的补码表示法，例如：

二进制：11011010 = -38（补）
面膜：10101010 = -86（补）
滨+面膜10000100 = -124（补）
（斌+面膜）XOR面膜：00101110 = -38（negabinary：-32 - 8 + 4 - 2）


二进制：11111111 11011010 = -38（补）
面膜：10101010 10101010 = -21846（补）
滨+面膜10101010 10000100 = -21884（补）
（斌+面膜）XOR面膜：00000000 00101110 = -38（negabinary：-32 - 8 + 4 - 2）


范围和溢出

具有n位的negabinary数目（n为偶数）的范围是：

  

-2/3＆倍; （2 ^N -1）RARR; 1/3＆倍; （2 ^N -1）

或者，对于常见位深度：

8位：-170〜85
16位：-43,690〜21845
32位：-2,863,311,530〜1431655765
64位：-1.23e + 19〜+ 6.15e 18
80位：-8.06e + 23〜+ 4.03e 23


此范围比相同的位深度符号和无符号标准整数重新presentations较低，所以有符号和无符号整数可能太大而无法重新presented在negabinary符号具有相同的比特深度。

虽然快速转换方法似乎可以运行到溢出低于-1/6和次负值; （2 ^N -4），转换的结果仍然是正确的：

二进制：11010011 = -45（补）
面膜：10101010 = -86（补）
滨+面膜11111111 01111101 = -131（补）
溢出截断：01111101 = 125（补）
（斌+面膜）XOR面膜：11010111 = -45（negabinary：-128 + 64 + 16 + 4 - 2 + 1）


二进制：11111111 11010011 = -45（补）
面膜：10101010 10101010 = -21846（补）
滨+面膜10101010 01111101 = -21891（补）
（斌+面膜）XOR面膜：00000000 11010111 = -45（negabinary：-128 + 64 + 16 + 4 - 2 + 1）


反函数

Negabinary号码可以通过颠倒加入，并与掩模，例如：

异或转换回标准整数值

uint64_t中negabinary（斌的int64_t）{
    如果（斌＆GT; 0x5555555555555555）抛出std ::溢出错误（值超出范围）;
    常量uint64_t中面具= 0xAAAAAAAAAAAAAAAA;
    回报（面膜+宾）^掩盖;
}revnegabin的int64_t（uint64_t中NEG）{
    //常量uint64_t中甚至= 0x2AAAAAAAAAAAAAAA，奇= 0x5555555555555555;
    //如果（（NEG＆安培;即使）GT;（NEG＆安培;奇））抛出std ::溢出错误（值超出范围）;
    常量uint64_t中面具= 0xAAAAAAAAAAAAAAAA;
    回报（面具^负） - 口罩;
}


（如果反向功能仅称为由negabinary（）函数创建negabinary号码，也没有溢出的危险。不过，从其他来源的64位negabinary号码可以具有以下的int64_t范围内的值，所以后来溢出检查成为必要。）

Could you provide a convincing explanation, or a mathematical proof, to why the following function calculates the negabinary representation of a given number?

function quickNegabinary(number) {
  var mask = 0xAAAAAAAA;
  return ((number + mask) ^ mask).toString(2);
}

解决方案

Negabinary notation

Negabinary notation uses a radix of -2. This means that, as in every number system with a negative base, every other bit has a negative value:

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  

Quick conversion method

The quick binary→negabinary conversion method adds and then xor's a number with 0xAAAAAAAA, or binary ...10101010 (a mask which indicates the odd positions which have a negative value in negabinary notation), e.g. for the value 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)  

How it works: one set bit

It is easy to see how the method works, if you take the example of a number with only one set bit in binary notation. If the set bit is at an even position, nothing changes:

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

However, if the set bit is at an odd position:

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

the set bit is shifted left (by adding 1 to it), and is then combined with the negative of its original value (by XOR-ing with the mask), so that a bit with value 2ⁿ is replaced by 2ⁿ⁺¹ - 2ⁿ.

So you can think of the quick conversion method simply as: "replace every 2 by 4 - 2, every 8 by 16 - 8, every 32 by 64 - 32, and so on".

How it works: multiple set bits

When converting a number with several set bits, the results of converting a number with one set bit, as described above, can simply be added together. Combining e.g. the single-set-bit examples of 4 and 8 (see above) to make 12:

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

Or, for a more complicated example, where some digits are carried:

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)  

What happens here is that in the sum which describes the binary number:

32 + 16 + 8 + 4 + 2

32 is converted into 64 - 32, 8 into 16 - 8 and 2 into 4 - 2, so that the sum becomes:

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

where the two 16's are then carried to become a 32 and the two 4's are carried to become an 8:

64 - 32 + 32 - 8 + 8 - 2

and the -32 and +32 cancel each other out, and the -8 and +8 cancel each other out, to give:

64 - 2

Or, using negabinary arithmetic:

          +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)  

Negative values

The quick conversion method also works for negative numbers in two's complement notation, e.g.:

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)  

Range and overflow

The range of a negabinary number with n bits (where n is an even number) is:

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

Or, for common bit depths:

 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  

This range is lower than both signed and unsigned standard integer representations with the same bit depth, so both signed and unsigned integers can be too large to be represented in negabinary notation with the same bit depth.

Although the quick conversion method can seemingly run into overflow for negative values below -1/6 × (2ⁿ-4), the result of the conversion is still correct:

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)  

Reverse function

Negabinary numbers can be converted back to standard integer values by reversing the addition and XOR-ing with the mask, e.g.:

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

(If the reverse function is only called on negabinary numbers created by the negabinary() function, there is no risk of overflow. However, 64-bit negabinary numbers from other sources could have a value below the int64_t range, so then overflow checking becomes necessary.)

这篇关于计算给定数量的negabinary重新presentation没有循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！