Codice di parità bit per numero dispari di bit

Sto cercando di trovare la parità di una stringa di bit in modo che restituisca 1 se x ha un numero dispari di 0.
posso solo usare operazioni bit per bit di base e quello che ho finora passa la maggior parte delle prove, ma mi chiedo 2 cose:Codice di parità bit per numero dispari di bit

Perché x^(x + ~ 1) lavoro? Mi sono imbattuto in questo, ma sembra darti 1 se c'è un numero dispari di bit e qualcos'altro se pari. Come 7^6 = 1 perché 7 = 0b0111
Questa è la giusta direzione per la risoluzione dei problemi? Sto assumendo che il mio problema derivi dalla prima operazione, in particolare (x + ~ 1) perché supererebbe alcuni numeri di complemento di 2. Grazie

Codice:

int bitParity(int x) { 
    int first = x^(x + ~1); 
    int second = first^1; // if first XOR gave 1 you'll return 0 here 
    int result = !!second; 
return result; 
}

fonte

2011-09-23 tippenein

Dove hai trovato quell'algoritmo? – rnunes

non usare 'int', ci sarà overflow e questo è quindi un comportamento non definito. Usa 'unsigned' e' 1u' invece, qui il wrap around è ben definito. –

Questo algoritmo non funziona. Restituisce 1 per tutti i valori compresi tra 0 e 255. –

userei il conteggio reale, piuttosto che hack a livello di bit che sfruttano la rappresentazione dei numeri, che sarebbero entrambi si sentono più sicuri ed essere più pulito e facile da capire. Probabilmente più lento, ovviamente, ma è un bel compromesso specialmente quando non si sa nulla delle aspettative di rendimento.

Fare questo, basta scrivere il codice per contare il numero di 1 bit, la soluzione più semplice generalmente si riduce a un ciclo.

UPDATE: Dati i limiti (strani e fastidiosi), la mia risposta sarebbe probabilmente al unwind loop data nella soluzione "naive" sulla pagina bithacks. Non sarebbe carino, ma potrei fare qualcosa di utile. :)

fonte

2011-09-23 14:45:25 unwind

I certamente userebbe un ciclo per contare facilmente ogni bit o anche solo XOR tutti i bit insieme, ma per questo compito, non mi è permesso usare le strutture di controllo. Solo |^& >><< ~ +! Quindi la tua risposta è stata la mia reazione immediata a questo, ma niente da fare. – tippenein

Ho preso un codice scritto in precedenza per il conteggio dei bit e solo AND'd il risultato con 0x1 per vedere se c'è un numero dispari di bit o meno. Tuttavia, ho fatto l'algoritmo bitCount (int x) tramite la forza bruta; controllato ogni bit con !!(x & (1 << bit #)) Al momento non è abbastanza buono per me, ma per ora il problema della parità di bit è stato risolto. – tippenein

La tua funzione di parità in realtà non funziona per quanto posso dire - sembra avere la risposta giusta circa la metà del tempo, che è tanto buona quanto restituire un risultato casuale (o anche solo restituire 0 o 1 tutto il tempo).

Ci sono diversi hack livello di bit che Do realmente funzionano a: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - probabilmente avrete bisogno di guardare l'ultimo di questi: http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel

fonte

2011-09-23 15:02:02

Mi rendo conto che il mio codice completo non funziona, ma il x^(x-1) sembrava dare risposte che avevano senso per i valori che ho provato. Se hai ragione, dovrei semplicemente scaricarlo e ricominciare da capo. – tippenein

Basta provare i valori di input 0, 1, 2 e 3 e vedrai che non funzionerà. –

bit di parità può essere fatto in questo modo:

#include <stdio.h> 

int parity(unsigned int x) { 
    int parity=0; 
    while (x > 0) { 
     parity = (parity + (x & 1)) % 2; 
     x >>= 1; 
    } 
} 

int main(int argc, char *argv[]) { 
    unsigned int i; 
    for (i = 0; i < 256; i++) { 
     printf("%d\t%s\n", i, parity(i)?"odd":"even"); 
    } 
}

fonte

2011-09-23 15:05:18 sastanin

Codice di parità bit per numero dispari di bit

risposta

Problemi correlati