tengo una arbitraria 8-bit binario número por ejemplo, 11101101Intercambio de par de bits en un byte
tengo que cambiar todo el par de bits como:
antes de intercambiar: 11-10-11-01 Después de cambiar : 11-01-11-10
¡Me lo preguntaron en una entrevista!
En pseudo-código:
x = ((x & 0b10101010) >> 1) | ((x & 0b01010101) << 1)
Funciona mediante la manipulación de los bits de baja y bits altos de cada par de bits por separado y después combinar el resultado:
x & 0b10101010 extrae el alto bit de cada par, y luego >> 1 lo desplaza a la posición de bit bajo.(x & 0b01010101) << 1 extrae el bit bajo de cada par y lo desplaza a la posición de bit alto.Como no todos los idiomas le permiten escribir literales binarios directamente, se podría escribir en, por ejemplo hexadecimal:
Binary Hexadecimal Decimal 0b10101010 0xaa 170 0b01010101 0x55 85
Dado que no todos los idiomas respetan el patrón 0b ..., es probable que valga la pena señalar que es 0xAA y 0x55 en hexadecimal respectivamente. – userx
@userx: +1 Sí, eso es definitivamente digno de mención. Adicional. –
Gracias Mark. ¡Ese es un método increíble! – RaviPathak
b = (a & 170 >> 1) | (a & 85 << 1)
Esto es completamente ilegible; Además, es ineficiente e incluso incorrecto para casos extremos. Dividir por dos no es equivalente a un desplazamiento a la derecha de un bit para los números negativos. – tdammers
igual que tdammers answer pero es más limpio y explícitamente binario, mientras que usted usa números decimales. – vulkanino
-1 muy ilegible – Tomas
Me primer código es longhand '- es decir, en varias etapas obvias, explícitas, y usarlo para validar que las pruebas unitarias que tenía en su lugar estaban funcionando correctamente, y sólo se mueven a mayor soluciones esotéricas de manipulación de bits si tuviera una necesidad de rendimiento (y ese rendimiento adicional fue entregado por dichas mejoras)
Código para personas primero, computadoras en segundo lugar.
-1 que no responde a la pregunta en absoluto – Tomas
10101010 y 01010101).Ejemplo de 16 bits (código no real):
short swap_bit_pair(short i) {
return ((i & 0101010110101010b) >> 1) | ((i & 0x0101010101010101b) << 1));
}
Um .. Creo que quiere decir 0xAA en lugar de 0x10101010 (0xAA es 10101010 en binario) y 0x55 en lugar de 0x01010101. Bueno para un byte de todos modos. 0xAAAA y 0x5555 respectivamente para un corto. – userx
Sí, ya editó el pseudocódigo tipo C para usar binario en su lugar. La pregunta original dice 8 bits de todos modos, entonces ... – tdammers
La solución más elegante y flexible es, como otros han dicho, para aplicar una máscara 'peine' tanto a los bits pares e impares por separado y luego, después de haberlos desplazado a la izquierda y a la derecha, respectivamente, un lugar para combinarlos utilizando bitwise o.
Otra solución que quizás desee considerar aprovecha el tamaño relativamente pequeño de su tipo de datos.Puede crear una tabla de consulta de 256 valores que se estáticamente inicializado a los valores que desee como salida a la entrada:
const unsigned char lookup[] = { 0x02, 0x01, 0x03, 0x08, 0x0A, 0x09, 0x0B ...
se coloca Cada valor de la matriz para representar la transformación del índice. Así que si a continuación, hace esto:
unsigned char out = lookup[ 0xAA ];
out contendrá 0x55
Esto es más complicado y menos flexible que el primer enfoque (lo que si quieres pasar de 8 bits a 16?) Pero tiene el enfoque de que será considerablemente más rápido si se realiza una gran cantidad de estas operaciones.
Supongamos que su número es num.
En primer lugar encontrar la posición de bit, incluso:
num & oxAAAAAAAA
Segundo paso encontrar el bit de posición extraña:
num & ox55555555
posición de cambio tercera etapa extraña posición de bit de posición e incluso la posición de bit en la posición impar bits:
Even = (num & oxAAAAAAAA)>>1
Odd = (num & 0x55555555)<<1
El último paso ... result = Even | Odd
Imprimir resultado
¿Cuál es la pregunta? – JamesM
Perdón por la primera respuesta que di si te confundió. Leí completamente tu antes/después mal. – colithium
@JamesM: Lo siento, si no es evidente, pero la pregunta es: en un byte, empareja los bits para, por ejemplo, si el byte es 10101100, entonces el emparejamiento de los bits se verá como '10 - 10 - 11 - 00'. Ahora, si intercambiamos los pares individuales, se convertiría en '01 - 01 - 11 - 00'. Necesitaba el mecanismo para implementar el intercambio – RaviPathak