Come invertire i bit di un byte?

2

Prova a ottenere questo libro, c'è un intero capitolo sul bit reversione: Hacker's Delight. Ma per favore controlla prima i contenuti se questo ti si addice.

fonte

2009-11-06 16:06:03

8

Il modo più veloce, ma anche quello che richiede più spazio è una ricerca, in cui ogni valore possibile di un byte (256 se si va per l'intero intervallo), è associato al suo equivalente "invertito".

Se avete solo un paio di questi byte da gestire, gli operatori bit-saggio farà, ma che sarà più lento, forse qualcosa di simile:

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; 
}

fonte

2009-11-06 16:07:01 mjv

+0

Storicamente, ho scoperto che avere una tabella di ricerca a 256 byte è il modo più veloce per ottenerlo dato che è solo una ricerca. 256 byte non è molto spazio da dedicare a qualcosa di simile se deve essere veloce. Anche se la funzione reverseBits di cui sopra è tanto piccola e stretta quanto è possibile ottenere il codice senza una ricerca. Anche per una piccola ottimizzazione potresti cambiare il primo {$ out | = 0x80;} a {$ out = 0x80;} come sai che la prima volta che stai ORing con 0. – skirmish

+0

@skirmish, d'accordo, mi piacerebbe utilizzare la matrice di ricerca nella maggior parte dei casi. Una soluzione intermedia, sarebbe quella di avere un array più piccolo, per 4 bit, e fare due ricerche con la moltiplicazione/divisione associata per il bit-quad più a sinistra). Questo modo di fare può anche essere usato per trattare gli interi, piuttosto che i byte, con . (Il lato negativo dell'approccio di ricerca è che il suo fabbisogno di spazio cresce in modo esponenziale, per cui l'apparaoch codificato linearmente (w/riguarda il numero di bit) – mjv

18

L'approccio dritto in avanti è quello di eseguire 8 maschere, 8 ruota e 7 aggiunte:

$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;

fonte

2009-11-06 16:07:55

+1

Che ha due upvotes? –

+1

@Kinopiko: 3 upvotes, con il mio. una soluzione migliore, postala e riceverai anche il mio voto! – Seb

+0

Beh, sta rispondendo alla domanda :-) –

14

Se avete già i bit, sotto forma di una stringa, utilizzare strrev.

In caso contrario, convertire prima il byte nella sua rappresentazione binaria utilizzando decbin, quindi invertire utilizzando strrev, quindi tornare a byte (se necessario) utilizzando bindec.

fonte

2009-11-06 16:09:16 Konamiman

+1

La migliore risposta IMO che funzionerà per i casi generali. Quel bit shifting, rotazione ecc sono solo mirati al valore di esempio dato e non funzioneranno con stringhe binarie casuali .. – Lukman

+0

+1 Questo è quello che avrei suggerito se non avessi sbagliato la comprensione iniziale. –

+0

Sono davvero curioso di sapere perché sono stato downvoted qui ... – Konamiman

14

Controllare la sezione su sequenze di inversione di bit in Bit Twiddling Hacks. Dovrebbe essere facile adattare una delle tecniche in PHP.

Mentre probabilmente non pratico per PHP, c'è un particolare affascinante con 3 operazioni a 64 bit:

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

fonte

2009-11-06 16:19:02

+0

Puoi spiegare cosa significa "ULL" qui? – Mask

+4

@mask che è un unsigned long long, il suffisso dice al compilatore che ciò che procede è un letterale intero senza segno a 64 bit. – PeterAllenWebb

+0

perché è una soluzione se non è pratico per php? – denoise

1

Non sono d'accordo con l'utilizzo di una tabella di guardare in alto, come (per gli interi più grandi) la quantità di tempo necessario per caricarlo nella memoria supera la prestazione di elaborazione.

Io uso anche un approccio bit per bit di mascheramento di una soluzione O (log), che si presenta come:

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))

Il vantaggio di questo approccio è che gestisce la dimensione della vostra intero come argomento

in php questo potrebbe essere simile:

function bitrev($bitstring, $size){ 

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

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

a meno che non ho fatto un casino la mia php qualche parte :(

fonte

2009-11-06 17:00:03 tzenes

+0

se si sta eseguendo l'operazione solo una volta, una tabella di ricerca non è buona. Ma se è un'operazione frequente, dovrebbe superare qualsiasi altro approccio. –

3

Questo è O (n) con la lunghezza del bit. Basti pensare all'input come stack e scrivere sullo stack di output.

Il mio tentativo di scrivere questo in 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; 
}

fonte

2009-11-06 17:35:06

1

Alcune persone sono state suggerendo una tabella di ricerca, mentre sto facendo uno:

[ 
     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]

Ed ecco una versione carattere:

[ 
    "\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)];

fonte

2017-09-08 12:00:28 FluorescentGreen5

Come invertire i bit di un byte?

risposta

Problemi correlati