È possibile determinare il numero di transizioni bit a bit in un numero intero a 8 bit?

Question

Non riesco a trovare alcun po 'di magia su questo, quindi speravo che qualcuno qui fosse in grado di fare un po' di luce se questo è possibile.

Sto cercando di trovare il numero di transizioni bit a bit in un intero a 8 bit (il numero intero è in realtà un intero a 32 bit, ma sto usando solo i primi 8 bit) per determinare se gli 8 bit sono uniformi (2 o meno transizioni).

Ad esempio:

00100000 - two transitions - uniform 
00100001 - three transitions - not uniform 
10101010 - seven transitions - not uniform 
00000000 - no transitions - uniform 

C'è un modo più veloce per trovare il numero di transizioni diverse scorrendo ogni bit (scorrendo ogni bit è attualmente l'unica soluzione che posso venire con)?

Answer 1

È possibile x-o il valore con il valore spostato di un bit e quindi contare il numero di 1 nel risultato.

unsigned v = (x^(x>>1)) & 0x7F; 
unsigned count = 0; 
while (v) { 
    count++; 
    v &= (v - 1); 
} 

noti inoltre che un byte può avere solo 256 configurazioni, in modo che il calcolo può essere fatto una volta e mettere in un piccolo tavolo di 256 byte.

Se si vuole solo sapere se ci sono 2 o meno modifiche del loop può essere srotolato:

unsigned v = (x^(x >> 1)) & 0x7F; 
v &= v - 1; 
v &= v - 1; 
uniform = (v == 0); 

Si noti che questo calcolo è indipendente da quanto grande è il numero e si può usare per esempio direttamente un 32-bit unsigned numero (l'unica cosa che cambia è la maschera che diventa 0x7FFFFFFF)

Answer 2

per la tua definizione di uniformi, il numero deve essere in forma 00011111 o 11110000. Considera il precedente (zeri seguiti da quelli).

Aggiungere uno al valore. Se è uniforme, sarebbe esattamente uno 1 bit, che significa una potenza di 2.

Per verificare se un valore è una potenza di due, utilizzare (x & (x - 1)) == 0. Per abbreviare il codice non è necessario aggiungerne uno nel passaggio precedente. Invece si controlla (x & (x + 1)) == 0

Applicare questo all'altro caso NON utilizzando il valore iniziale e ripetere il processo precedente.

#include <cstdio> 
bool isuniform(unsigned char x) { 
    unsigned char y = ~x; 
    return (x & (x + 1)) == 0 || (y & (y + 1)) == 0; 
} 
int main() { 
    printf("%d\n", isuniform(0)); // 00000000 
    printf("%d\n", isuniform(1)); // 00000001 
    printf("%d\n", isuniform(3)); // 00000011 
    printf("%d\n", isuniform(7)); // 00000111 
    printf("%d\n", isuniform(15)); // 00001111 
    printf("%d\n", isuniform(31)); // 00011111 
    printf("%d\n", isuniform(63)); // 00111111 
    printf("%d\n", isuniform(127)); // 01111111 
    printf("%d\n", isuniform(255)); // 11111111 
    printf("%d\n", isuniform(254)); // 11111110 
    printf("%d\n", isuniform(252)); // 11111100 
    printf("%d\n", isuniform(248)); // 11111000 
    printf("%d\n", isuniform(240)); // 11110000 
    printf("%d\n", isuniform(224)); // 11100000 
    printf("%d\n", isuniform(192)); // 11000000 
    printf("%d\n", isuniform(128)); // 10000000 
    //---------- 
    printf("%d\n", isuniform(2)); 
    printf("%d\n", isuniform(4)); 
    printf("%d\n", isuniform(50)); 
    printf("%d\n", isuniform(123)); 
    printf("%d\n", isuniform(129)); 
    printf("%d\n", isuniform(253)); 
    return 0; 
}