Ho visto le numerose domande sul conteggio del numero di bit impostati in un input , ma perché è utile?Perché è utile contare il numero di bit?
Per chi cerca gli algoritmi di contare po ', guarda qui:
Si può considerare una stringa di bit come set, con un 1 che rappresenta l'appartenenza al set per l'elemento corrispondente. Il conteggio dei bit ti dà quindi il population count del set.
Le applicazioni pratiche comprendono codici di compressione, crittografia e correzione degli errori. Vedi per es. wikipedia.org/wiki/Hamming_weight e wikipedia.org/wiki/Hamming_distance.
Se stai ruotando il tuo schema di parità, potresti voler contare il numero di bit. (In generale, ovviamente, preferirei usare quello di qualcun altro.) Se stai emulando un vecchio computer e vuoi tenere traccia di quanto velocemente avrebbe funzionato sull'originale, alcuni avevano istruzioni di moltiplicazione la cui velocità variava con il numero di 1 bit.
Non riesco a pensare a nessuna volta che ho voluto farlo negli ultimi dieci anni o giù di lì, quindi sospetto che si tratti più di un esercizio di programmazione che di un'esigenza pratica.
In modo ironico, è utile per una domanda di intervista perché richiede un pensiero dettagliato di basso livello e non sembra essere insegnato come un algoritmo standard nei corsi di sci.
Alcune persone preferiscono utilizzare bitmap per indicare presenza/assenza di "materiale".
C'è un semplice trucco per isolare il meno significativo 1 bit in una parola, convertirlo in un campo di quelli nei bit sottostanti, e quindi è possibile trovare il numero di bit contando gli 1 bit.
countbits((x XOR (x-1)))-1;
Guarda che funziona.
Let x = 00101100
Then x-1 = 00101011
x XOR x-1 = 00000111
che dispone di 3 bit impostati, quindi il bit 2 è stato il meno significativo 1-bit nella parola originale
È possibile calcolare la parità direttamente con un minor numero di operazioni che per un conteggio di popolazione (a meno che la CPU ha ' POPCNT' o simile). –