在没有循环的情况下计算给定数字的负二进制表示
Calculating the negabinary representation of a given number without loops
您能否提供令人信服的解释或数学证明，说明为什么以下函数会计算给定数字的 negabinary 表示形式？
function quickNegabinary(number) {
var mask = 0xAAAAAAAA;
return ((number + mask) ^ mask).toString(2);
}
“0xAAAAAAAA”是其中一个包含 10（二进制）模式序列的幻数。这用作掩码，因为您正在执行按位异或运算。当您将数字添加到此掩码并执行 XOR 时，结果将仅受数字提供的那些位的影响，结果中的其余部分将为 0。 [因为两个相同位的 XOR 为 0]。最后，toString(2) 将结果转换为二进制
示例：
-> 考虑 3 是你的号码。将 3 添加到 2863311530 [这是 0xAAAAAAAA 的十进制表示形式]。
-> 将总和（掩码 + 3）与 0xAAAAAAAA 异或，即 ....101010101101 ^ ....10101010。这给你 111（因为掩码中的最后 3 个对应位和总和不同）
->将111转为二进制，即7
二进制表示法
负二进制表示法使用基数 -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。
所以你可以简单的把快速转换的方法想成："replace every 2 by 4 - 2, every 8 by 16 - 8, every 32 by 64 - 32, and so on"。
工作原理：多个设置位
当转换具有多个设置位的数字时，如上所述，可以简单地将转换为具有一个设置位的数字的结果相加。结合例如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)
反转函数
负二进制数可以通过逆向加法和掩码异或转换回标准整数值，例如：
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() 函数创建的负二进制数调用反向函数，则没有溢出的风险。但是，来自其他来源的 64 位负二进制数可能有一个值低于 int64_t 范围，因此需要进行溢出检查。）
您能否提供令人信服的解释或数学证明，说明为什么以下函数会计算给定数字的 negabinary 表示形式？
function quickNegabinary(number) {
var mask = 0xAAAAAAAA;
return ((number + mask) ^ mask).toString(2);
}
“0xAAAAAAAA”是其中一个包含 10（二进制）模式序列的幻数。这用作掩码，因为您正在执行按位异或运算。当您将数字添加到此掩码并执行 XOR 时，结果将仅受数字提供的那些位的影响，结果中的其余部分将为 0。 [因为两个相同位的 XOR 为 0]。最后，toString(2) 将结果转换为二进制
示例： -> 考虑 3 是你的号码。将 3 添加到 2863311530 [这是 0xAAAAAAAA 的十进制表示形式]。 -> 将总和（掩码 + 3）与 0xAAAAAAAA 异或，即 ....101010101101 ^ ....10101010。这给你 111（因为掩码中的最后 3 个对应位和总和不同） ->将111转为二进制，即7
二进制表示法
负二进制表示法使用基数 -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。
所以你可以简单的把快速转换的方法想成："replace every 2 by 4 - 2, every 8 by 16 - 8, every 32 by 64 - 32, and so on"。
工作原理：多个设置位
当转换具有多个设置位的数字时，如上所述，可以简单地将转换为具有一个设置位的数字的结果相加。结合例如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)
反转函数
负二进制数可以通过逆向加法和掩码异或转换回标准整数值，例如：
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() 函数创建的负二进制数调用反向函数，则没有溢出的风险。但是，来自其他来源的 64 位负二进制数可能有一个值低于 int64_t 范围，因此需要进行溢出检查。）