Bit Reversal using bitwise

Question

I am trying to do bit reversal in a byte. I use the code below

static int BitReversal(int n)
{
    int u0 = 0x55555555; // 01010101010101010101010101010101
    int u1 = 0x33333333; // 00110011001100110011001100110011
    int u2 = 0x0F0F0F0F; // 00001111000011110000111100001111
    int u3 = 0x00FF00FF; // 00000000111111110000000011111111
    int u4 = 0x0000FFFF;
    int x, y, z;
    x = n;
    y = (x >> 1) & u0;
    z = (x & u0) << 1;
    x = y | z;

    y = (x >> 2) & u1;
    z = (x & u1) << 2;
    x = y | z;

    y = (x >> 4) & u2;
    z = (x & u2) << 4;
    x = y | z;

    y = (x >> 8) & u3;
    z = (x & u3) << 8;
    x = y | z;

    y = (x >> 16) & u4;
    z = (x & u4) << 16;
    x = y | z;

    return x;
}

It can reverser the bit (on a 32-bit machine), but there is a problem, For example, the input is 10001111101, I want to get 10111110001, but this method would reverse the whole byte including the heading 0s. The output is 10111110001000000000000000000000. Is there any method to only reverse the actual number? I do not want to convert it to string and reverser, then convert again. Is there any pure math method or bit operation method?

Best Regards,

Answer 1

Get the highest bit number using a similar approach and shift the resulting bits to the right 33 - #bits and voila!

Answer 2

Cheesy way is to shift until you get a 1 on the right:

if (x != 0) {
    while ((x & 1) == 0) {
        x >>= 1;
    }
}

Note: You should switch all the variables to unsigned int. As written you can have unwanted sign-extension any time you right shift.