Bit reversal of an integer, ignoring integer size and limb

Question

An integer typedef is given:

typedef unsigned int TYPE; 

or

 typedef unsigned long TYPE; 

I have the following code to access the bits of an integer:

 TYPE max_bit= (TYPE)-1; void reverse_int_setup() { TYPE bits= (TYPE)max_bit; while (bits <<= 1) max_bit= bits; } TYPE reverse_int(TYPE arg) { TYPE bit_setter= 1, bit_tester= max_bit, result= 0; for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1) if (arg & bit_tester) result|= bit_setter; return result; } 

First you need to run run_int_setup (), which stores the integer with the highest bit, then any call to reverse_int (arg) returns arg with the bits that were canceled (for use as a key to the binary tree, taken from the growing counter, but more or less inconsequential).

Is there an agronizing method that, at compile time, has the correct value for max_int after calling reverse_int_setup (); Otherwise, is there an algorithm that you think is better / more compact than the one I have for reverse_int ()?

Thanks.

Answer 1

 #include<stdio.h> #include<limits.h> #define TYPE_BITS sizeof(TYPE)*CHAR_BIT typedef unsigned long TYPE; TYPE reverser(TYPE n) { TYPE nrev = 0, i, bit1, bit2; int count; for(i = 0; i < TYPE_BITS; i += 2) { /*In each iteration, we swap one bit on the 'right half' of the number with another on the left half*/ count = TYPE_BITS - i - 1; /*this is used to find how many positions to the left (and right) we gotta move the bits in this iteration*/ bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/ bit1 <<= count; /*Shift it to where it belongs*/ bit2 = n & 1<<((i/2) + count); /*Find the 'left half' bit*/ bit2 >>= count; /*Place that bit in bit1 original position*/ nrev |= bit1; /*Now add the bits to the reversal result*/ nrev |= bit2; } return nrev; } int main() { TYPE n = 6; printf("%lu", reverser(n)); return 0; } 

This time I used the idea of ​​“number of bits” from TK, but made it somewhat more portable, not assuming that the byte contains 8 bits and uses the CHAR_BIT macro instead. Now the code is more efficient (with removal of the inner loop). Hope this time the code will be a little less cryptic. :)

The need to use count is that the number of positions by which we must shift the bit changes at each iteration - we must transfer the rightmost bit to 31 positions (assuming a 32-bit number), the second rightmost bit to 29 positions and t .d. Therefore, the counter should decrease with each iteration as i increases.

Hope this information is helpful in understanding the code ...

Answer 2

The following program serves to demonstrate a more compact algorithm for reversing bits, which can be easily extended to handle 64-bit numbers.

 #include <stdio.h> #include <stdint.h> int main(int argc, char**argv) { int32_t x; if ( argc != 2 ) { printf("Usage: %s hexadecimal\n", argv[0]); return 1; } sscanf(argv[1],"%x", &x); /* swap every neigbouring bit */ x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1; /* swap every 2 neighbouring bits */ x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2; /* swap every 4 neighbouring bits */ x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4; /* swap every 8 neighbouring bits */ x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8; /* and so forth, for say, 32 bit int */ x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16; printf("0x%x\n",x); return 0; } 

This code should not contain errors and was tested using 0x12345678 to get the correct answer 0x1e6a2c48.

Answer 3

 typedef unsigned long TYPE; TYPE reverser(TYPE n) { TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2; int count; for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2) { /*In each iteration, we swap one bit on the 'right half' of the number with another on the left half*/ k = 1<<i; /*this is used to find how many positions to the left (or right, for the other bit) we gotta move the bits in this iteration*/ count = 0; while(k << 1 && k << 1 != 1) { k <<= 1; count++; } nrevbit1 = n & (1<<(i/2)); nrevbit1 <<= count; nrevbit2 = n & 1<<((i/2) + count); nrevbit2 >>= count; nrev |= nrevbit1; nrev |= nrevbit2; } return nrev; } 

This works fine in gcc on Windows, but I'm not sure if it is completely platform independent. A few problematic questions:

• condition in the for loop - it assumes that when you leave shift 1 behind the left-most bit, you will get either 0 with the loss of 1 (what would I expect and what old old Turbo C gives iirc), or 1 circle, and you get 1 (which is similar to gcc behavior).

• condition in the inner while loop: see above. But here a strange thing happens: in this case gcc seems to allow 1 to drop out, not around!

The code can be cryptic: if you are interested and need an explanation, please feel free to ask - I will post it somewhere.

Answer 4

@ ΤΖΩΤΖΙΟΥ

In response to the comments of ΩΤ, I present a modified version above, which depends on the upper limit for the bit width.

 #include <stdio.h> #include <stdint.h> typedef int32_t TYPE; TYPE reverse(TYPE x, int bits) { TYPE m=~0; switch(bits) { case 64: x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16; case 32: x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16; case 16: x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8; case 8: x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4; x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2; x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1; } return x; } int main(int argc, char**argv) { TYPE x; TYPE b = (TYPE)-1; int bits; if ( argc != 2 ) { printf("Usage: %s hexadecimal\n", argv[0]); return 1; } for(bits=1;b;b<<=1,bits++); --bits; printf("TYPE has %d bits\n", bits); sscanf(argv[1],"%x", &x); printf("0x%x\n",reverse(x, bits)); return 0; } 

Notes:

• gcc will warn about 64-bit constants
• printfs also generates warnings.
• If you need more than 64 bits, the code should be simple enough to extend

I apologize in advance for the crimes that I committed above - gracious kind sir!

Answer 5

There's a good collection of “Twiddling Hacks Bit”, including many simple and not-so-simple C inverse bit conversion algorithms encoded in C at http://graphics.stanford.edu/~seander/bithacks.html .

I personally like the "Obvious" algorithm ( http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious ) because, well, that is obvious. Some of the others may require less instructions to complete. If I really need to optimize the situation, I can choose not so obvious, but faster versions. Otherwise, for readability, maintainability and mobility, I would choose the Obvious.

Answer 6

Here is a more accessible option. Its advantage is its ability to work in situations where the bit length of the value that needs to be changed - the code word - is unknown, but it is guaranteed not to exceed the value that we will call maxLength. A good example of this case is Huffman code decompression.

The code below works with code words from 1 to 24 bits long. It is optimized for fast execution on Pentium D. Note that it accesses the lookup table up to 3 times per use. I experimented with many variations that reduced this number to 2 at the expense of a larger table (4096 and 65,536 entries). This version with a 256-byte table was a clear winner, partly because it is so useful that the table data is in caches, and possibly also because the processor has an 8-bit table search / translation instruction.

 const unsigned char table[] = { 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}; const unsigned short masks[17] = {0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00}; unsigned long codeword; // value to be reversed, occupying the low 1-24 bits unsigned char maxLength; // bit length of longest possible codeword (<= 24) unsigned char sc; // shift count in bits and index into masks array if (maxLength <= 8) { codeword = table[codeword << (8 - maxLength)]; } else { sc = maxLength - 8; if (maxLength <= 16) { codeword = (table[codeword & 0X00FF] << sc) | table[codeword >> sc]; } else if (maxLength & 1) // if maxLength is 17, 19, 21, or 23 { codeword = (table[codeword & 0X00FF] << sc) | table[codeword >> sc] | (table[(codeword & masks[sc]) >> (sc - 8)] << 8); } else // if maxlength is 18, 20, 22, or 24 { codeword = (table[codeword & 0X00FF] << sc) | table[codeword >> sc] | (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1)); } } 

Answer 7

What about:

 long temp = 0; int counter = 0; int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary) while(value > 0) // loop until value is empty { temp <<= 1; // shift whatever was in temp left to create room for the next bit temp |= (value & 0x01); // get the lsb from value and set as lsb in temp value >>= 1; // shift value right by one to look at next lsb counter++; } value = temp; if (counter < number_of_bits) { value <<= counter-number_of_bits; } 

(I assume that you know how many bit values ​​are stored and stored in number_of_bits)

Obviously temp should be the longest imaginary data type, and when you copy temp back to the value, all extraneous bits in temp should magically disappear (I think!).

Or, path 'c' would have to say:

 while(value) 

your choice

Answer 8

We can save the results of reversing all possible 1 byte sequences in an array (256 separate records), and then use the search combination in this table and some org logic to get the opposite integer.

Answer 9

Here is a variation and correction of the TK solution, which may be clearer than the solutions using sundar. It takes individual bits from t and pushes them into return_val:

 typedef unsigned long TYPE; #define TYPE_BITS sizeof(TYPE)*8 TYPE reverser(TYPE t) { unsigned int i; TYPE return_val = 0 for(i = 0; i < TYPE_BITS; i++) {/*foreach bit in TYPE*/ /* shift the value of return_val to the left and add the rightmost bit from t */ return_val = (return_val << 1) + (t & 1); /* shift off the rightmost bit of t */ t = t >> 1; } return(return_val); } 

Answer 10

The general approach ball will work for objects of any type of any size, this will invert the bytes of the object, and vice versa - the order of the bits in each byte. In this case, the bit level algorithm is tied to a specific number of bits (byte), and the logic of "variables" (in size) rises to the level of whole bytes.

Answer 11

In case the bit-reverse is time critical and mainly in combination with FFT, it is best to store the entire bit-reverse array. In any case, this array will be smaller in size than the unity roots, which must be previously calculated in the Cooley-Tuki FFT algorithm. An easy way to calculate an array is:

 int BitReverse[Size]; // Size is power of 2 void Init() { BitReverse[0] = 0; for(int i = 0; i < Size/2; i++) { BitReverse[2*i] = BitReverse[i]/2; BitReverse[2*i+1] = (BitReverse[i] + Size)/2; } } // end it all 

Answer 12

Here's my generalization of the freespace solution (in case we get 128-bit machines one day). This leads to fail-safe code when compiling with gcc -O3 and is obviously insensitive to the definition of foo_t on machines with a tier. Unfortunately, this depends on the shift being 2!

 #include <limits.h> #include <stdio.h> typedef unsigned long foo_t; foo_t reverse(foo_t x) { int shift = sizeof (x) * CHAR_BIT / 2; foo_t mask = (1 << shift) - 1; int i; for (i = 0; shift; i++) { x = ((x & mask) << shift) | ((x & ~mask) >> shift); shift >>= 1; mask ^= (mask << shift); } return x; } int main() { printf("reverse = 0x%08lx\n", reverse(0x12345678L)); }