实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
当前回答
您可能希望使用标准模板库。它可能比上面提到的代码慢。然而,在我看来,这似乎更清楚,更容易理解。
#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;
}
其他回答
另一个基于循环的解决方案,在数量较低时快速退出(在c++中用于多种类型)
template<class T>
T reverse_bits(T in) {
T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1);
T out;
for (out = 0; bit && in; bit >>= 1, in >>= 1) {
if (in & 1) {
out |= bit;
}
}
return out;
}
或者C语言中unsigned int
unsigned int reverse_bits(unsigned int in) {
unsigned int bit = 1u << (sizeof(T) * 8 - 1);
unsigned int out;
for (out = 0; bit && in; bit >>= 1, in >>= 1) {
if (in & 1)
out |= bit;
}
return out;
}
通用的
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);
原生ARM指令“rbit”可以用1个cpu周期和1个额外的cpu寄存器来完成,不可能被击败。
假设你有一个比特数组,怎么样: 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();
}
伪代码中的位反转
源-要反转的>字节b00101100 Destination ->反转,也需要为unsigned类型,这样符号位就不会向下传播
复制到临时,因此原始不受影响,还需要为unsigned类型,以便符号位不会自动移位
bytecopy = b0010110
循环8://执行8次 测试字节拷贝是否< 0(负)
set bit8 (msb) of reversed = reversed | b10000000
else do not set bit8
shift bytecopy left 1 place
bytecopy = bytecopy << 1 = b0101100 result
shift result right 1 place
reversed = reversed >> 1 = b00000000
8 times no then up^ LOOP8
8 times yes then done.