How to reverse bits of a byte?

For example, in PHP, how would I reverse the bits of the byte 11011111开发者_高级运维 to 11111011?

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.

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;

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;

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 & 0x20) $out |= 0x04;
  if ($in & 0x40) $out |= 0x02;
  if ($in & 0x80) $out |= 0x01;

  return $out;
}

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

    return $inBits;
}

Some people have been suggesting a lookup table, while I have been making one:

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

And here's a character version:

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

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

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 :(

I had the same challenge! If we're really just talking about 8-bit unsigned, then the quickest way, according to my tests, is to use an array (0 - 255), which value holds the reverse int value.

$lsb = [
    0 => 0,
    1 => 128,
    2 => 64,
    3 => 192,
    4 => 32,
    5 => 160,
    ...
    252 => 63,
    253 => 191,
    254 => 127,
    255 => 255,
];

function getByteLSBF($lsb, $byte) {
    return $lsb[$byte];
}

The next fastest approach was surprisingly the string conversion approach described by @Konamiman (about the third slower) - which really baffled me since the direct bit manipulations were the slowest (more than double slower):

function getByteLSBfirst(int $byte): int
{
   $lsbFirst = 0;
   for ($i = 0; $i < 8; $i++) {
      $lsbFirst = ($lsbFirst << 1) | ($byte & 1);
      $byte = $byte >> 1;
   }

   return $lsbFirst;
}

I tested all three approaches with the same random int (byte) in 10,000 iterations simultaneously.

In 1984, I came up with this solution (on a Commodore Vic20 and memory was a premium back then). So my two-line calculation in BASIC did the trick. Simple, quick and no memory-hogging table.

Since =11001111=207, input this in W.

The program returns V = 243... = 11110011

PROGRAM:

input w: v=0: for x=0 to 7
if w>(2^(7-x))-1 then v=v+(2^x): w=w-(2^(7-x))
next
print v