Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

Reverse Bit Operations

Status
Not open for further replies.

chillidog23

Technical User
Jul 4, 2007
4
CA
Hi,
I am looking for a C++ function to reverse the bits of a variable. For example, assume testvar = 11100110, then reverse(testvar) = 01100111. Does anyone know of such a function? Thanks.
 
I should've mentioned that testvar is represented as a binary above, i.e. testvar = 11100110, and reverse(testvar) = 01100111.
 
Sorry, I messed up again: testvar = 11100110b, and reverse(testvar) = 01100111b
 
Of course, no such library function but there are full set of bitwise operators in C and C++: <<, >>, &, |, ^, ~ (+ loop statements;).
You may use more sofisticated approach with byte by byte substitution too.
Alas, no binary constants with b suffix in C++...
 
If you need to do this very fast for any reason, it would be worth making a 256-byte lookup table with the results already reversed. Even if you're reversing much larger numbers than 8 bits, the look-up would pay off as you can reverse the bytes of a big number very easily, and then reverse the bits in each byte using the look-up. Reversing bits by repeated shifts and tests is quite a lot of cycles per byte.
 
Isn't there also an assembly instruction on some chips that reverses bits? Is so, you could use that (as long as you don't care about multi-platformedness).
 
There wasn't in the 8086 family up to the pentium. I don't know if there's something whizzy since then. There were bscan instructions, forwards and backwards, that found the position of a bit in a register, but they were incredibly, outrageously slow; basically they were a repeated 1-bit shift and test, and ran just about as efficiently.
 
Well, look at this (portable - 16..24..32..64..;) monster:
Code:
static unsigned int rb[256] = /* uint contains 8*n bits */
{
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,
};
/* this routine ignores byte structure (and addressing scheme) */
unsigned int revbits(unsigned int u)
{
  int	i, j, k;
  unsigned int a, b;
  unsigned int r = 0;

  static int n;
  static unsigned int uu = 0x100u;

  /* octets per unsigned int?
   it's interesting: can't calc with preprocessor!
  */

  if (uu) /* the 1st call... */
  for (n = 2; uu <<= 8; ++n) /* not thread-safe code! */
     ;
  k = n;

  for (i = 0, j = 8*(n-1); k > 1; k -= 2, i += 8, j -=8)
  {
    a = rb[(u >> i)&0xFFu];
    b = rb[(u >> j)&0xFFu];
    r |= (b << i);
    r |= (a << j); /* next two reverted octets swapped */
  }
  if (k)	/* (now exotic system with odd num of octets per uint;) */
     r |= (rb[(u >> i)&0xFFu] << i);
  return r;
}
 
The obfuscated answers are truly remarkable but I'd love to see their execution times compared to simple look-ups and a well-placed bswap. Multiplication! Good gracious.
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top