Calcolo della rappresentazione negabinaria di un dato numero senza loop

Question

È possibile fornire una spiegazione convincente o una dimostrazione matematica del motivo per cui la seguente funzione calcola la rappresentazione negabinary di un determinato numero?

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

Answer 1

notazione Negabinary

notazione Negabinary utilizza una radice di -2. Ciò significa che, come in ogni sistema numerico a base negativa, ogni bit ha un valore negativo:

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 

metodo di conversione rapida

Il binario → metodo di conversione negabinary rapido aggiunge quindi xor è un numero con 0xAAAAAAAA o binario ...10101010 (una maschera che indica le posizioni dispari che hanno un valore negativo nella notazione negabinaria), ad es. per il valore di 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) 

Come funziona: un bit impostato

E 'facile vedere come funziona il metodo, se si prende l'esempio di un numero con un solo bit impostato in binario notazione. Se il bit è in una posizione ancora, nulla cambia:

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

Tuttavia, se il bit set è in una posizione strana:

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

il bit set viene spostata a sinistra (con l'aggiunta di 1 a esso), e viene quindi combinato con il negativo del suo valore originale (tramite XOR-ing con la maschera), in modo che un bit con valore 2 ⁿ sia sostituito da 2 ^{n + 1} - 2 ⁿ.

Quindi puoi pensare al metodo di conversione rapida semplicemente come: "sostituisci ogni 2 per 4 - 2, ogni 8 per 16 - 8, ogni 32 per 64 - 32, e così via".

Come funziona: più bit impostati

Quando si converte un numero con più bit impostati, i risultati di conversione di un numero con un bit impostato, come descritto sopra, possono essere semplicemente aggiunti insieme. Combinando per es.esempi-set-bit singolo di 4 e 8 (vedi sopra) per rendere 12:

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

Oppure, per un esempio più complesso, dove vengono effettuate alcune cifre:

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) 

Cosa accade qui è che nella somma che descrive il numero binario:

32 + 16 + 8 + 4 + 2

32 viene convertito in 64 - 32, 8 in 16 - 8 e 2 in 4 - 2, in modo che la somma diventa:

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

dove i due 16 del vengono quindi portati a diventare 32 e le due 4 del sono portati a diventare un 8:

64 - 32 + 32; - 8 + 8 - 2

e il -32 e +32 ca ncel a vicenda, e il -8 e +8 si annullano a vicenda, per dare:

64 - 2

Oppure, usando l'aritmetica negabinary:

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

Il metodo di conversione rapida funziona anche con numeri negativi nella notazione a complemento a due, ad esempio:

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 e troppopieno

La portata di un numero negabinary con n bit (dove n è un numero pari) è:

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

Oppure, per profondità di bit comuni:

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 

Questo intervallo è inferiore a entrambe le rappresentazioni interi standard, con e senza segno con la stessa profondità di bit, quindi entrambi gli interi con e senza segno può essere troppo grande per essere rappresentato in notazione negabinaria con la stessa profondità di bit.

Sebbene il metodo di conversione pratica può apparentemente incorrere in troppopieno per valori negativi di sotto -1/6 × (2 ⁿ -4), il risultato della conversione è ancora corretto:

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) 

funzione inversa

numeri Negabinary possono essere riconvertiti in valori interi standard, invertendo l'aggiunta e XOR-re con la maschera, ad esempio:

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

(Se la funzione inversa viene chiamato solo numeri negabinary creati dalla funzione negabinary(), non v'è alcun rischio di trabocco. Tuttavia, i numeri negabinari a 64 bit da altre fonti potrebbero avere un valore inferiore all'interv. Int64_t, quindi diventa necessario il controllo di overflow.)

Answer 2

"0xAAAAAAAA" è uno di quei numeri magici che contiene una sequenza di 10 pattern (binari). Viene utilizzato come maschera perché si esegue un'operazione XOR bit a bit. Quando aggiungi il numero a questa maschera e fai un XOR, il risultato sarebbe influenzato solo da quei bit forniti dal numero, il resto sarebbe 0 nel risultato. [Poiché XOR di due stessi bit è 0]. Infine, toString (2) converte il risultato in binario

Esempio: -> Considerare 3 è il tuo numero. Aggiungi 3 a 2863311530 [che è la rappresentazione decimale di 0xAAAAAAAA]. -> XOR la ​​somma (maschera + 3) con 0xAAAAAAAA, che è .... 10101010^.... 10101010. Questo dà 111 (dal ultimi 3 corrispondenti bit nella maschera e la somma è differente) -> Converti 111 in binario, che è 7