codice C per contare il numero di bit '1' in un unsigned char
-
22-08-2019 - |
Domanda
Ho bisogno di codice C per restituire il numero di 1 di in un unsigned char in C. Ho bisogno di una spiegazione sul perché funziona se non è evidente. Ho trovato un sacco di codice per un numero a 32 bit, ma non tanto per un unsigned char.
Soluzione
Lo stesso codice funzionerà per un unsigned char. Loop su tutti i bit di loro prova. Vedere questo .
Altri suggerimenti
const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
unsigned char CountOnes(unsigned char x)
{
unsigned char results;
results = oneBits[x&0x0f];
results += oneBits[x>>4];
return results
}
Avere una matrice che conosce il numero di bit per 0 a 15. Registrare i risultati per ogni nibble.
HACKMEM ha questo algoritmo in 3 operazioni (approssimativamente tradotto a C):
bits = (c * 01001001001ULL & 042104210421ULL) % 017;
(ULL
è quello di forzare a 64 bit aritmetica. E 'necessario, a malapena ... questo calcolo richiede interi 33-bit).
In realtà, è possibile sostituire il secondo costante con 042104210021ULL
, dal momento che si sta contando solo 8 bit, ma non sembra ben simmetrica.
Come funziona? Pensate a c
bit per bit, e ricordare che (a + b) % c = (a % c + b % c) % c
, e se e solo se (a | b) == a + b
(a & b) == 0
.
(c * 01001001001ULL & 042104210421ULL) % 017
01 01001001001 01 1
02 02002002002 02000000000 1
04 04004004004 04000000 1
010 010010010010 010000 1
020 020020020020 020 1
040 040040040040 040000000000 1 # 040000000000 == 2 ** 32
0100 0100100100100 0100000000 1
0200 0200200200200 0200000 1
Se non si dispone di 64 bit aritmetica disponibili, è possibile dividere c
fino in stuzzichini e fare ogni mezzo, prendendo 9 operazioni. Ciò richiede solo 13 bit, in modo da utilizzare 16 o 32 bit aritmetica funzionerà.
bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7;
(c * 0421 & 01111) % 7
1 0421 01 1
2 01042 01000 1
4 02104 0100 1
8 04210 010 1
Per esempio, se c == 105 == 0b11001001
,
c == 0100
| 040
| 010
| 01 == 0151
* 01001001001001ULL == 0100100100100
| 040040040040
| 010010010010
| 01001001001 == 0151151151151
& 0421042104210421ULL == 0100000000
| 04000000000
| 010000
| 01 == 04100010001
% 017 == 4
c & 017 == 8 | 1 == 011
011 * 0421 == 8 * 0421 | 1 * 0421 == 04210 | 0421 == 04631
04631 & 0111 == 04210 & 0111 | 0421 & 0111 == 010 | 01 == 011
011 % 7 == 2
c >> 4 == 4 | 2 == 06
06 * 0421 == 4 * 0421 | 2 * 0421 == 02104 | 01042 == 03146
03146 & 0111 == 02104 & 0111 | 01042 & 0111 == 0100 | 01000 == 01100
01100 % 7 == 2
2 + 2 == 4
Si veda la pagina hack po 'mani in: http://graphics.stanford.edu /~seander/bithacks.html#CountBitsSetKernighan
ci sono molte buone soluzioni per questo.
Inoltre, questa funzione nella sua più semplice implementazione è abbastanza banale. Si dovrebbe prendere il tempo per imparare come fare questo.
Per un intero piccolo come un unsigned char a ottenere migliori prestazioni con un piccolo lookup-table.
So cosa algoritmi di popolazione-count che stai nota. Essi lavorano facendo aritmetica dei più parole più piccoli di un intero memorizzato in un registro.
Questa tecnica è chiamata SWAR ( http://en.wikipedia.org/wiki/SWAR).
Per ulteriori informazioni vi consiglio di controllare le hacker delizia sito: www.hackersdelight.org. Ha codice di esempio e scritto un libro che spiega questi trucchi in dettaglio.
Come già risposto, i modi standard di bit contando anche lavorare su caratteri senza segno.
Esempio:
unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
if ( value & 1 == 1 )
bitCount++;
value >>= 1;
}
unsigned char è un "numero" esattamente nello stesso modo in cui un galleggiante 32 bit o intero è un "numero", ciò che il compilatore li ritiene rappresentare è quello che cambia.
se ti immagini un char come i suoi bit:
01010011 (8 bit);
si possono contare i bit impostati nel modo seguente:
prendere il valore, diciamo x, e prendere x% 2, il resto sarà 1 o 0. che è, a seconda della endianness del char, sinistra o più a destra bit. accumulare il resto in una variabile separata (questo sarà il numero risultante di bit impostati).
>> poi (spostamento a destra) 1 bit.
ripetere fino a 8 bit sono stati spostati.
il codice c dovrebbe essere abbastanza semplice da implementare dal mio pseudocodice, ma in fondo
public static int CountSetBits(char c)
{
int x = 0;
int setBits = 0;
while (x < 7)
{
setBits = setBits + c % 2;
c = c >> 1;
x = x + 1;
}
}
di base sul post di Ephemient, abbiamo la non ramificata versione 8 bit. E 'in un'espressione esadecimale.
typedef unsigned char UINT8;
typedef unsigned short UINT16;
typedef unsigned long long UINT64;
int hammingWeight8( const UINT8& c)
{
return ( c* 0x8040201ULL & 0x11111111)%0xF;
}
Applicare due volte, abbiamo una versione a 16 bit, che ha bisogno di 9 operazioni.
int hammingWeight16( const UINT16& c)
{
return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF +
((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}
Qui scrivo una versione 16bits variante che necessita 64bit registri e 11 operazioni. Sembra non migliore di quella precedente, ma utilizza solo il funzionamento 1 modulo.
int hammingWeight16( const UINT16& c)
{
UINT64 w;
w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
return (c!=0)*(w+1+(c==0xFFFF)*15);
}