实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
当前回答
unsigned char ReverseBits(unsigned char data)
{
unsigned char k = 0, rev = 0;
unsigned char n = data;
while(n)
{
k = n & (~(n - 1));
n &= (n - 1);
rev |= (128 / k);
}
return rev;
}
其他回答
原生ARM指令“rbit”可以用1个cpu周期和1个额外的cpu寄存器来完成,不可能被击败。
高效意味着吞吐量或延迟。
从头到尾,看看安德斯·塞德罗尼厄斯的回答,很好。
为了降低延迟,我推荐以下代码:
uint32_t reverseBits( uint32_t x )
{
#if defined(__arm__) || defined(__aarch64__)
__asm__( "rbit %0, %1" : "=r" ( x ) : "r" ( x ) );
return x;
#endif
// Flip pairwise
x = ( ( x & 0x55555555 ) << 1 ) | ( ( x & 0xAAAAAAAA ) >> 1 );
// Flip pairs
x = ( ( x & 0x33333333 ) << 2 ) | ( ( x & 0xCCCCCCCC ) >> 2 );
// Flip nibbles
x = ( ( x & 0x0F0F0F0F ) << 4 ) | ( ( x & 0xF0F0F0F0 ) >> 4 );
// Flip bytes. CPUs have an instruction for that, pretty fast one.
#ifdef _MSC_VER
return _byteswap_ulong( x );
#elif defined(__INTEL_COMPILER)
return (uint32_t)_bswap( (int)x );
#else
// Assuming gcc or clang
return __builtin_bswap32( x );
#endif
}
编译器输出:https://godbolt.org/z/5ehd89
好吧,这基本上与第一个“reverse()”相同,但它是64位的,只需要从指令流中加载一个即时掩码。GCC创建的代码没有跳转,所以这应该是相当快的。
#include <stdio.h>
static unsigned long long swap64(unsigned long long val)
{
#define ZZZZ(x,s,m) (((x) >>(s)) & (m)) | (((x) & (m))<<(s));
/* val = (((val) >>16) & 0xFFFF0000FFFF) | (((val) & 0xFFFF0000FFFF)<<16); */
val = ZZZZ(val,32, 0x00000000FFFFFFFFull );
val = ZZZZ(val,16, 0x0000FFFF0000FFFFull );
val = ZZZZ(val,8, 0x00FF00FF00FF00FFull );
val = ZZZZ(val,4, 0x0F0F0F0F0F0F0F0Full );
val = ZZZZ(val,2, 0x3333333333333333ull );
val = ZZZZ(val,1, 0x5555555555555555ull );
return val;
#undef ZZZZ
}
int main(void)
{
unsigned long long val, aaaa[16] =
{ 0xfedcba9876543210,0xedcba9876543210f,0xdcba9876543210fe,0xcba9876543210fed
, 0xba9876543210fedc,0xa9876543210fedcb,0x9876543210fedcba,0x876543210fedcba9
, 0x76543210fedcba98,0x6543210fedcba987,0x543210fedcba9876,0x43210fedcba98765
, 0x3210fedcba987654,0x210fedcba9876543,0x10fedcba98765432,0x0fedcba987654321
};
unsigned iii;
for (iii=0; iii < 16; iii++) {
val = swap64 (aaaa[iii]);
printf("A[]=%016llX Sw=%016llx\n", aaaa[iii], val);
}
return 0;
}
// Purpose: to reverse bits in an unsigned short integer
// Input: an unsigned short integer whose bits are to be reversed
// Output: an unsigned short integer with the reversed bits of the input one
unsigned short ReverseBits( unsigned short a )
{
// declare and initialize number of bits in the unsigned short integer
const char num_bits = sizeof(a) * CHAR_BIT;
// declare and initialize bitset representation of integer a
bitset<num_bits> bitset_a(a);
// declare and initialize bitset representation of integer b (0000000000000000)
bitset<num_bits> bitset_b(0);
// declare and initialize bitset representation of mask (0000000000000001)
bitset<num_bits> mask(1);
for ( char i = 0; i < num_bits; ++i )
{
bitset_b = (bitset_b << 1) | bitset_a & mask;
bitset_a >>= 1;
}
return (unsigned short) bitset_b.to_ulong();
}
void PrintBits( unsigned short a )
{
// declare and initialize bitset representation of a
bitset<sizeof(a) * CHAR_BIT> bitset(a);
// print out bits
cout << bitset << endl;
}
// Testing the functionality of the code
int main ()
{
unsigned short a = 17, b;
cout << "Original: ";
PrintBits(a);
b = ReverseBits( a );
cout << "Reversed: ";
PrintBits(b);
}
// Output:
Original: 0000000000010001
Reversed: 1000100000000000
我认为下面是我所知道的最简单的方法。MSB是输入,LSB是“反向”输出:
unsigned char rev(char MSB) {
unsigned char LSB=0; // for output
_FOR(i,0,8) {
LSB= LSB << 1;
if(MSB&1) LSB = LSB | 1;
MSB= MSB >> 1;
}
return LSB;
}
// It works by rotating bytes in opposite directions.
// Just repeat for each byte.