实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
当前回答
通用的
C代码。以1字节输入数据num为例。
unsigned char num = 0xaa; // 1010 1010 (aa) -> 0101 0101 (55)
int s = sizeof(num) * 8; // get number of bits
int i, x, y, p;
int var = 0; // make var data type to be equal or larger than num
for (i = 0; i < (s / 2); i++) {
// extract bit on the left, from MSB
p = s - i - 1;
x = num & (1 << p);
x = x >> p;
printf("x: %d\n", x);
// extract bit on the right, from LSB
y = num & (1 << i);
y = y >> i;
printf("y: %d\n", y);
var = var | (x << i); // apply x
var = var | (y << p); // apply y
}
printf("new: 0x%x\n", new);
其他回答
我很好奇原始旋转有多快。 在我的机器(i7@2600)上,1,500,150,000次迭代的平均值为27.28 ns(在131,071个64位整数的随机集上)。
优点:占用内存少,代码简单。我想说它也没有那么大。对于任何输入(128个算术SHIFT运算+ 64个逻辑and运算+ 64个逻辑OR运算),所需的时间都是可预测的常量。
我比较了@Matt J获得的最佳时间,他有公认的答案。如果我没有看错他的答案,他得到的最好结果是0.631739秒,100万次迭代,这导致平均每次旋转631 ns。
我使用的代码片段如下:
unsigned long long reverse_long(unsigned long long x)
{
return (((x >> 0) & 1) << 63) |
(((x >> 1) & 1) << 62) |
(((x >> 2) & 1) << 61) |
(((x >> 3) & 1) << 60) |
(((x >> 4) & 1) << 59) |
(((x >> 5) & 1) << 58) |
(((x >> 6) & 1) << 57) |
(((x >> 7) & 1) << 56) |
(((x >> 8) & 1) << 55) |
(((x >> 9) & 1) << 54) |
(((x >> 10) & 1) << 53) |
(((x >> 11) & 1) << 52) |
(((x >> 12) & 1) << 51) |
(((x >> 13) & 1) << 50) |
(((x >> 14) & 1) << 49) |
(((x >> 15) & 1) << 48) |
(((x >> 16) & 1) << 47) |
(((x >> 17) & 1) << 46) |
(((x >> 18) & 1) << 45) |
(((x >> 19) & 1) << 44) |
(((x >> 20) & 1) << 43) |
(((x >> 21) & 1) << 42) |
(((x >> 22) & 1) << 41) |
(((x >> 23) & 1) << 40) |
(((x >> 24) & 1) << 39) |
(((x >> 25) & 1) << 38) |
(((x >> 26) & 1) << 37) |
(((x >> 27) & 1) << 36) |
(((x >> 28) & 1) << 35) |
(((x >> 29) & 1) << 34) |
(((x >> 30) & 1) << 33) |
(((x >> 31) & 1) << 32) |
(((x >> 32) & 1) << 31) |
(((x >> 33) & 1) << 30) |
(((x >> 34) & 1) << 29) |
(((x >> 35) & 1) << 28) |
(((x >> 36) & 1) << 27) |
(((x >> 37) & 1) << 26) |
(((x >> 38) & 1) << 25) |
(((x >> 39) & 1) << 24) |
(((x >> 40) & 1) << 23) |
(((x >> 41) & 1) << 22) |
(((x >> 42) & 1) << 21) |
(((x >> 43) & 1) << 20) |
(((x >> 44) & 1) << 19) |
(((x >> 45) & 1) << 18) |
(((x >> 46) & 1) << 17) |
(((x >> 47) & 1) << 16) |
(((x >> 48) & 1) << 15) |
(((x >> 49) & 1) << 14) |
(((x >> 50) & 1) << 13) |
(((x >> 51) & 1) << 12) |
(((x >> 52) & 1) << 11) |
(((x >> 53) & 1) << 10) |
(((x >> 54) & 1) << 9) |
(((x >> 55) & 1) << 8) |
(((x >> 56) & 1) << 7) |
(((x >> 57) & 1) << 6) |
(((x >> 58) & 1) << 5) |
(((x >> 59) & 1) << 4) |
(((x >> 60) & 1) << 3) |
(((x >> 61) & 1) << 2) |
(((x >> 62) & 1) << 1) |
(((x >> 63) & 1) << 0);
}
假设你有一个比特数组,怎么样: 1. 从MSB开始,将比特一个一个地推入堆栈。 2. 从这个堆栈弹出位到另一个数组(如果你想节省空间,也可以是同一个数组),将第一个弹出位放入MSB,然后从那里继续到较低的有效位。
Stack stack = new Stack();
Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 };
for (int i = 0; i < bits.Length; i++)
{
stack.push(bits[i]);
}
for (int i = 0; i < bits.Length; i++)
{
bits[i] = stack.pop();
}
当然,玩弄比特的黑客的明显来源是: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
您可能希望使用标准模板库。它可能比上面提到的代码慢。然而,在我看来,这似乎更清楚,更容易理解。
#include<bitset>
#include<iostream>
template<size_t N>
const std::bitset<N> reverse(const std::bitset<N>& ordered)
{
std::bitset<N> reversed;
for(size_t i = 0, j = N - 1; i < N; ++i, --j)
reversed[j] = ordered[i];
return reversed;
};
// test the function
int main()
{
unsigned long num;
const size_t N = sizeof(num)*8;
std::cin >> num;
std::cout << std::showbase << std::hex;
std::cout << "ordered = " << num << std::endl;
std::cout << "reversed = " << reverse<N>(num).to_ulong() << std::endl;
std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl;
}
这不是人类能做的工作!... 但非常适合做机器
这是2015年,距离第一次提出这个问题已经过去了6年。编译器从此成为我们的主人,而我们作为人类的工作只是帮助它们。那么,把我们的意图传达给机器的最佳方式是什么呢?
位反转是如此普遍,以至于你不得不怀疑为什么x86不断增长的ISA没有包含一次性完成它的指令。
原因是:如果你给编译器一个真正简洁的意图,位反转应该只需要大约20个CPU周期。让我向你展示如何制作reverse()并使用它:
#include <inttypes.h>
#include <stdio.h>
uint64_t reverse(const uint64_t n,
const uint64_t k)
{
uint64_t r, i;
for (r = 0, i = 0; i < k; ++i)
r |= ((n >> i) & 1) << (k - i - 1);
return r;
}
int main()
{
const uint64_t size = 64;
uint64_t sum = 0;
uint64_t a;
for (a = 0; a < (uint64_t)1 << 30; ++a)
sum += reverse(a, size);
printf("%" PRIu64 "\n", sum);
return 0;
}
使用Clang版本>= 3.6,-O3, -march=native(用Haswell测试)编译这个示例程序,使用新的AVX2指令提供美术质量代码,运行时为11秒处理~ 10亿reverse()秒。这是~10 ns每反向(),0.5 ns CPU周期假设2 GHz,我们将达到甜蜜的20个CPU周期。
对于单个大数组,您可以在访问RAM一次所需的时间内放入10个reverse() ! 你可以在访问L2缓存LUT两次的时间里放入1个reverse()。
注意:这个示例代码应该可以作为一个不错的基准运行几年,但是一旦编译器足够聪明,可以优化main()只输出最终结果,而不是真正计算任何东西,它最终就会开始显得过时了。但目前它只用于展示reverse()。