<p>Given an integer typedef:</p>

<pre><code>typedef unsigned int TYPE;
</code></pre>

<p>or</p>

<pre><code>typedef unsigned long TYPE;
</code></pre>

<p>I have the following code to reverse the bits of an integer:</p>

<pre><code>TYPE max_bit= (TYPE)-1;

void reverse_int_setup()
{
    TYPE bits= (TYPE)max_bit;

    while (bits &lt;&lt;= 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&gt;&gt;= 1, bit_setter&lt;&lt;= 1)
        if (arg &amp; bit_tester)
            result|= bit_setter;
    return result;
}
</code></pre>

<p>One just needs first to run reverse_int_setup(), which stores an integer with the highest bit turned on, then any call to reverse_int(<em>arg</em>) returns <em>arg</em> with its bits reversed (to be used as a key to a binary tree, taken from an increasing counter, but that's more or less irrelevant).</p>

<p>Is there a platform-agnostic way to have in compile-time the correct value for max_int after the call to reverse_int_setup(); Otherwise, is there an algorithm you consider <em>better/leaner</em> than the one I have for reverse_int()?</p>

<p>Thanks.</p>

[{'answer_id': 63854, 'author': 'TK.', 'author_id': 1816, 'author_profile': 'https://Stackoverflow.com/users/1816', 'pm_score': 0, 'selected': False, 'text': "<p>How about:</p>\n\n<pre><code>long temp = 0;\nint counter = 0;\nint number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary)\n\nwhile(value &gt; 0)            // loop until value is empty\n{\n    temp &lt;&lt;= 1;             // shift whatever was in temp left to create room for the next bit\n    temp |= (value &amp; 0x01); // get the lsb from value and set as lsb in temp\n    value &gt;&gt;= 1;            // shift value right by one to look at next lsb\n\n    counter++;\n}\n\nvalue = temp;\n\nif (counter &lt; number_of_bits)\n{\n    value &lt;&lt;= counter-number_of_bits;\n}\n</code></pre>\n\n<p>(I'm assuming that you know how many bits value holds and it is stored in number_of_bits)</p>\n\n<p>Obviously temp needs to be the longest imaginable data type and when you copy temp back into value, all the extraneous bits in temp should magically vanish (I think!). </p>\n\n<p>Or, the 'c' way would be to say :</p>\n\n<pre><code>while(value)\n</code></pre>\n\n<p>your choice</p>\n"}, {'answer_id': 64023, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>We can store the results of reversing all possible 1 byte sequences in an array (256 distinct entries), then use a combination of lookups into this table and some oring logic to get the reverse of integer.</p>\n'}, {'answer_id': 64626, 'author': 'freespace', 'author_id': 8297, 'author_profile': 'https://Stackoverflow.com/users/8297', 'pm_score': 3, 'selected': False, 'text': '<p>The following program serves to demonstrate a leaner algorithm for reversing bits, which can be easily extended to handle 64bit numbers.</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;stdint.h&gt;\nint main(int argc, char**argv)\n{\n        int32_t x;\n        if ( argc != 2 ) \n        {\n                printf("Usage: %s hexadecimal\\n", argv[0]);\n                return 1;\n        }\n\n        sscanf(argv[1],"%x", &amp;x);\n        /* swap every neigbouring bit */\n        x = (x&amp;0xAAAAAAAA)&gt;&gt;1 | (x&amp;0x55555555)&lt;&lt;1;\n        /* swap every 2 neighbouring bits */\n        x = (x&amp;0xCCCCCCCC)&gt;&gt;2 | (x&amp;0x33333333)&lt;&lt;2;\n        /* swap every 4 neighbouring bits */\n        x = (x&amp;0xF0F0F0F0)&gt;&gt;4 | (x&amp;0x0F0F0F0F)&lt;&lt;4;\n        /* swap every 8 neighbouring bits */\n        x = (x&amp;0xFF00FF00)&gt;&gt;8 | (x&amp;0x00FF00FF)&lt;&lt;8;\n        /* and so forth, for say, 32 bit int */\n        x = (x&amp;0xFFFF0000)&gt;&gt;16 | (x&amp;0x0000FFFF)&lt;&lt;16;\n        printf("0x%x\\n",x);\n        return 0;\n}\n</code></pre>\n\n<p>This code should not contain errors, and was tested using 0x12345678 to produce 0x1e6a2c48 which is the correct answer.</p>\n'}, {'answer_id': 64949, 'author': 'Sundar R', 'author_id': 8127, 'author_profile': 'https://Stackoverflow.com/users/8127', 'pm_score': 2, 'selected': False, 'text': "<pre><code>typedef unsigned long TYPE;\n\nTYPE reverser(TYPE n)\n{\n    TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;\n    int count;\n\n    for(i = 0; !i || (1 &lt;&lt; i &amp;&amp; (1 &lt;&lt; i) != 1); i+=2)\n    {\n        /*In each iteration, we  swap one bit \n            on the 'right half' of the number with another \n            on the left half*/\n\n        k = 1&lt;&lt;i; /*this is used to find how many positions \n                    to the left (or right, for the other bit) \n                    we gotta move the bits in this iteration*/\n\n        count = 0;\n\n        while(k &lt;&lt; 1 &amp;&amp; k &lt;&lt; 1 != 1)\n        {\n            k &lt;&lt;= 1;\n            count++;\n        }\n\n        nrevbit1 = n &amp; (1&lt;&lt;(i/2));\n        nrevbit1 &lt;&lt;= count;\n\n        nrevbit2 = n &amp; 1&lt;&lt;((i/2) + count);\n        nrevbit2 &gt;&gt;= count;\n\n        nrev |= nrevbit1;\n        nrev |= nrevbit2;\n    }\n    return nrev;\n}\n</code></pre>\n\n<p>This works fine in gcc under Windows, but I'm not sure if it's completely platform independent. A few places of concern are:</p>\n\n<ul>\n<li><p>the condition in the for loop - it assumes that when you left shift 1 beyond the leftmost bit, you get either a 0 with the 1 'falling out' (what I'd expect and what good old Turbo C gives iirc), or the 1 circles around and you get a 1 (what seems to be gcc's behaviour).</p></li>\n<li><p>the condition in the inner while loop: see above. But there's a strange thing happening here: in this case, gcc seems to let the 1 fall out and not circle around!</p></li>\n</ul>\n\n<p>The code might prove cryptic: if you're interested and need an explanation please don't hesitate to ask - I'll put it up someplace.</p>\n"}, {'answer_id': 70906, 'author': 'Sundar R', 'author_id': 8127, 'author_profile': 'https://Stackoverflow.com/users/8127', 'pm_score': 4, 'selected': True, 'text': '<pre><code>#include&lt;stdio.h&gt;\n#include&lt;limits.h&gt;\n\n#define TYPE_BITS sizeof(TYPE)*CHAR_BIT\n\ntypedef unsigned long TYPE;\n\nTYPE reverser(TYPE n)\n{\n    TYPE nrev = 0, i, bit1, bit2;\n    int count;\n\n    for(i = 0; i &lt; TYPE_BITS; i += 2)\n    {\n        /*In each iteration, we  swap one bit on the \'right half\' \n        of the number with another on the left half*/\n\n        count = TYPE_BITS - i - 1;  /*this is used to find how many positions \n                                    to the left (and right) we gotta move \n                                    the bits in this iteration*/\n\n        bit1 = n &amp; (1&lt;&lt;(i/2)); /*Extract \'right half\' bit*/\n        bit1 &lt;&lt;= count;         /*Shift it to where it belongs*/\n\n        bit2 = n &amp; 1&lt;&lt;((i/2) + count);  /*Find the \'left half\' bit*/\n        bit2 &gt;&gt;= count;         /*Place that bit in bit1\'s original position*/\n\n        nrev |= bit1;   /*Now add the bits to the reversal result*/\n        nrev |= bit2;\n    }\n    return nrev;\n}\n\nint main()\n{\n    TYPE n = 6;\n\n    printf("%lu", reverser(n));\n    return 0;\n}\n</code></pre>\n\n<p>This time I\'ve used the \'number of bits\' idea from TK, but made it somewhat more portable by not assuming a byte contains 8 bits and instead using the CHAR_BIT macro. The code is more efficient now (with the inner for loop removed). I hope the code is also slightly less cryptic this time. :)</p>\n\n<p>The need for using count is that the number of positions by which we have to shift a bit varies in each iteration - we have to move the rightmost bit by 31 positions (assuming 32 bit number), the second rightmost bit by 29 positions and so on. Hence count must decrease with each iteration as i increases. </p>\n\n<p>Hope that bit of info proves helpful in understanding the code... </p>\n'}, {'answer_id': 73999, 'author': 'Frosty', 'author_id': 7476, 'author_profile': 'https://Stackoverflow.com/users/7476', 'pm_score': 0, 'selected': False, 'text': "<p>Here is a variation and correction to TK's solution which might be clearer than the solutions by sundar.  It takes single bits from t and pushes them into return_val:</p>\n\n<pre><code>typedef unsigned long TYPE;\n#define TYPE_BITS sizeof(TYPE)*8\n\nTYPE reverser(TYPE t)\n{\n    unsigned int i;\n    TYPE return_val = 0\n    for(i = 0; i &lt; TYPE_BITS; i++)\n    {/*foreach bit in TYPE*/\n        /* shift the value of return_val to the left and add the rightmost bit from t */\n        return_val = (return_val &lt;&lt; 1) + (t &amp; 1);\n        /* shift off the rightmost bit of t */\n        t = t &gt;&gt; 1;\n    }\n    return(return_val);\n}\n</code></pre>\n"}, {'answer_id': 74332, 'author': 'freespace', 'author_id': 8297, 'author_profile': 'https://Stackoverflow.com/users/8297', 'pm_score': 1, 'selected': False, 'text': '<p>@ΤΖΩΤΖΙΟΥ</p>\n\n<p>In reply to ΤΖΩΤΖΙΟΥ \'s comments, I present modified version of above which depends on a upper limit for bit width.</p>\n\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;stdint.h&gt;\ntypedef int32_t TYPE;\nTYPE reverse(TYPE x, int bits)\n{\n    TYPE m=~0;\n    switch(bits)\n    {\n        case 64:\n            x = (x&amp;0xFFFFFFFF00000000&amp;m)&gt;&gt;16 | (x&amp;0x00000000FFFFFFFF&amp;m)&lt;&lt;16;\n        case 32:\n            x = (x&amp;0xFFFF0000FFFF0000&amp;m)&gt;&gt;16 | (x&amp;0x0000FFFF0000FFFF&amp;m)&lt;&lt;16;\n        case 16:\n            x = (x&amp;0xFF00FF00FF00FF00&amp;m)&gt;&gt;8 | (x&amp;0x00FF00FF00FF00FF&amp;m)&lt;&lt;8;\n        case 8:\n            x = (x&amp;0xF0F0F0F0F0F0F0F0&amp;m)&gt;&gt;4 | (x&amp;0x0F0F0F0F0F0F0F0F&amp;m)&lt;&lt;4;\n            x = (x&amp;0xCCCCCCCCCCCCCCCC&amp;m)&gt;&gt;2 | (x&amp;0x3333333333333333&amp;m)&lt;&lt;2;\n            x = (x&amp;0xAAAAAAAAAAAAAAAA&amp;m)&gt;&gt;1 | (x&amp;0x5555555555555555&amp;m)&lt;&lt;1;\n    }\n    return x;\n}\n\nint main(int argc, char**argv)\n{\n    TYPE x;\n    TYPE b = (TYPE)-1;\n    int bits;\n    if ( argc != 2 ) \n    {\n        printf("Usage: %s hexadecimal\\n", argv[0]);\n        return 1;\n    }\n    for(bits=1;b;b&lt;&lt;=1,bits++);\n    --bits;\n    printf("TYPE has %d bits\\n", bits);\n    sscanf(argv[1],"%x", &amp;x);\n\n    printf("0x%x\\n",reverse(x, bits));\n    return 0;\n}\n</code></pre>\n\n<p>Notes:</p>\n\n<ul>\n    <li>gcc will warn on the 64bit constants</li>\n    <li>the printfs will generate warnings too</li>\n    <li>If you need more than 64bit, the code should be simple enough to extend</li>\n</ul>\n\n<p>I apologise in advance for the coding crimes I committed above - mercy good sir!</p>\n'}, {'answer_id': 79181, 'author': 'mxg', 'author_id': 11157, 'author_profile': 'https://Stackoverflow.com/users/11157', 'pm_score': 1, 'selected': False, 'text': '<p>There\'s a nice collection of "Bit Twiddling Hacks", including a variety of simple and not-so simple bit reversing algorithms coded in C at <a href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow noreferrer">http://graphics.stanford.edu/~seander/bithacks.html</a>.</p>\n\n<p>I personally like the "Obvious" algorigthm (<a href="http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious" rel="nofollow noreferrer">http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious</a>) because, well, it\'s obvious.  Some of the others may require less instructions to execute.  If I really need to optimize the heck out of something I may choose the not-so-obvious but faster versions.  Otherwise, for readability, maintainability, and portability I would choose the Obvious one.</p>\n'}, {'answer_id': 1845062, 'author': 'The Neocompressionist', 'author_id': 224525, 'author_profile': 'https://Stackoverflow.com/users/224525', 'pm_score': 1, 'selected': False, 'text': "<p>Here is a more generally useful variation. Its advantage is its ability to work in situations where the bit length of the value to be reversed -- the codeword -- is unknown but is guaranteed not to exceed a value we'll call maxLength. A good example of this case is Huffman code decompression. </p>\n\n<p>The code below works on codewords from 1 to 24 bits in length. It has been optimized for fast execution on a Pentium D. Note that it accesses the lookup table as many as 3 times per use. I experimented with many variations that reduced that number to 2 at the expense of a larger table (4096 and 65,536 entries). This version, with the 256-byte table, was the clear winner, partly because it is so advantageous for table data to be in the caches, and perhaps also because the processor has an 8-bit table lookup/translation instruction.</p>\n\n<pre><code>const unsigned char table[] = {  \n0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,  \n0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,  \n0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,  \n0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,  \n0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,  \n0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,  \n0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,  \n0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,  \n0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,  \n0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,  \n0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,  \n0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,  \n0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,  \n0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,  \n0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,  \n0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF};  \n\n\nconst unsigned short masks[17] =  \n{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};  \n\n\nunsigned long codeword;   // value to be reversed, occupying the low 1-24 bits  \nunsigned char maxLength;  // bit length of longest possible codeword (&lt;= 24)  \nunsigned char sc;         // shift count in bits and index into masks array  \n\n\nif (maxLength &lt;= 8)  \n{  \n   codeword = table[codeword &lt;&lt; (8 - maxLength)];  \n}  \nelse  \n{  \n   sc = maxLength - 8;  \n\n   if (maxLength &lt;= 16)  \n   {\n      codeword = (table[codeword &amp; 0X00FF] &lt;&lt; sc)  \n               |  table[codeword &gt;&gt; sc];  \n   }  \n   else if (maxLength &amp; 1)  // if maxLength is 17, 19, 21, or 23  \n   {  \n      codeword = (table[codeword &amp; 0X00FF] &lt;&lt; sc)  \n               |  table[codeword &gt;&gt; sc] |  \n                 (table[(codeword &amp; masks[sc]) &gt;&gt; (sc - 8)] &lt;&lt; 8);  \n   }  \n   else  // if maxlength is 18, 20, 22, or 24  \n   {  \n      codeword = (table[codeword &amp; 0X00FF] &lt;&lt; sc)  \n               |  table[codeword &gt;&gt; sc]  \n               | (table[(codeword &amp; masks[sc]) &gt;&gt; (sc &gt;&gt; 1)] &lt;&lt; (sc &gt;&gt; 1));  \n   }  \n}  \n</code></pre>\n"}, {'answer_id': 1845084, 'author': 'AnT stands with Russia', 'author_id': 187690, 'author_profile': 'https://Stackoverflow.com/users/187690', 'pm_score': 0, 'selected': False, 'text': '<p>The generic approach hat would work for objects of any type of any size would be to reverse the of bytes of the object, and the reverse the order of bits in each byte. In this case the bit-level algorithm is tied to a concrete number of bits (a byte), while the "variable" logic (with regard to size) is lifted to the level of whole bytes.</p>\n'}, {'answer_id': 2489633, 'author': 'ivan', 'author_id': 298718, 'author_profile': 'https://Stackoverflow.com/users/298718', 'pm_score': 0, 'selected': False, 'text': "<p>In case bit-reversal is time critical, and mainly in conjunction with FFT, the best is to store the whole bit reversed array. In any case, this array will be smaller in size than the roots of unity that have to be precomputed in FFT Cooley-Tukey algorithm. An easy way to compute the array is:</p>\n\n<pre><code>int BitReverse[Size]; // Size is power of 2\nvoid Init()\n{\n   BitReverse[0] = 0;\n   for(int i = 0; i &lt; Size/2; i++)\n   {\n      BitReverse[2*i] = BitReverse[i]/2;\n      BitReverse[2*i+1] = (BitReverse[i] + Size)/2;\n   }\n} // end it's all\n</code></pre>\n"}, {'answer_id': 5036813, 'author': 'Bernd Jendrissek', 'author_id': 117911, 'author_profile': 'https://Stackoverflow.com/users/117911', 'pm_score': 0, 'selected': False, 'text': '<p>Here\'s my generalization of freespace\'s solution (in case we one day get 128-bit machines).  It results in jump-free code when compiled with gcc -O3, and is obviously insensitive to the definition of foo_t on sane machines.  Unfortunately it does depend on shift being a power of 2!</p>\n\n<pre><code>#include &lt;limits.h&gt;\n#include &lt;stdio.h&gt;\n\ntypedef unsigned long foo_t;\n\nfoo_t reverse(foo_t x)\n{\n        int shift = sizeof (x) * CHAR_BIT / 2;\n        foo_t mask = (1 &lt;&lt; shift) - 1;\n        int i;\n\n        for (i = 0; shift; i++) {\n                x = ((x &amp; mask) &lt;&lt; shift) | ((x &amp; ~mask) &gt;&gt; shift);\n                shift &gt;&gt;= 1;\n                mask ^= (mask &lt;&lt; shift);\n        }\n\n        return x;\n}       \n\nint main() {\n        printf("reverse = 0x%08lx\\n", reverse(0x12345678L));\n}\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/63776', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/6899/']