3

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?

slanden
  • 1,199
  • 2
  • 15
  • 35
  • 1
    Those are different - the first one reverses all bits, while the second reverses all four bytes (4 8-bit blocks) – joe Nov 08 '17 at 08:32
  • `and I get the exact same number, x = 2147483648` - no, you don't.You input `0x80000000` and the output is `0x00000080` - i.e., the BYTES have been reversed (not the bits). – Matthew Watson Nov 08 '17 at 08:34
  • @MatthewWatson when you say "No, you don't" do you mean that the difference is just in the method that yields the resulting integer, bytes vs bits? Because with that code, and the environment I listed in my question I print the result to the console and I do indeed get `2147483648` both times. – slanden Nov 08 '17 at 18:03
  • @slanden I mean that the input is 0x80000000 and the output is 0x00000080, which is NOT 2147483648 (in decimal). – Matthew Watson Nov 09 '17 at 08:50
  • Why would the bit reverse of 1 be 1 in your example numbers given ? You put `0,1` becoming `0,2` – WDUK Mar 18 '19 at 23:37

4 Answers4

5

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.

Manfred Radlwimmer
  • 13,257
  • 13
  • 53
  • 62
EvilTak
  • 7,091
  • 27
  • 36
  • That was from when you only had the string-based solution. – Manfred Radlwimmer Nov 08 '17 at 09:16
  • @EvilTak Could you explain your answer more? Specifically, 1) What is `k` and why do I want to only reverse the first `k` bits? 2) What is `n`, why is it equal to 2^k? 3) Is `x` the number that should be reversed? – slanden Nov 08 '17 at 18:24
  • 1) and 2) They come directly from the definition of a bit-reversal permutation as on Wikipedia (linked in your question). Did you not try to understand _what_ a bit-reversal permutation is before implementing it? 3) Yes, `x` is the number to be reversed. – EvilTak Nov 09 '17 at 05:52
  • Yes, I read the link before I posted here. What I don't quite understand though is where it says(and so did you) that `n` is a sequence of elements and `n=2^k`, which it says is a power of 2 but a little further in the article is says that `2^n`, `n` for example being 0, 1, 2, 3, etc. and not all of those are power of 2. Also, in the 2nd sentence where they say _(padded so that each of these binary numbers has length exactly k)_ seems like that's where they mention the reason behind reversing the first `k` bits, but I don't understand. – slanden Nov 09 '17 at 07:03
  • 1
    The `n` in the part where they refer to `2^n` is completely different; consider it as a different variable (like `i`, for example). `n = 2^k` is the _size_ of the sequence on which you intend to apply a bit-reversal permutation. There is no "reason" behind reversing the first `k` bits, it is part of the definition of a bit-reversal permutation. Simply put, for a sequence `S` of length `n = 2^k`, its bit-reversal permutation `P` is defined as `P[i] = S[reversed(i)]`, where `reversed(x)` reverses the first `k` bits of `x`. – EvilTak Nov 09 '17 at 07:15
  • Oh ok, so you have a sequence of numbers of known size, `n`, which can be say 2, 4, 8, 16, etc. because those are a power of 2. Therefore, you can't perform the bit-reversal permutation on a sequence of say 3, or 5, or 6 numbers. And, defining `k` based on `n`, `k`=log_2(n). If `n=4` then `k=2`, if `n=8` then `k=3`. Or, defining `n` based on `k`, `n=2^k` where `k` can then be 0, 1, 2, 3, as per the definition. I think part of my confusion was coming from me looking at it as defining `k` based on `n`. – slanden Nov 09 '17 at 20:07
1

If you want to implement functions for given bit lengths (which you will if you know that your DFT has a given length such as 64) then you can hardcode various constants and write a function tailored to that bit-length, e.g:

public static int Reverse6Bits(int n)
{
    n = (n >> 1) & 0x55 | (n << 1) & 0xaa;
    n = (n >> 2) & 0x33 | (n << 2) & 0xcc;
    n = (n >> 6) & 0x03 | (n << 2) & 0x3c;
    return n;
}

if I have 0, 1, 2, 3, 4, 5, 6, 7 - I should get 0, 4, 2, 6, 1, 5, 3, 7

You can reverse 3 bits using a constant as a lookup table:

public static int Reverse3Bits(int n)
{
     return (0x73516240 >> (n << 2)) & 7;
}
samgak
  • 23,944
  • 4
  • 60
  • 82
0
    uint ret=n;
    ret = ret >> 16 | ret<<16;
    ret = (ret & 0xff00ff00) >> 8 | (ret & 0x00ff00ff) << 8;
    ret = (ret & 0xf0f0f0f0) >> 4 | (ret & 0x0f0f0f0f) << 4;
    ret = (ret & 0xcccccccc) >> 2 | (ret & 0x33333333) << 2;
    ret = (ret & 0xaaaaaaaa) >> 1 | (ret & 0x55555555) << 1;
    return ret;
Ashok
  • 743
  • 4
  • 13
  • 1
    Yes but that has the problem OP describes, instead of solving the problem. OP needs the FFT-style bitreverse, which is not just a plain 32bit bitreverse. It's a slightly different problem. – harold Feb 12 '18 at 01:19
  • Welcome to Stack Overflow, please review: https://stackoverflow.com/help/how-to-ask – Daniel Feb 12 '18 at 02:14
0

Since glsl has bitfieldReverse() operation, however, bitfieldReverse() is reversing all 32 bits.

In the case of FFT, only the right-most log2(N) bits are required to be reversed. Therefore, two extra int uniforms shiftBits and bitfieldMask could be introduced to complete the correct reverse_bits() function.

uniform int shiftBits; // 32-log2(N)
uniform int bitfieldMask; // 1<<log2(N) - 1;

int reverse_bits( int y )
{
    return (bitfieldReverse(y)>>shiftBits) & bitfieldMask;
}
Duncan Chen
  • 61
  • 5