C# reversing the bits of an integer

Question

I know this has been asked in similar variances many times, but I'm having trouble with the output of bitwise operations in C#(Unity3D).

I'm trying to do bit-reversal permutation, that is, get the bit-reversed order of integers(or unsigned int, either one) for the purpose using in the Cooley-Tukey FFT algorithm. So if I have 0, 1, 2, 3 - I want to end up with 0, 2, 1, 3 and if I have 0, 1, 2, 3, 4, 5, 6, 7 - I should get 0, 4, 2, 6, 1, 5, 3, 7.

I've tried a few bit-reversal algorithms found online, such as this one:

public uint ReverseBits(uint n)
{
    n = (n >> 1) & 0x55555555 | (n << 1) & 0xaaaaaaaa;
    n = (n >> 2) & 0x33333333 | (n << 2) & 0xcccccccc;
    n = (n >> 4) & 0x0f0f0f0f | (n << 4) & 0xf0f0f0f0;
    n = (n >> 8) & 0x00ff00ff | (n << 8) & 0xff00ff00;
    n = (n >> 16) & 0x0000ffff | (n << 16) & 0xffff0000;
    return n;
}

And I'd use it like this:

uint x = 1;
x = ReverseBits(x);  //this results in x = 2147483648;

I wanted to try another algorithm so I found this one, which as pointed out reverses the bytes:

public uint ReverseBytes(uint value)
{
    return (value & 0x000000FFU) << 24 | (value & 0x0000FF00U) << 8 |
           (value & 0x00FF0000U) >> 8 | (value & 0xFF000000U) >> 24;
}

and I get the exact same number, x = 2147483648. A bitwise operator such as >> performs the same function in C# as it would in other languages such as C, right? So, am I missing a step?

Answer 1

The algorithms you are currently using reverse the bits in the whole integer (i.e. 32 bits for an int and 64 bits for a long), whereas what you really want is to reverse only the first k bits (where n = 2^k for the bit-reversal permutation).

A simple solution would be to use strings:

int x = 6;
int k = 3;
// Binary representation of x of length k
string binaryString = Convert.ToString(x, 2).PadLeft(k, '0');
int reversed = Convert.ToInt32(Reverse(binaryString), 2);

where Reverse is defined as follows:

public static string Reverse( string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}

Or if you don't want to use strings, you could stick with a bitwise operator solution:

int x = 6;
int k = 3;
int reversed = 0;

for(int i = 0; i < k; i++) {
    // If the ith bit of x is toggled, toggle the ith bit from the right of reversed
    reversed |= (x & (1 << i)) != 0 ? 1 << (k - 1 - i) : 0;
}

You can even remove the ternary operator at the cost of readability:

reversed |= (((x & (1 << i)) >> i) & 1) << (k - 1 - i);

The & 1 compensates for the case when the right arithmetic shift (>> i) fills in the sign bit.