How to reverse bits of a byte?

Question

For example, in PHP, how would I reverse the bits of the byte 11011111 to 11111011?

Your question needs a bit more clarification. For instance, is this a string or an actual integer whose bits you are attempting to flip? Context is very important when asking a question. — Topher Fangio, Nov 06 '09 at 16:04
@klez - +1 lol, you almost made me spit my coffee on my keyboard =P — Topher Fangio, Nov 06 '09 at 16:05
+1 to Kletz, but for this case you can do much simpler thing: assign with 0b11111011 value (for some architectures it could be much efficient ;) ). — Roman Nikitchenko, Nov 06 '09 at 16:10

Epsilon Prime · Answer 1 · 2010-01-07T17:26:57.713

17

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;

edited Jan 07 '10 at 17:26

answered Nov 06 '09 at 16:07

Epsilon Prime

4,576
5
31
34

1

@Kinopiko: 3 upvotes, with mine. Do you have a better solution. Post it and you'll get my vote too! – Seb Nov 06 '09 at 16:13
Well, it is answering the question :-) – Arthur Reutenauer Nov 06 '09 at 16:14
1

which mathematical theorem or algorithm is this answer based on? – Lukman Nov 06 '09 at 16:18
9

"The Principle of Brute Force" – Epsilon Prime Nov 11 '09 at 22:35
1

It's not a theorem, its literally just reconstructing a byte by rearranging the bits. I had to use parenthesis and OR instead of + though: `(128&n)>>7|(64&n)>>5|(32&n)>>3|(16&n)>>1|(8&n)<<1|(4&n)<<3|(2&n)<<5|(1&n)<<7` – bryc Feb 27 '19 at 22:29

score 17 · Answer 2 · answered Nov 06 '09 at 16:09

17

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.

answered Nov 06 '09 at 16:09

Konamiman

49,681
17
108
138

3

The best answer IMO that will work for general cases. Those bit shifting, rotation etc are just targeting the example value given and won't work for random binary strings .. – Lukman Nov 06 '09 at 16:17
+1 This is what I would have suggested had I not botched the initial understanding. – Kevin Peno Nov 06 '09 at 16:18

score 16 · Answer 3 · answered Nov 06 '09 at 16:19

16

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;

answered Nov 06 '09 at 16:19

Paul Dixon

295,876
54
310
348

Can you explain what "ULL" means here? – Mask Nov 07 '09 at 00:57
5

@mask that's an unsigned long long, the suffix tells the compiler that what proceeds it is a 64-bit unsigned integer literal. – PeterAllenWebb Nov 07 '09 at 04:13
3

why it's a solution if it is not practical for php? – denoise Jul 13 '17 at 12:52

score 10 · Answer 4 · edited Dec 08 '15 at 15:52

10

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

edited Dec 08 '15 at 15:52

answered Nov 06 '09 at 16:07

mjv

73,152
14
113
156

Historically, I've found that having a 256 byte lookup table is the fastest way to achieve it as it's just a lookup. 256 bytes is not a lot of space to dedicate to something like this if it need to be fast. Though the above reverseBits function is about as small and tight as you can get the code without having a lookup. Also for one small optimization you could change the first { $out |= 0x80;} to { $out = 0x80;} as you know that first time you're ORing with 0. – skirmish Nov 06 '09 at 16:33
@skirmish, agreed, I'd tend to use the lookup array in most cases. An intermediate solution, would be to have a smaller array, for 4 bits, and do two lookups with the associated multiplication/division for the leftmost bit-quad). This way of doing can also be used to deal with say integers rather that bytes. (The downside of the lookup approach is that its space requirement grows exponentially, whereby the coded appraoch linearly (w/ regards to the number of bits). – mjv Nov 06 '09 at 16:55

score 3 · Answer 5 · edited Jun 16 '14 at 11:56

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

FluorescentGreen5 · Answer 6 · 2017-09-08T15:23:46.477

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

score 2 · Answer 7 · answered Nov 06 '09 at 16:06

2

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

answered Nov 06 '09 at 16:06

Roman Nikitchenko

12,800
7
74
110

score 1 · Answer 8 · answered Nov 06 '09 at 17:00

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

if you're performing the operation just once, a lookup table is bad. But if it's a frequent operation, it should outperform any other approach. — Paul Dixon, Nov 06 '09 at 18:57

score 0 · Answer 9 · answered Sep 10 '22 at 15:02

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.

score -1 · Answer 10 · edited May 10 '21 at 18:33

-1

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

edited May 10 '21 at 18:33

Nick

4,820
18
31
47

answered May 09 '21 at 08:15

Sylvain Lariviere

1

How to reverse bits of a byte?

10 Answers10

Linked