Innanzitutto una precisazione:
Quando s = 4 (cioè, il modulo è uguale a 0xF) ottengo il seguente srotolamento:
m = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F)
m = ((n >> 16) + (n & 0x0000FFFF)
m = ((n >> 8) + (n & 0x000000FF)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = ((n >> 4) + (n & 0x0000000F)
m = m == 0xF ? 0 : m;
Questo è molto diverso da quello che hai nella tua domanda. Per spiegare perché funziona:
Hai mai sentito parlare del trucco matematico in cui se sommi tutte le cifre di un numero e è divisibile per 9, allora anche il numero originale è? Funziona perché il resto di dividere sia l'originale che la somma per 9 è lo stesso. In realtà, è quello che stiamo facendo qui, solo in una base diversa - nel tuo esempio, con base esadecimale.
La matematica kung-fu è questo:
contributo di ogni cifra esadecimale al valore finale può essere rappresentato come V * 16^P. Notare che 16^P = 1 (mod 15), quindi il contributo di ciascuna cifra esadecimale al valore finale è semplicemente V (mod 15). In altre parole, per ottenere il contributo totale da tutte le cifre, aggiungile tutte a (mod 15).
Le operazioni bit a bit sono solo un modo intelligente per eseguire ciò nel numero di passi logaritmico: aggiungere ripetutamente la prima metà delle cifre esadecimali alla seconda metà.
Il problema con il trucco dei 9 è che si potrebbe finire con un numero a due cifre: 99 = 9 + 9 = 18 (mod 10)! Quindi fai di nuovo il trucco: 18 = 1 + 8 = 9 (mod 10).
Allo stesso modo, seguiamo le iterazioni "extra" di m = ((n >> 4) + (n & 0x0000000F) finché il numero rimanente è una cifra.
Ora l'unico dettaglio rimanente è se otteniamo 0xF come risultato nel qual caso vogliamo invece 0x0.
Sì, lo sapevo. Sto lavorando per ottimizzare un metodo di modulo di assemblaggio, che al momento utilizza rami e una maschera del modulo 2^n-1. Quindi sto cercando di sbarazzarmi dei rami e usare invece questo metodo. –
Interessante. Posso chiederti che tipo di applicazione hai che usa un modulo di 2^n-1? C'è una ragione per non usare 2^n o un numero primo invece? – JS1
@ JS1 Non è così insolito. Un esempio di molti: un codice Reed-Solomon byte-saggio (riconoscimento e correzione degli errori dei dati) e algoritmi basati sul campo di Galois in generale. La codifica (di RS) è fata semplice in termini di codice, consiste principalmente di cicli, aggiunte e modulo (dato che alcuni dati statici vengono calcolati in anticipo, anziché ogni volta durante la decodifica) – deviantfan