Cómo invertir bits de un byte?

2

Intentar obtener este libro, hay capítulo entero acerca de los bits de reversión: Hacker's Delight. Pero compruebe el contenido primero si esto le conviene.

Fuente

2009-11-06 16:06:03

8

La manera más rápida, pero también la que requiere más espacio, es una búsqueda, en la que cada valor posible de un byte (256 si se usa para todo el rango) está asociado con su equivalente "invertido".

Si sólo tiene un par de dichos bytes de manejar, los operadores bit a bit van a hacer, pero que va a ser más lento, tal vez algo como:

function reverseBits($in) { 
    $out = 0; 

    if ($in & 0x01) $out |= 0x80; 
    if ($in & 0x02) $out |= 0x40; 
    if ($in & 0x04) $out |= 0x20; 
    if ($in & 0x08) $out |= 0x10; 
    if ($in & 0x10) $out |= 0x08; 
    if ($in & 0x20) $out |= 0x04; 
    if ($in & 0x40) $out |= 0x02; 
    if ($in & 0x80) $out |= 0x01; 

    return $out; 
}

Fuente

2009-11-06 16:07:01 mjv

+0

Históricamente, he encontrado que tener una tabla de búsqueda de 256 bytes es la forma más rápida de lograrlo, ya que solo es una búsqueda. 256 bytes no es mucho espacio para dedicar a algo como esto si necesita ser rápido. Aunque la función reverseBits anterior es tan pequeña y ajustada como puedes obtener el código sin tener que buscar. También para una optimización pequeña, puede cambiar el primer {$ out | = 0x80;} a {$ out = 0x80;} como sabe la primera vez que está haciendo un OR con 0. – skirmish

+0

@skirmish, de acuerdo, tendería a use la matriz de búsqueda en la mayoría de los casos. Una solución intermedia sería tener una matriz más pequeña, de 4 bits, y hacer dos búsquedas con la multiplicación/división asociada para el bit-quad más a la izquierda). Esta forma de hacer también se puede usar para tratar con decir enteros en lugar de bytes. (La desventaja del enfoque de búsqueda es que su requerimiento de espacio crece exponencialmente, por lo que el approo codificado es lineal (con respecto a la cantidad de bits). – mjv

18

El enfoque recta hacia adelante es llevar a cabo 8 máscaras, 8 gira y 7 adiciones:

$blah = $blah & 128 >> 7 + $blah & 64 >> 5 + $blah & 32 >> 3 + $blah & 16 >> 1 + $blah & 8 << 1 + $blah & 4 << 3 + $blah & 2 << 5 + $blah & 1 << 7;

Fuente

2009-11-06 16:07:55

+1

¿Eso tiene dos votos positivos? –

+1

@Kinopiko: 3 votos ascendentes, con el mío. una mejor solución. ¡Publique y obtendrá mi voto también! – Seb

+0

Bueno, está respondiendo la pregunta :-) –

14

Si ya tiene los bits en la forma de una cadena, utilice strrev.

De lo contrario, convierta primero el byte a su representación binaria usando decbin, luego invierta usando strrev, luego vuelva al byte (si es necesario) usando bindec.

Fuente

2009-11-06 16:09:16 Konamiman

+1

La mejor respuesta IMO que funcionará para casos generales. Esos cambios de bit, rotación, etc. solo se enfocan en el valor de ejemplo proporcionado y no funcionarán para cadenas binarias aleatorias. – Lukman

+0

+1 Esto es lo que habría sugerido si no hubiera fracasado en la comprensión inicial. –

+0

Tengo mucha curiosidad sobre por qué he sido votado aquí ... – Konamiman

14

Consulte la sección sobre secuencias de bits inversas en Bit Twiddling Hacks. Debería ser fácil adaptar una de las técnicas a PHP.

Aunque probablemente no sea práctico para PHP, hay una particularmente fascinante con 3 operaciones de 64 bits:

unsigned char b; // reverse this (8-bit) byte 
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

Fuente

2009-11-06 16:19:02

+0

¿Puede explicar qué significa "ULL" aquí? – Mask

+4

@mask que es un unsigned long long, el sufijo le dice al compilador que lo que procede es un literal entero sin signo de 64 bits. – PeterAllenWebb

+0

¿por qué es una solución si no es práctico para php? – denoise

1

no estoy de acuerdo con el uso de una tabla de consulta como (para los números enteros más grandes) la cantidad de tiempo necesario para cargarlo en la memoria supera el rendimiento del procesamiento.

También utilizo un enfoque a nivel de bit de enmascaramiento de una solución de O (log n), que se parece:

MASK = onescompliment of 0  
while SIZE is greater than 0 
    SIZE = SIZE shiftRight 1 
    MASK = MASK xor (MASK shiftLeft SIZE) 
    output = ((output shiftRight SIZE) bitwiseAnd MASK) bitwiseOR ((onescompliment of MASK) bitwiseAnd (output shfitLeft SIZE))

La ventaja de este enfoque es que maneja el tamaño de su número entero como argumento

en php ejemplo de esta situación:

function bitrev($bitstring, $size){ 

    $mask = ~0; 
    while ($size > 0){ 

    $size = $size >> 1; 
    $mask = $mask^($mask << $size); 
    $bitstring = (($bitstring >> $size) & $mask) | ((~$mask) & ($bitstring << $size)); 
    } 
}

menos que lo arruiné mi php algún lugar :(

Fuente

2009-11-06 17:00:03 tzenes

+0

si realiza la operación solo una vez, una tabla de búsqueda es incorrecta. Pero si se trata de una operación frecuente, debe superar cualquier otro enfoque. –

3

Esto es O (n) con la longitud del bit. Solo piense en la entrada como una pila y escriba en la pila de salida.

Mi intento de escribir esto en PHP.

function bitrev ($inBits, $bitlen){ 
    $cloneBits=$inBits; 
    $inBits=0; 
    $count=0; 

    while ($count < $bitlen){ 
     $count=$count+1; 
     $inBits=$inBits<<1; 
     $inBits=$inBits|($cloneBits & 0x1); 
     $cloneBits=$cloneBits>>1; 
    } 

    return $inBits; 
}

Fuente

2009-11-06 17:35:06

1

Algunas personas han sugerido una tabla de búsqueda, mientras que yo he estado haciendo una:

[ 
     0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 
     0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 
     0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 
     0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 
     0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 
     0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 
     0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 
     0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 
     0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 
     0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 
     0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 
     0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 
     0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 
     0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 
     0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 
     0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF, 
][$byte]

y aquí está una versión de caracteres:

[ 
    "\x00", "\x80", "\x40", "\xC0", "\x20", "\xA0", "\x60", "\xE0", "\x10", "\x90", "\x50", "\xD0", "\x30", "\xB0", "\x70", "\xF0", 
    "\x08", "\x88", "\x48", "\xC8", "\x28", "\xA8", "\x68", "\xE8", "\x18", "\x98", "\x58", "\xD8", "\x38", "\xB8", "\x78", "\xF8", 
    "\x04", "\x84", "\x44", "\xC4", "\x24", "\xA4", "\x64", "\xE4", "\x14", "\x94", "\x54", "\xD4", "\x34", "\xB4", "\x74", "\xF4", 
    "\x0C", "\x8C", "\x4C", "\xCC", "\x2C", "\xAC", "\x6C", "\xEC", "\x1C", "\x9C", "\x5C", "\xDC", "\x3C", "\xBC", "\x7C", "\xFC", 
    "\x02", "\x82", "\x42", "\xC2", "\x22", "\xA2", "\x62", "\xE2", "\x12", "\x92", "\x52", "\xD2", "\x32", "\xB2", "\x72", "\xF2", 
    "\x0A", "\x8A", "\x4A", "\xCA", "\x2A", "\xAA", "\x6A", "\xEA", "\x1A", "\x9A", "\x5A", "\xDA", "\x3A", "\xBA", "\x7A", "\xFA", 
    "\x06", "\x86", "\x46", "\xC6", "\x26", "\xA6", "\x66", "\xE6", "\x16", "\x96", "\x56", "\xD6", "\x36", "\xB6", "\x76", "\xF6", 
    "\x0E", "\x8E", "\x4E", "\xCE", "\x2E", "\xAE", "\x6E", "\xEE", "\x1E", "\x9E", "\x5E", "\xDE", "\x3E", "\xBE", "\x7E", "\xFE", 
    "\x01", "\x81", "\x41", "\xC1", "\x21", "\xA1", "\x61", "\xE1", "\x11", "\x91", "\x51", "\xD1", "\x31", "\xB1", "\x71", "\xF1", 
    "\x09", "\x89", "\x49", "\xC9", "\x29", "\xA9", "\x69", "\xE9", "\x19", "\x99", "\x59", "\xD9", "\x39", "\xB9", "\x79", "\xF9", 
    "\x05", "\x85", "\x45", "\xC5", "\x25", "\xA5", "\x65", "\xE5", "\x15", "\x95", "\x55", "\xD5", "\x35", "\xB5", "\x75", "\xF5", 
    "\x0D", "\x8D", "\x4D", "\xCD", "\x2D", "\xAD", "\x6D", "\xED", "\x1D", "\x9D", "\x5D", "\xDD", "\x3D", "\xBD", "\x7D", "\xFD", 
    "\x03", "\x83", "\x43", "\xC3", "\x23", "\xA3", "\x63", "\xE3", "\x13", "\x93", "\x53", "\xD3", "\x33", "\xB3", "\x73", "\xF3", 
    "\x0B", "\x8B", "\x4B", "\xCB", "\x2B", "\xAB", "\x6B", "\xEB", "\x1B", "\x9B", "\x5B", "\xDB", "\x3B", "\xBB", "\x7B", "\xFB", 
    "\x07", "\x87", "\x47", "\xC7", "\x27", "\xA7", "\x67", "\xE7", "\x17", "\x97", "\x57", "\xD7", "\x37", "\xB7", "\x77", "\xF7", 
    "\x0F", "\x8F", "\x4F", "\xCF", "\x2F", "\xAF", "\x6F", "\xEF", "\x1F", "\x9F", "\x5F", "\xDF", "\x3F", "\xBF", "\x7F", "\xFF", 
][ord($byte)];

Fuente

2017-09-08 12:00:28 FluorescentGreen5

Respuesta

Cuestiones relacionadas