CODEWITHSUNDEEP
c++bit-manipulationreverse
Red
Red

Reputation: 27

Reverse Bits Algorithm

This is a very obvious and simple question that I am unfortunately having some trouble with. Reversing the bits in a given integer (not inverting/flipping the bits) making MSB to LSB and MSB-1 to LSB+1 and so on. In my mind, the way I think of doing this is to store the last bit of the input into an output variable and right shift that variable by 1 each time then left shift the input by 1 and repeat the process. Here is the function I have written so far to do this:

unsigned int oldRev(unsigned int input){
    unsigned int output = 0;    

    for(int i=0; i<((sizeof(int)*8)-1); i++){
        output |= input&1;
        output <<= 1;
        input >>= 1;
    }    

    return output;    

}

The issue arises when I try to do oldRev(2147483648) where only the most significant bit is 1 in the input. The output should be just 1 but I get 0. Why does this happen? I have been trying to figure out the issue with my logic but have been unsuccessful thus far. I have seen the various methods of doing this online but still want to know what I am doing wrong.

Thank you in advance!

Upvotes: 1

Views: 785

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118425

You need to switch the order of two operations:

    output <<= 1;
    output |= input&1;

To understand why, stare at the existing code and pontificate the fact that it will always wind up producing an output whose last bit will always be 0. Because the last thing that ever will be done to output, always, no matter how big your int is, would be the left shift operation. Which would always leave output's last bit as 0. Which is obviously wrong.

Also, since there are sizeof(int)*8 bits in an int, the loop has to obviously iterate sizeof(int)*8 times, to process that # of bits, but:

for(int i=0; i<((sizeof(int)*8)-1); i++){

This iterates sizeof(int)*8-1 times. One less than the number required. This should be:

for(int i=0; i<sizeof(int)*8; i++){

Upvotes: 3

Related Questions