Swap ogni coppia di bit in byte

Questa era una domanda posta da un rappresentante di NVIDIA ad una carriera fiera:Swap ogni coppia di bit in byte

Scrivi piccolo, codice efficiente per scambiare ogni coppia di bit all'interno di un byte; ad esempio, 10 11 01 10 dovrebbe diventare 01 11 10 01.

Esiste un modo più "efficiente" per farlo rispetto al fare un ciclo for attraverso ogni altro indice? Il mio codice era piccolo, ma non riesco a pensare a quanto potrebbe essere più "efficiente" di un ciclo ... Immagino che ci possa essere un modo per usare XOR per evitare un loop, ma non posso capirlo.

Grazie!

fonte

2011-01-25 Mehrdad

E 'wasn't' una domanda? Io non lo vedo ... –

@ MrDisappointment Sospetto che se fosse una domanda, Mehrdad avrebbe violato un accordo scritto o avrebbe chiesto di non condividere la domanda con gli altri. – Phrogz

@MrDisappointment: LOL mi dispiace, errore di battitura; fixed XD ... @Phrogs: Non esisteva un accordo o qualcosa del genere, era una fiera aperta di carriera con cento o due persone; nessuna firma o nulla del genere. :) – Mehrdad

È possibile utilizzare una tabella di ricerca a 256 voci.

In alternativa, ((x & 0x55) << 1) | ((x & 0xAA) >> 1).

fonte

2011-01-25 00:32:42

+1. Se è la velocità che vuoi, la tabella di ricerca è la risposta. Utilizza 256 byte per una tabella di ricerca ma, come con la maggior parte delle ottimizzazioni, è un compromesso spazio/tempo. Se non vuoi sprecare quello spazio, è improbabile che tu diventi più veloce di un paio di turni e operazioni bit. – paxdiablo

Attenzione al tipo "firmato", ovviamente. –

+1 Penso che sia la seconda soluzione, dal momento che è la più concisa e molto efficiente ... argh, così facile eppure così difficile. :( – Mehrdad

Ricerca tabella (a meno che non ci sia una particolare soluzione specifica NVIDA che stava cercando).

fonte

2011-01-25 00:32:06

Non era alla ricerca di una soluzione specifica per NVIDIA, ma era alla ricerca di un codice * veloce * e * piccolo ... la soluzione di ricerca della tabella sarebbe stata conteggiata? (anche se devo ammettere che non ci ho pensato ...) – Mehrdad

@Mehrdad: La ricerca di una tabella è solo una "prima cosa che viene in mente" con questi tipi di problemi. Certamente potrebbe esserci un migliore, intelligente trucco. Si potrebbe anche considerare una tabella più piccola di 16 byte (o anche di 8 byte) combinata con alcune operazioni di spostamento/maschera per cercare 4 bit alla volta. Non sono sicuro di dove potrebbe essere il punto debole. –

Qualcosa del genere dovrebbe funzionare

(i >> 1) & 01010101 + (i << 1) & 10101010

i >> 1 turni tutto a 1 bit verso destra, e & 01010101 lascia solo bit alla posizione pari.
La seconda parte si occupa di posizioni di bit dispari nella stessa fasion.

Non sono sicuro di quanto sia efficiente.

fonte

2011-01-25 00:32:59

+1 Questo è dannatamente intelligente, grazie ... Stavo pensando ad un modo per usare i bit shift ma non riuscivo a capirlo. Cool !! :) – Mehrdad

Sì, preferisco il | operatore all'operatore + ma la stessa soluzione. E ovviamente il tuo codice è pseudo per la rappresentazione in base 2. – CashCow

Poiché esistono solo 256 combinazioni possibili in un byte, questo sembra un buon candidato per l'utilizzo di una soluzione basata su una tabella di ricerca per qualsiasi momento in cui la velocità di esecuzione continua è più importante del pre-calcolo iniziale e/o dell'utilizzo totale della memoria.

Ad esempio:

lookupTable[00000000] = 00000000 
lookupTable[00000001] = 00000010 
lookupTable[00000010] = 00000001 
...

fonte

2011-01-25 00:34:12 Coxy

Decisamente non un piccolo codice. :( – Mehrdad

Sicuramente non sono d'accordo, ma ricorda che il codice piccolo non è sempre efficiente ed il codice non è sempre piccolo – Coxy

La mancanza di cache è un problema con le tabelle di ricerca in generale.Per le cose così piccole, è più semplice calcolare il risultato Penso. –

Senza tabella di ricerca (o per generare la cosa in primo luogo) è inoltre possibile:

spostamento a sinistra e E con maschera sinistra bit (10101010)
spostamento a destra e AND con maschera bit di destra (01010101)
O risultati insieme.

spostato a sinistra è 01 10 11 00 mascherato con 10101010 ci dà 00 10 10 00

spostato a destra (originale) è mascherata con 01010101 ci dà 01 01 00 01

O i nostri risultati insieme

Quindi, in C o C++ si potrebbe fare

unsigned char bitswap(unsigned char uch) 
{ 
    return ((uch<<1) & 0xAA) | (uch>>1) & 0x55); 
}

solo correre che per tutti i valori da 0x00 a 0xFF (garantire il vostro ciclo termina!) Per generare il "tavolo".

fonte

2011-01-25 15:20:20 CashCow

Grazie per la spiegazione! – Chayemor

Per 32 bit interger in java ..

public int swapOddEvenbits(int x) 
{ 
    return ( ((x & 0xaaaaaaaa) >> 1 | ((x & 0X55555555) << 1)); 

}

Se si lavora con 64 bit, si avrebbe bisogno di cambiare maschera ..

fonte

2014-07-19 17:52:26

Swap ogni coppia di bit in byte

risposta

Problemi correlati