N位反向位数
我正在试图找到一个简单的算法，它将一个数字的位数反转到N个比特数。例如：
N= 2：
01 -> 10
11 -> 11N= 3：
001 -> 100
011 -> 110
101 -> 101我一直发现的唯一的事情是如何反转一个完整的字节，但这只适用于N=8，而这并不总是我所需要的。
有谁知道一个算法可以执行这个按位操作吗？我需要做很多的FFT，所以我正在寻找的东西，可以非常优化也。
回答 3
Stack Overflow用户
发布于 2020-07-04 04:40:34
它是按位反向操作的C#实现：
public uint Reverse(uint a, int length)
{
uint b = 0b_0;
for (int i = 0; i < length; i++)
{
b = (b << 1) | (a & 0b_1);
a = a >> 1;
}
return b;
}上面的代码首先将输出值移到左边，然后将输入的最小位置上的位添加到输出，然后将输入移到右边。并重复它，直到所有的比特完成。以下是一些样本：
uint a = 0b_1100;
uint b = Reverse(a, 4); //should be 0b_0011;和
uint a = 0b_100;
uint b = Reverse(a, 3); //should be 0b_001;该实现的时间复杂度为O(N)，其中N是输入的长度。
在Dotnet小提琴中编辑
Stack Overflow用户
发布于 2020-07-04 17:59:33
这里有一个小的查找表解决方案，它对(2<=N<=32)有好处。
对于N==8，我认为每个人都同意256个字节数组查找表是可行的。类似地，对于从2到7的N，可以创建4、8、.128个查找字节数组。
对于N==16，您可以翻转每个字节，然后重新排序这两个字节。类似地，对于N==24，您可以翻转每个字节，然后重新排序(这将使中间的一个翻转，但位置相同)。N==32的工作方式应该是显而易见的。
对于N==9，将其看作是三个3位数字(翻转每个数字，重新排序，然后做一些掩蔽和移动，以使他们在正确的位置)。对于N==10，它是两个5位数.对于N==11来说，中心位两边的两个5位数是不变的。同样适用于N==13 (两个6位数围绕一个不变的中心位)。对于像N==23这样的素数，它将是围绕一个中心7位数的一对8位数。
对于24到32之间的奇数，它变得更加复杂。你可能需要考虑五个不同的数字。以N==29为例，它可能是围绕一个不变的中心位的四个7位数。对于N==31，它将是由一对8位数和一对7位数环绕的中心位。
尽管如此，这是一堆复杂的逻辑。这将是一只需要测试的熊。它可能比@MuhammadVakili的位移位解决方案(当然是针对N<=8)更快，但它可能不会。我建议你接受他的解决方案。
Stack Overflow用户
发布于 2020-07-04 04:46:05
使用字符串操作？
static void Main(string[] args)
{
uint number = 269;
int numBits = 4;
string strBinary = Convert.ToString(number, 2).PadLeft(32, '0');
Console.WriteLine($"{number}");
Console.WriteLine($"{strBinary}");
string strBitsReversed = new string(strBinary.Substring(strBinary.Length - numBits, numBits).ToCharArray().Reverse().ToArray());
string strBinaryModified = strBinary.Substring(0, strBinary.Length - numBits) + strBitsReversed;
uint numberModified = Convert.ToUInt32(strBinaryModified, 2);
Console.WriteLine($"{strBinaryModified}");
Console.WriteLine($"{numberModified}");
Console.Write("Press Enter to Quit.");
Console.ReadLine();
}输出：
269
00000000000000000000000100001101
00000000000000000000000100001011
267
Press Enter to Quit.https://stackoverflow.com/questions/62724992
复制相似问题
腾讯云开发者
