C reverse bits in unsigned integer

Question

I'm converting an unsigned integer to binary using bitwise operators, and currently do integer & 1 to check if bit is 1 or 0 and output, then right shift by 1 to divide by 2. However the bits are returned in the wrong order (reverse), so I thought to reverse the bits order in the integer before beginning.

Is there a simple way to do this?

Example: So if I'm given the unsigned int 10 = 1010

while (x not eq 0) 
  if (x & 1)
    output a '1'
  else 
    output a '0'
  right shift x by 1

this returns 0101 which is incorrect... so I was thinking to reverse the order of the bits originally before running the loop, but I'm unsure how to do this?

Calore

You should post some code to make this a bit more clear (no pun intended). – Temple

Possible duplicate of Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C – Paraclete

Answer 1

Reversing the bits in a word is annoying and it's easier just to output them in reverse order. E.g.,

void write_u32(uint32_t x)
{
    int i;
    for (i = 0; i < 32; ++i)
        putchar((x & ((uint32_t) 1 << (31 - i)) ? '1' : '0');
}

Here's the typical solution to reversing the bit order:

uint32_t reverse(uint32_t x)
{
    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);
    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);
    x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4);
    x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8);
    x = ((x >> 16) & 0xffffu) | ((x & 0xffffu) << 16);
    return x;
}

Trehala

Could u please give me further explanation of second part (or give me a phrase to put into google). It does not make sense to me and my knowledge about bit representation is appearantly worse than I thought. Thank you in advance. – Surf

@AoeAoe: It's a bit twiddling hack. I suggest writing out the numbers in binary if you want to understand how it works. Each line exchanges the positions of half of the bits with another half, and the five lines in the core can be written in any order. – Trehala

Here's explanation: Let us divide all bits in block size b, starting with b=1. Now we swap each adjacent block. Double block size and repeat. Continue until block size is half of word size. For 32 bits, this will be 5 steps. Each step can be written as ((x & mask) << b) | ((x & mask') << b). Thus in 5 statements, we can reverse 32 bit int. – Balas

Dietrich Epp, do you agree that the 5 lines of x = ((x >> ... could be reversed and provide the same efficient answer? – Stevestevedore

@chux-ReinstateMonica: Those lines can be put in any order. – Trehala

Answer 2

you could move from left to right instead, that is shift a one from the MSB to the LSB, for example:

unsigned n = 20543;
unsigned x = 1<<31;
while (x) {
    printf("%u ", (x&n)!=0);
    x = x>>1;
}

Climatology

@SethCarnegie no, it's x>>1 because x=1<<31 so we're moving from the MSB to LSB or left to right to reverse the order of the bits. – Climatology

Ah I had confused x with n. – Spline

1<<31; is UB. Use 1u<<31;. – Stevestevedore

Answer 3

You could just loop through the bits from big end to little end.

#define N_BITS (sizeof(unsigned) * CHAR_BIT)
#define HI_BIT (1 << (N_BITS - 1))

for (int i = 0; i < N_BITS; i++) {
     printf("%d", !!(x & HI_BIT));
     x <<= 1;
}

Where !! can also be written !=0 or >> (N_BITS - 1).

Mundy

Isn't !!(x) == x ? double negation cancels out, and ==0 will be true, i.e 1 if it's 0 so it prints the bits flipped. – Climatology

@mux: no, double negation only cancels out for 0 and 1. You're right about ==0, that should have been !=0, sorry. – Mundy

oh I see it now, something like !(!(512)) = !(0) = 1 thanks, I blame it on too much discrete :) ... – Climatology

1 << (N_BITS - 1) is UB (shifting a 1 into the sign bit). Use 1u << (N_BITS - 1). – Stevestevedore

Answer 4

The 2nd answer by Dietrich Epp is likely what's best on a modern out of order processor. Typical microcontrollers however are not, and there the following is more versatile (with u8, u16, u32 versions), more compact and often faster (in C):

// reverse a byte
uint8_t reverse_u8(uint8_t x)
{
   const unsigned char * reverse_u4 = "\x0\x8\x4\xC\x2\xA\x6\xE\x1\x9\x5\xD\x3\xB\x7\xF";
   return reverse_u4[x >> 4] | (reverse_u4[x & 0x0F] << 4);
}

// reverse a word
uint16_t reverse_u16(uint16_t x)
{
   return reverse_u8(x >> 8) | (reverse_u8(x & 0xFF) << 8);
}

// reverse a long
uint32_t reverse_u32(uint32_t x)
{
   return reverse_u16(x >> 16) | (reverse_u16(x & 0xFFFF) << 16);
}

The code is easily translated to Java, Go, Rust etc. Of course if you only need to print the digits, it is best to simply print in reverse order (see the answer by Dietrich Epp).

Objectivism

Thank you for your solution. I was not able to get Dietrich’s solution working but yours was brilliant. Are you able to explain the meaning behind the unsigned char* rev? I was able to deduce that the 5th element is the next increment of the 1st, the 6th element is the next increment of the 2nd and so forth. – Antiserum

Sorry I meant the 9th element of the 1st element. Miscounted/misremembered since I am typing on mobile. – Antiserum

@Antiserum So rev takes the lowest 4 bits as the index, and maps them to the reversed value of those bits. So it performs the reversing of 4 bits at a time. reverse_u8() immediately extends that to 8 bits. In rev 0b0000 maps to 0b0000, 0b0001 maps to 0b1000, 0b0010 maps to 0b0100, and so on, all bit-reversed. A string allows for hex characters to be inserted, so that was used there instead of the binary shown. Hope this helps. – Objectivism

@Antiserum I've renamed rev to reverse_u4 to make its function more clear – Objectivism

That was incredibly clever. Thank you for the explanation. – Antiserum

Answer 5

It seems foolish to reverse the bit order of an integer value and then pick off bits from the low end, when it is trivial to leave it unchanged and pick off bits from the high end.

You want to convert an integer into a text representation, in this case in base-2 (binary). Computers convert integers into text all the time, most often in base-10 or base-16.

A simple built-in solution is:

printf('%b', 123);  // outputs 1111011

But that's not standard in C. (See Is there a printf converter to print in binary format?)

Numbers are written with the most-significant digit (or bit) first, so repeatedly taking the least-significant digit (or bit) is half the job. You have to collect the digits and assemble or output them in reverse order.

To display the value 123 as base-10, you would:

• Divide 123 by 10, yielding 12 remainder 3.
• Divide 12 by 10, yielding 1 remainder 2.
• Finally, divide 1 by 10, yielding 0 remainder 1. (0 is the stopping point.)
• Display the remainders (3, 2, 1) in reverse order, to display "123".

We could put any number of zeros before the 123, but that is not proper, because they do not contribute anything. Bigger numbers need longer character strings ("123", "123000", "123000000"). With this approach, you don't know how many digits are needed until you compute the most-significant digit, so you can't output the first digit until you have computed all of them.

Alternatively, you can compute the most-significant digit first. It looks a little more complex. Especially in bases other than base-2. Again starting with 123:

• Divide 123 by 1000, yielding 0 remainder 123.
• Divide 123 by 100, yielding 1 remainder 23.
• Divide 23 by 10, yielding 2 remainder 3.
• Finally, divide 3 by 1, yielding 3 remainder 0. (0 is the stopping point.)
• Display the quotients (0, 1, 2, 3) in the same order, skipping the leading zeros, to display "123".

You could output the digits in order as they are computed. You have to start with a large-enough divisor. For uint16 it's 10000; for uint32 it's 1000000000.

To display the value 123 as base-2, using the first method:

• Divide 123 by 2, yielding 61 remainder 1.
• Divide 61 by 2, yielding 30 remainder 1.
• Divide 30 by 2, yielding 15 remainder 0.
• Divide 15 by 2, yielding 7 remainder 1.
• Divide 7 by 2, yielding 3 remainder 1.
• Divide 3 by 2, yielding 1 remainder 1.
• Finally, divide 1 by 2, yielding 0 remainder 1. (0 is the stopping point.)
• Display the remainders (1,1,0,1,1,1,1) in reverse order, to display "1111011".

(Dividing by 2 can be accomplished by right-shifting by 1 bit.)

The second method yields the digits (bits) in order.

• Divide 123 by 256, yielding 0 remainder 123.
• Divide 123 by 128, yielding 0 remainder 123.
• Divide 123 by 64, yielding 1 remainder 59.
• Divide 59 by 32, yielding 1 remainder 27.
• Divide 27 by 16, yielding 1 remainder 11.
• Divide 11 by 8, yielding 1 remainder 3.
• Divide 3 by 4, yielding 0 remainder 3.
• Divide 2 by 2, yielding 1 remainder 1.
• Finally, divide 1 by 1, yielding 1 remainder 0. (0 is the stopping point.)
• Display the quotients (0,0,1,1,1,1,0,1,1) in the same order, skipping any leading first zeros, to display "1111011".

(These divisions can be accomplished using comparisons. The comparison values can be generated by dividing by 2, which means right-shifting by 1 bit.)

Any of these solutions might need a hack to prevent the value 0 from displaying as nothing (a.k.a. "", or the empty string) instead of "0".

Purplish

Answer 6

You could reverse the bits like you output them, and instead store them in another integer, and do it again :

for (i = 0; i < (sizeof(unsigned int) * CHAR_BIT); i++)
{
  new_int |= (original_int & 1);
  original_int = original_int >> 1;
  new_int = new_int << 1;
}

Or you could just do the opposite, shift your mask :

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while (mask > 0)
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
}

If you want to remove leading 0's you can either wait for a 1 to get printed, or do a preliminary go-through :

unsigned int mask = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1);
while ((mask > 0) && ((original_int & mask) == 0))
  mask = mask >> 1;
do
{
  bit = original_int & mask;
  mask = mask >> 1;
  printf("%d", (bit > 0));
} while (mask > 0);

this way you will place the mask on the first 1 to be printed and forget about the leading 0's

But remember : printing the binary value of an integer can be done just with printf

Disafforest

Just remember to multiply the sizeof by 8, and your First solution will be fine. (The second will overflow, but with some corrections, it can work) – Marika

Better still, multiply by CHAR_BIT. – Rachelrachele

How would I discard leading 0s from the output in this case? I could check and not output until it has detected a true bit, but that doesn't seem very elegant and also wouldn't work if the input to the program is 0. – Calore

@Calore I added leading 0 removal in my answer, changing to a do/while to keep the last 0. You can also use while ((mask > 1) ... in the first while and keep the second as while (mask > 0) – Disafforest

@Marika what could overflow ? there is no multiplication or shift to the left in the second solution – Disafforest

isn't original_int & mask is either 0 or a number >= 1 depending on the bit position, and not 0/1 ? – Climatology

No shifting to the left? what about 1 << (sizeof(unsigned int) * CHAR_BIT)? – Marika

@Disafforest I'm unsure why but it doesn't output anything for odd numbers – Calore

@Marika okay I think the error was 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1) right ? @Calore try it out with this version. – Disafforest

1 << ((sizeof(unsigned int) * CHAR_BIT) - 1); is UB (shifting a 1 into the sign bit). Use 1u << ((sizeof(unsigned int) * CHAR_BIT) - 1); or the like. – Stevestevedore

Answer 7

unsigned int rev_bits(unsigned int input)
{
    unsigned int output = 0;
    unsigned int n = sizeof(input) << 3;
    unsigned int i = 0;

    for (i = 0; i < n; i++)
        if ((input >> i) & 0x1)
            output |=  (0x1 << (n - 1 - i));

    return output;
}

Rhetic

0x1 << 31 has undefined behavior. You should write output |= 1U << (n - 1 - i); – Vegetative

Answer 8

You can reverse an unsigned 32-bit integer and return using the following reverse function :

unsigned int reverse(unsigned int A) {
    unsigned int B = 0;
    for(int i=0;i<32;i++){
        unsigned int j = pow(2,31-i);
        if((A & (1<<i)) == (1<<i)) B += j; 
    }
return B; 
}

Remember to include the math library. Happy coding :)

Untrue

To avoid undefined behavior on 1 << 31, you should use if((A & (1U<<i)) == (1U<<i)) B += j; Also use unsigned int j = 1U << (31 - i); instead of floating point arithmetics. – Vegetative

Answer 9

I believe the question is asking how to not output in reverse order.

Fun answer (recursion):

#include <stdio.h>

void print_bits_r(unsigned int x){
    if(x==0){
       printf("0");
       return;
    }
    unsigned int n=x>>1;
    if(n!=0){
       print_bits_r(n);
    }
    if(x&1){
        printf("1");
    }else{
        printf("0");
    }
}


void print_bits(unsigned int x){
    printf("%u=",x);
    print_bits_r(x);
    printf("\n");
}

int main(void) {
    print_bits(10u);//1010
    print_bits((1<<5)+(1<<4)+1);//110001
    print_bits(498598u);//1111001101110100110
    return 0;
}

Expected output:

10=1010
49=110001
498598=1111001101110100110

Sequential version (picks off the high-bits first):

#include <limits.h>//Defines CHAR_BIT
//....
void print_bits_r(unsigned int x){
    //unsigned int mask=(UINT_MAX>>1)+1u;//Also works...
    unsigned int mask=1u<<(CHAR_BIT*sizeof(unsigned int)-1u);
    int start=0;
    while(mask!=0){
        if((x&mask)!=0){
            printf("1");
            start=1;
        }else{
            if(start){
                printf("0");
            }
        }
        mask>>=1;
    }
    if(!start){
       printf("0");
    }    
}

Pengelly

Answer 10

The Best way to reverse the bit in an integer is:

1. It is very efficient.
2. It only runs upto when the leftmost bit is 1.

CODE SNIPPET

int reverse ( unsigned int n )
{
    int x = 0;
    int mask = 1;
    while ( n > 0 )
    {
        x = x << 1;
        if ( mask & n )
            x = x | 1;
        n = n >> 1;
    }
    return x;
}

Greatnephew

Better to return unsigned and use unsigned x; (to avoid UB). – Stevestevedore

Answer 11

I came up with a solution which dosesn't involve any application of bitwise operators. it is inefficient in terms of both space and time.

int arr[32];
for(int i=0;i<32;i++)
{
    arr[i]=A%2;
    A=A/2;
}
double res=1;
double re=0;
for(int i=0;i<32;i++)
{
    int j=31-i;
    res=arr[i];
    while(j>0)
    {
        res=res*2;
        j--;
    }
    re=re+res;
}
cout<<(unsigned int )re;

Poliomyelitis

Answer 12

Here's a golang version of reverse bits in an integer, if anyone is looking for one. I wrote this with an approach similar to string reverse in c. Going over from bits 0 to 15 (31/2), swap bit i with bit (31-i). Please check the following code.

package main
import "fmt"

func main() {
    var num = 2
    //swap bits at index i and 31-i for i between 0-15
    for i := 0; i < 31/2; i++ {
        swap(&num, uint(i))
    }
    fmt.Printf("num is %d", num)
}

//check if bit at index is set
func isSet(num *int, index uint) int {
    return *num & (1 << index)
}

//set bit at index
func set(num *int, index uint) {
    *num = *num | (1 << index)
}

//reset bit at index
func reSet(num *int, index uint) {
    *num = *num & ^(1 << index)
}

//swap bits on index and 31-index
func swap(num *int, index uint) {
    //check index and 31-index bits
    a := isSet(num, index)
    b := isSet(num, uint(31)-index)
    if a != 0 {
        //bit at index is 1, set 31-index
        set(num, uint(31)-index)
    } else {
        //bit at index is 0, reset 31-index
        reSet(num, uint(31)-index)
    }
    if b != 0 {
        set(num, index)
    } else {
        reSet(num, index)
    }
}`

Decrepit

Answer 13

The following make use of a table that stored all the reversed value of each byte, table[byte] == reversed_byte, and reverse the 4 bytes of the unsigned integer. Faster to compute than other answers.

#include <stdint.h>

uint32_t reverse_bits(uint32_t n) {
static const uint8_t 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
    };

// 1 2 3 4 -> byte 4 becomes 1, 3 becomes 2, 2 becomes 3 and 1 becomes 4.
return (table[n & 0xff] << 24) | (table[(n >> 8) & 0xff] << 16) |
        (table[(n >> 16) & 0xff] << 8) | (table[(n >> 24) & 0xff]);
}

Mews

Faster to compute than other answers: Did you benchmark your proposal against the other answers? How much faster is it? – Vegetative

yes I did. So basically it is way faster than all branching solutions (while, for etc) and very slightly faster than divide and conquer. I missed user103185's answer, will test later and provide the benchmark. – Mews

@AntoninGAVREL I benchmarked this and it’s slow due to all the excessive bitwise ops, shifting, and masking. I counted 15 bit ops in the assembly output. See my answer above, which does all the shifting and masking in 2 bit ops and 4 movs by utilizing endianness. – Gillispie

Answer 14

I believe this should be the fastest. It uses a lookup table for all 256 possible byte values and avoids unnecessary shifts by utilizing endianness. The add with a second memory operand should macrofuse nicely on Intel processors and be very fast. It also uses ARM's rbit instruction where available in both MSVC and GCC/Clang.

#include <stdint.h>

#if defined(__clang__)
__attribute__((minsize))
#elif defined(__GNUC__)
__attribute__((optimize("Os")))
#elif defined(_MSC_VER) && (defined(_M_ARM) || defined(_M_ARM64))
    unsigned int _arm_rbit(unsigned int _Rm);
    #pragma intrinsic(_arm_rbit)
#endif
uint32_t fastBitReversal32(uint32_t in) {
    #if defined(__GNUC__) && (defined(__arm__) || defined(__aarch64__))
        uint32_t out;
        __asm__ inline ("rbit %0, %1" : "=r"(out) : "r"(in));
        return out;
    #elif defined(_MSC_VER) && (defined(_M_ARM) || defined(_M_ARM64))
        return _arm_rbit(in);
    #elif defined(__x86_64__) || (defined(_M_AMD64) && !defined(_M_PPC) && !defined(_M_IA64) && !defined(_M_ALPHA))
        // leverage unaligned access on the x86_64
        #ifdef __GNUC__
        __attribute__((aligned(2048))) // avoid crossing a page boundary
        #elif defined(_MSC_VER)
        __declspec(aligned(2048))
        #endif
        static const uint32_t lookup[257] = {0,0,128,64,192,32,160,96,224,
            16,144,80,208,48,176,112,240,8,136,72,200,40,168,104,232,24,
            152,88,216,56,184,120,248,4,132,68,196,36,164,100,228,20,148,
            84,212,52,180,116,244,12,140,76,204,44,172,108,236,28,156,92,
            220,60,188,124,252,2,130,66,194,34,162,98,226,18,146,82,210,
            50,178,114,242,10,138,74,202,42,170,106,234,26,154,90,218,58,
            186,122,250,6,134,70,198,38,166,102,230,22,150,86,214,54,182,
            118,246,14,142,78,206,46,174,110,238,30,158,94,222,62,190,126,
            254,1,129,65,193,33,161,97,225,17,145,81,209,49,177,113,241,9,
            137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,5,133,
            69,197,37,165,101,229,21,149,85,213,53,181,117,245,13,141,77,
            205,45,173,109,237,29,157,93,221,61,189,125,253,3,131,67,195,
            35,163,99,227,19,147,83,211,51,179,115,243,11,139,75,203,43,
            171,107,235,27,155,91,219,59,187,123,251,7,135,71,199,39,167,
            103,231,23,151,87,215,55,183,119,247,15,143,79,207,47,175,111,
            239,31,159,95,223,63,191,127,255};
        #if defined(__GNUC__) 
            uint32_t out, tmp;
            __asm__ inline (
                "movzx{l %b[in], %[out]| %[out], %b[in]}\n\t"
                "mov{l %p[lu]+1(,%[out],4), %[out]| %[out], DWORD PTR %p[lu][%[out]*4+1]}\n\t"
                #ifdef __AVX2__
                    "rorx{l $8, %[in], %[tmp]| %[tmp], %[in], 8}\n\t"
                #else
                    "mov{l %[in], %[tmp]| %[tmp], %[in]}\n\t"
                    "shr{l $8, %[tmp]| %[tmp], 8}\n\t"
                #endif
                "shr{l $24, %[in]| %[in], 24}\n\t"
                "add{l %p[lu]+4(,%[in],4), %[out]| %[out], DWORD PTR %p[lu][%[in]*4+4]}\n\t"
                "movzx{l %h[tmp], %[in]| %[in], %h[tmp]}\n\t"
                "movzx{l %b[tmp], %[tmp]| %[tmp], %b[tmp]}\n\t"
                "add{l %p[lu]+3(,%[in],4), %[out]| %[out], DWORD PTR %p[lu][%[in]*4+3]}\n\t"
                "add{l %p[lu]+2(,%[tmp],4), %[out]| %[out], DWORD PTR %p[lu][%[tmp]*4+2]}"
                : [out] "=r" (out), [tmp] "=Q" (tmp), [in] "+r" (in)
                : [lu] "m" (lookup)
            );
            return out;
        #else
            return *(uint32_t*)((char*)lookup + 1 + 4*(uint8_t)(in >>  0))
                + *(uint32_t*)((char*)lookup + 2 + 4*(uint8_t)(in >>  8))
                + *(uint32_t*)((char*)lookup + 3 + 4*(uint8_t)(in >> 16))
                + *(uint32_t*)((char*)lookup + 4 + 4*(uint8_t)(in >> 24));
        #endif
    #else
        // fallback to regular slow path
        uint32_t x = (in >> 16) | (in << 16);
        x = (x << 8) & UINT32_C(0xff00ff00) | ((x & UINT32_C(0xff00ff00))>>8);
        x = (x << 4) & UINT32_C(0xf0f0f0f0) | ((x & UINT32_C(0xf0f0f0f0))>>4);
        x = (x << 2) & UINT32_C(0x33333333) | ((x & UINT32_C(0x33333333))>>2);
        x = (x << 1) & UINT32_C(0xAAAAAAAA) | ((x & UINT32_C(0xAAAAAAAA))>>1);
        return x;
    #endif
}

Gillispie

Answer 15

Here's my bit shift version which I think is very concise. Does not work with leading zeros though. The main idea is as follows

• Input is in variable a, final answer in b

• Keep extracting the right most bit from a using (a&1)

• OR that with b and left shift b to make place for the next bit

• Right shift a to go to the next bit

   #include <stdio.h>
  
   void main()
   {
     int a = 23;
     int b = 0;
     while(a!=0)
     {
       b = (b<<1)|(a&1);
       a = a>>1;
     }
     printf("reversed bits gives %d\n", b);
    }
  

Grade

Infinite loop when a < 0. – Stevestevedore

Answer 16

for(i = 0,j=((sizeof(iReverNum)*8)-1);i<((sizeof(iReverNum)*8)/2);i++,j--)
{
    if(iReverNum & (1<<i))
    {
            swap_1 = 1;
    }
    else
    {
            swap_1 = 0;
    }
    if(iReverNum & (1<<j))
    {
            swap_2 = 1;
    }
    else
    {
            swap_2 =0;
    }
    if(swap_1)
    {
            iReverNum |= (1<<j);
    }
    else
    {
            iReverNum &= ~(1<<j);
    }
    if(swap_2)
    {
            iReverNum |= (1<<i);

    }
    else
    {
            iReverNum &= ~(1<<i);
    }
}

Kern

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Anthe