C#反转整数的位

Question

我知道这已被多次询问类似的差异，但我在 C#(Unity3D) 中的按位运算输出方面遇到了问题。

我正在尝试做 bit-reversal permutation ，也就是说，为了在 Cooley-Tukey FFT algorithm 中使用的目的，获取整数(或无符号整数，两者之一)的位反转顺序.因此，如果我有 0、1、2、3 - 我想以 0、2、1、3 结束，如果我有 0、1、2、3、4、5、6、7 - 我应该得到 0， 4、2、6、1、5、3、7。

我已经尝试了一些在网上找到的位反转算法，比如这个:

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

我会这样使用它:

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

我想尝试另一种算法，所以我找到了这个算法，正如指出的那样，它反转了字节:

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

我得到了完全相同的数字，x = 2147483648。 >>> 等位运算符在 C# 中执行的功能与在其他语言(如 C)中执行的功能相同，对吧？那么，我错过了一步吗？

Answer 1

您当前使用的算法反转了整数中的位(即 int 为 32 位，long 为 64 位) )，而你真正想要的是仅反转 first k bits(其中 n = 2^k用于位反转排列)。

一个简单的解决方案是使用字符串:

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

哪里Reverse is defined as follows :

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

或者如果您不想使用字符串，您可以坚持使用按位运算符解决方案:

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

您甚至可以以可读性为代价删除三元运算符:

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

& 1补偿了算术右移(>> i)填入符号位的情况。