Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Xmolch

How to reverse a bit-sequence?

This topic is 5577 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Here is an example: Bit-sequence: 111001011 Result(when reversed): 110100111 Is there any function that does this for me? If not, how would you solve this problem? ------------------------------ Suffering binds you to reality.

Share this post


Link to post
Share on other sites
Advertisement
That I''m aware of, there''s no function to do that. But I suppose you could do it pretty easily in a simple for loop. Something like this, I imagine.


unsigned char ReverseBits(unsigned char number){

unsigned char temp = 0;

for (int loop = 0; loop < 8; loop++){
int bit = (number&(1<<loop))>>loop;
temp |= bit<<(7-loop);
}

return temp;

}


Of course, that function assumes it''s working with an 8 bit number, but it''s pretty straightforward to change that for other bit depths too.

-Arek the Absolute

Share this post


Link to post
Share on other sites

// reverse_bits_table

const unsigned char reverse_bits_table[256] =
{
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
};

// reverse_bits_slow

unsigned char reverse_byte_slow(unsigned char b)
{
unsigned char r;

#define REVERSE_BIT { r |= b & 128; b <<= 1; r >>= 1; }

REVERSE_BIT
REVERSE_BIT
REVERSE_BIT
REVERSE_BIT
REVERSE_BIT
REVERSE_BIT
REVERSE_BIT

r |= b & 128;

return r;
#undef REVERSE_BIT
}

// reverse_bits_fast

unsigned char reverse_bits_fast(unsigned char b)
{
return reverse_bits_table[b];
}


[edited by - doho on June 19, 2003 4:36:06 PM]

Share this post


Link to post
Share on other sites
This will reverse an arbitrary number of bits, upto 32. You can expand the pattern to 64 bits if you need more.

e.g. 0x01 becomes 0x80 when you reverse 8bits (as opposed to 0x80000000 which happen when you reverse 32bits). The i>>= 32-nbits takes care of this.


inline u32 ReverseBits(u32 i, u32 nbits)
{
i = ((i & 0x55555555) << 1 ) | ((i & 0xAAAAAAAA) >> 1 );
i = ((i & 0x33333333) << 2 ) | ((i & 0xCCCCCCCC) >> 2 );
i = ((i & 0x0F0F0F0F) << 4 ) | ((i & 0xF0F0F0F0) >> 4 );
i = ((i & 0x00FF00FF) << 8 ) | ((i & 0xFF00FF00) >> 8 );
i = ((i & 0x0000FFFF) << 16) | ((i & 0xFFFF0000) >> 16);
i >>= 32-nbits;
return x;
}




[edited by - Magmai Kai Holmlor on June 19, 2003 4:39:56 PM]

Share this post


Link to post
Share on other sites
Fun problem. Decided to code my own solution.


#define TYPE unsigned char
TYPE reverse( TYPE val )
{
TYPE temp = 0;
for(int i = 0; i < sizeof(TYPE)*8; i++)
if( val & (1 << i) )
temp |= 1 << (sizeof(TYPE)*8 - i - 1);
return temp;
}


I think its the best because of simplicity.

EDIT: Made it even easier.



[edited by - haro on June 19, 2003 4:56:18 PM]

Share this post


Link to post
Share on other sites
No, it really wasn''t. I was just interested in the solution, out of curiosity..

------------------------------
Suffering binds you to reality.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!