How to reverse bits of a byte ?

Question

Best in PHP,

for example,

11011111 ==> 11111011

Answer 1

Try to get this book, there is whole chapter about bits reversion: Hacker's Delight. But please check content first if this suits you.

Answer 2

In your example you are not doing reversal. See PHP documentation on this for shift right bitwise operation.

If you were doing a true reversal, you'd use the NOT operation like so:

$test = b'111000111';
$rtest = ~$test;

The b'1111' above requires PHP 5.3 in order to use binary strings.

Answer 3

The quickest way, but also the one requiring more space is a lookup, whereby each possible value of a byte (256 if you go for the whole range), is associated with its "reversed" equivalent.

If you only have a few such bytes to handle, bit-wise operators will do but that will be slower, maybe something like:

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 & 0x12) { $out |= 0x04;}
  if ($in & 0x14) { $out |= 0x02;}
  if ($in & 0x18) { $out |= 0x01;}
  return $out;
}

Answer 4

Make a print out of the bits onto a piece of paper. Hold the piece of paper up to a mirror and then type them in in reverse order, using the mirror reflection. Simple, really.

Answer 5

The straight forward approach is to perform 8 masks, 8 rotates, and 7 additions:

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

Answer 6

If you have already the bits in the form of a string, use strrev.

If not, convert first the byte to its binary representation by using decbin, then reverse using strrev, then go back to byte (if necessary) by using bindec.

Answer 7

Check the section on reversing bit sequences in Bit Twiddling Hacks. Should be easy to adapt one of the techniques into PHP.

While probably not practical for PHP, there's a particularly fascinating one using 3 64bit operations:

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

Answer 8

I disagree with using a look up table as (for larger integers) the amount of time necessary to load it into memory trumps processing performance.

I also use a bitwise masking approach for a O(logn) solution, which looks like:

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

The advantage of this approach is it handles the size of your integer as an argument

in php this might look like:

function bitrev($bitstring, $size){

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

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

unless I screwed up my php somewhere :(

Answer 9

This is O(n) with the bit length. Just think of the input as a stack and write to the output stack.

My attempt at writing this 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;
   }
}