Intercambiar cada par de bits en el byte

Ésta era una pregunta formulada por el representante de NVIDIA en una feria de empleo:Intercambiar cada par de bits en el byte

escribir código pequeño y eficiente para intercambiar cada par de bits dentro de un byte; por ejemplo, 10 11 01 10 debe convertirse en 01 11 10 01.

¿Hay alguna manera más "eficiente" de hacer esto que haciendo un ciclo for a través de cualquier otro índice? Mi código era pequeño, pero no se me ocurre cuánto más "eficiente" podría obtenerse que un ciclo ... Supongo que podría haber una forma de usar XOR para evitar un ciclo, pero no puedo descárgalo.

Gracias!

Fuente

2011-01-25 Mehrdad

It 'wasn't' una pregunta? No lo veo ... –

@MrDisappointment Sospecho que si fuera una pregunta, Mehrdad estaría violando un acuerdo escrito o no compartiría la pregunta con otros. – Phrogz

@MrDisappointment: LOL lo siento, error; XD fijo ... @Phrogs: No hubo tal acuerdo ni nada, era una feria abierta de carrera con cien o dos personas; sin firmas ni nada por el estilo. :) – Mehrdad

Puede usar una tabla de búsqueda de 256 entradas.

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

Fuente

2011-01-25 00:32:42

+1. Si es la velocidad que desea, la tabla de búsqueda es la respuesta. Utiliza 256 bytes para una tabla de búsqueda, pero, como ocurre con la mayoría de las optimizaciones, es una compensación de espacio/tiempo. Si no quiere perder ese espacio, es poco probable que obtenga más rápido que un par de turnos y operaciones de bits. – paxdiablo

Tenga cuidado con el tipo 'signed', por supuesto. –

+1 Creo que es la segunda solución, ya que es la más concisa, y muy eficiente ... argh, tan fácil y, sin embargo, tan difícil. :( – Mehrdad

Búsqueda de tablas (a menos que haya alguna solución particular específica de NVIDA que esté buscando).

Fuente

2011-01-25 00:32:06

No estaba buscando una solución específica para NVIDIA, pero estaba buscando un código pequeño * y * rápido ... ¿la solución de búsqueda de tabla contaría? (aunque hay que admitir que no pensé en ello ...) – Mehrdad

@Mehrdad: la búsqueda de tablas es solo "lo primero que viene a la mente" con este tipo de problemas. Ciertamente podría haber un truco de bits mejor e inteligente. También podría considerar una tabla más pequeña de 16 bytes (o incluso 8 bytes quizás) combinada con algunas operaciones de cambio/máscara para buscar 4 bits a la vez. No estoy seguro de dónde podría estar el punto dulce. –

Algo como esto debería funcionar

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

i >> 1 turnos todo en 1 bit a la derecha, y deja sólo & 01010101 bits a siquiera posición.
La segunda parte se ocupa de las posiciones de bits impares en el mismo fasion.

No estoy seguro de lo eficiente que es.

Fuente

2011-01-25 00:32:59

+1 Esto es muy inteligente, gracias ... Estaba pensando en alguna forma de usar los cambios de bit, pero no pude resolverlo. Genial !! :) – Mehrdad

Sí, prefiero el | operador al operador + pero la misma solución. Y, por supuesto, su código es pseudo para la representación de base 2. – CashCow

Dado que solo hay 256 combinaciones posibles en un byte, esto parece ser un buen candidato para usar una solución basada en tabla de búsqueda para cualquier momento cuando la velocidad de ejecución continua es más importante que el precalculo original y/o la utilización total de la memoria.

Por ejemplo:

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

Fuente

2011-01-25 00:34:12 Coxy

Definitivamente no es un código pequeño. :( – Mehrdad

Definitivamente no estoy de acuerdo, pero recuerde que el código pequeño no siempre es eficiente y el código eficiente no siempre es pequeño – Coxy

La caché falla es un problema con las tablas de búsqueda en general. Para cosas tan pequeñas, es más fácil calcular el resultado Creo. –

Sin tabla de búsqueda (o para generar la cosa en el primer lugar) también puede:

desplazamiento a la izquierda y Y con la máscara izquierda bits (10101010)
desplazamiento a la derecha y Y con la máscara de bits a la derecha (01010101)
O resultados en conjunto.

desplazado a la izquierda es 01 10 11 00 enmascarado con 10101010 nos da 00 10 10 00

desplazada hacia la derecha (original) es enmascarado con 01010101 nos da 01 01 00 01

O nuestros resultados, junto

Así que en C o C++ que podría hacer

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

Sólo tiene que ejecutar que para todos los valores de 0x00 a 0xFF (asegurarse de que su ciclo termina!) Para generar su "mesa".

Fuente

2011-01-25 15:20:20 CashCow

¡Gracias por la explicación! – Chayemor

Por número entero de 32 bits en Java ..

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

}

Si está trabajando con 64 bits, lo que se necesita para cambiar la máscara ..

Fuente

2014-07-19 17:52:26

Intercambiar cada par de bits en el byte

Respuesta

Cuestiones relacionadas