Come deinterlacciare i bit (annullamento della messa in attesa?)

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.