Qual è il modo più efficace per de-interleave di bit da un int a 32 bit? In questo caso particolare, mi preoccupo solo dei bit dispari, anche se sono sicuro che è semplice generalizzare qualsiasi soluzione per entrambi i set.
Ad esempio, voglio convertire 0b01000101 in 0b1011 . Qual è il modo più veloce?
MODIFICARE:
In questa applicazione, posso garantire che i bit pari siano tutti zeri. Posso approfittare di questo fatto per migliorare la velocità o ridurre lo spazio?
Dato che sai che ogni altro bit è 0 nella tua applicazione, puoi farlo in questo modo:
x = (x | (x >> 1)) & 0x33333333; x = (x | (x >> 2)) & 0x0f0f0f0f; x = (x | (x >> 4)) & 0x00ff00ff; x = (x | (x >> 8)) & 0x0000ffff;
Il primo passo appare così:
0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p x | 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0 x >> 1 -------------------------------- = 0aabbccddeeffgghhiijjkkllmmnnoop x | (x >> 1) & 00110011001100110011001100110011 0x33333333 -------------------------------- = 00ab00cd00ef00gh00ij00kl00mn00op (x | (x >> 1)) & 0x33333333
Quindi il secondo passaggio funziona con due bit alla volta e così via.
In termini di velocità, una tabella di ricerca di 16 bit di larghezza con 2 ^ 32 voci sarà difficile da battere! Ma se non si dispone di molta memoria, quattro ricerche in una tabella a 256 voci, più alcuni turni e AND per unirli insieme, potrebbero essere una scelta migliore. O forse il punto debole è da qualche parte nel mezzo … dipende dalle risorse che hai a disposizione e da come il costo di inizializzazione della tabella di ricerca sarà ammortizzato sul numero di ricerche che devi eseguire.
Non sono sicuro di quanto sarebbe veloce , ma potresti fare qualcosa del genere
int a = 0b01000101; int b = 0; int i = 0; while (a > 0) { b |= (a & 1) << i; a >>= 2; }
Il che toglierebbe tutti i pezzi dispari da a e li mise su b.