Back to For Beginners

How to reverse a bit-sequence?

For Beginners

Started by Xmolch June 19, 2003 02:36 PM

6 comments, last by Xmolch 20 years, 10 months ago

Xmolch

122

Author

June 19, 2003 02:36 PM

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.

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

Arek the Absolute

350

June 19, 2003 03:04 PM

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

-Arek the Absolute"The full quartet is pirates, ninjas, zombies, and robots. Create a game which involves all four, and you risk being blinded by the sheer level of coolness involved." - Superpig

Xmolch

122

Author

June 19, 2003 03:07 PM

Thank you for that idea!

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

doho

378

June 19, 2003 03:30 PM

// reverse_bits_tableconst 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_slowunsigned 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_fastunsigned char reverse_bits_fast(unsigned char b){	return reverse_bits_table[b];}

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

Shannon Barber

1,684

June 19, 2003 03:39 PM

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]

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

haro

502

June 19, 2003 03:55 PM

Fun problem. Decided to code my own solution.

#define TYPE unsigned charTYPE 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.