Bit Reversal

If you do not sleep,chat,eat snack,drink beverage and play your PSP in your Data Structure and Algorithm class, you may be already familiar with the topic I will write.  This is the dividing and conquering algorithm. This is a common algorithm that you would see a lot in practice. The essence  of it is to make the original problem smaller and smaller until to unit, and solve them individually, then combine the results.

Take the bit reversal as an example, there is x=(abcdefghijk)(each character stands for 1 or 0), reversing the bit means to make the x’=(kjihgfedcba).Keep you mind that we want to reverser the bit in a byte, not reverse the character in s string or an element in a array.

Given abcdefgh
step1 badcfehg
step2 dcbahgfe
step3 hgfedcba

The complexity for it is Ω(logn).
It can reverser the bit (on a 32-bit machine), but there is a problem, For example, the input is 10001111101, it would reverse the whole byte including the heading 0s. The output is 10111110001000000000000000000000.

static int BitReversal(int n)
{
    int u0 = 0x55555555; // 01010101010101010101010101010101
    int u1 = 0x33333333; // 00110011001100110011001100110011
    int u2 = 0x0F0F0F0F; // 00001111000011110000111100001111
    int u3 = 0x00FF00FF; // 00000000111111110000000011111111

    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;
}