루프없이 주어진 숫자의 음수 표현 계산

음수 표기법

음수 표기법은 기수 -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(음수 표기법으로 음수 값을 갖는 홀수 위치를 나타내는 마스크)을 사용 하여 숫자를 더한 다음 xor (예 : 값 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을 더하여) 원래 값의 음수 (마스크와 XOR-ing)와 결합되어 값이 ^{2n 인} 비트가 ^{2n + 1} 로 대체됩니다. -2 ⁿ .

따라서 빠른 변환 방법은 "매 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)  

음수 값

빠른 변환 방법은 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 × ( ²ⁿ -1) → 1/3 × ( ²ⁿ -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 × (2 ⁿ -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 범위 미만의 값을 가질 수 있으므로 오버플로 검사가 필요한.)