在C / C ++中,最简单的方法是颠倒一个字节中的位的顺序?

虽然有多种方法可以反转字节中的位顺序,但我很好奇开发人员实现的“最简单”。 而通过颠倒我的意思是:

1110 -> 0111 0010 -> 0100 

这是相似的,但不是这个 PHP问题的重复。

这是类似的,但不是这个 C问题的重复。 这个问题是要求开发人员实现最简单的方法。 “最佳algorithm”与内存和CPU性能有关。

如果你正在谈论一个字节,一个表查找可能是最好的select,除非由于某种原因,你没有256字节可用。

这应该工作:

 unsigned char reverse(unsigned char b) { b = (b & 0xF0) >> 4 | (b & 0x0F) << 4; b = (b & 0xCC) >> 2 | (b & 0x33) << 2; b = (b & 0xAA) >> 1 | (b & 0x55) << 1; return b; } 

首先左边的四位与右边的四位交换。 然后所有相邻的对被交换,然后是所有相邻的单个位。 这导致相反的顺序。

我认为查找表必须是最简单的方法之一。 但是,您不需要完整的查找表。

 //Index 1==0b0001 => 0b1000 //Index 7==0b0111 => 0b1110 //etc static unsigned char lookup[16] = { 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, }; uint8_t reverse(uint8_t n) { // Reverse the top and bottom nibble then swap them. return (lookup[n&0b1111] << 4) | lookup[n>>4]; } // Detailed breakdown of the math // + lookup reverse of bottom nibble // | + grab bottom nibble // | | + move bottom result into top nibble // | | | + combine the bottom and top results // | | | | + lookup reverse of top nibble // | | | | | + grab top nibble // VVVVVV // (lookup[n&0b1111] << 4) | lookup[n>>4] 

这很容易编码和validation视觉。
最终,这甚至可能比全表快。 位algorithm便宜,表很容易适应caching线。

看到有点混乱的黑客许多解决scheme。 从那里复制是显而易见的。 =)

例如(在一个32位的CPU上):

 uint8_t b = byte_to_reverse; b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

如果通过“简单实施”,就意味着在考试或面试中没有参考就可以完成的任务,那么最安全的做法可能是以相反的顺序将比特逐一复制到另一个variables中(已经在其他答案中显示)。

由于没有人发布完整的表查找解决scheme,这里是我的:

 unsigned char reverse_byte(unsigned char x) { static const unsigned char table[] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, }; return table[x]; } 
 template <typename T> T reverse(T n, size_t b = sizeof(T) * CHAR_BIT) { assert(b <= std::numeric_limits<T>::digits); T rv = 0; for (size_t i = 0; i < b; ++i, n >>= 1) { rv = (rv << 1) | (n & 0x01); } return rv; } 

编辑:

将其转换为带有可选位数的模板

两行:

 for(i=0;i<8;i++) reversed |= ((original>>i) & 0b1)<<(7-i); 

或者如果你有“0b1”部分的问题:

 for(i=0;i<8;i++) reversed |= ((original>>i) & 1)<<(7-i); 

“原始”是你想要反转的字节。 结果是“反转”,初始化为0。

虽然可能不能移植,但我会使用汇编语言。
许多汇编语言都有指令将进位标志旋转一点,并将进位标志旋转到字(或字节)中。

该algorithm是:

 for each bit in the data type: rotate bit into carry flag rotate carry flag into destination. end-for 

这样的高级语言代码要复杂得多,因为C和C ++不支持旋转从进位转动。 进位标志必须build模。

编辑:例如汇编语言

 ; Enter with value to reverse in R0. ; Assume 8 bits per byte and byte is the native processor type. LODI, R2 8 ; Set up the bit counter Loop: RRC, R0 ; Rotate R0 right into the carry bit. RLC, R1 ; Rotate R1 left, then append carry bit. DJNZ, R2 Loop ; Decrement R2 and jump if non-zero to "loop" LODR, R0 R1 ; Move result into R0. 

最简单的方法可能是遍历循环中的位位置:

 unsigned char reverse(unsigned char c) { int shift; unsigned char result = 0; for (shift = 0; shift < CHAR_BITS; shift++) { if (c & (0x01 << shift)) result |= (0x80 >> shift); } return result; } 

你可能对std::vector<bool> (这是位打包的)和std::bitset感兴趣

它应该是最简单的要求。

 #include <iostream> #include <bitset> using namespace std; int main() { bitset<8> bs = 5; bitset<8> rev; for(int ii=0; ii!= bs.size(); ++ii) rev[bs.size()-ii-1] = bs[ii]; cerr << bs << " " << rev << endl; } 

其他选项可能会更快。

编辑:我欠你一个解决scheme,使用std::vector<bool>

 #include <algorithm> #include <iterator> #include <iostream> #include <vector> using namespace std; int main() { vector<bool> b{0,0,0,0,0,1,0,1}; reverse(b.begin(), b.end()); copy(b.begin(), b.end(), ostream_iterator<int>(cerr)); cerr << endl; } 

第二个示例需要c ++ 0x扩展(用{...}来初始化数组)。 使用bitsetstd::vector<bool> (或boost::dynamic_bitset )的优点是,您不限于字节或单词,但可以反转任意数量的位。

HTH

对于恒定的8位input,运行时无需存储器或CPU。

 #define MSB2LSB(b) (((b)&1?128:0)|((b)&2?64:0)|((b)&4?32:0)|((b)&8?16:0)|((b)&16?8:0)|((b)&32?4:0)|((b)&64?2:0)|((b)&128?1:0)) 

我用ARINC-429这个标签的位顺序(字节顺序)与字的其余部分相反。 标签通常是一个常数,而且通常是八进制的。 例如:

 #define LABEL_HF_COMM MSB2LSB(0205) 

我发现下面的解决scheme比我在这里看到的其他的小提琴algorithm更简单。

 unsigned char reverse_byte(char a) { return ((a & 0x1) << 7) | ((a & 0x2) << 5) | ((a & 0x4) << 3) | ((a & 0x8) << 1) | ((a & 0x10) >> 1) | ((a & 0x20) >> 3) | ((a & 0x40) >> 5) | ((a & 0x80) >> 7); } 

它获取字节中的每一位,并相应地从第一个位置到最后一个位置进行移位。 说明:

  ((a & 0x1) << 7) //get first bit on the right and shift it into the first left position | //add it to ((a & 0x2) // << 5) //the second bit, shifted to the second position from the left //and so on 

表查找或

 uint8_t rev_byte(uint8_t x) { uint8_t y; uint8_t m = 1; while (m) { y >>= 1; if (m&x) { y |= 0x80; } m <<=1; } return y; } 

编辑

在这里寻找其他解决scheme,可能会更好地为您服务

在实现任何algorithm解决scheme之前,请检查汇编语言以了解您正在使用的任何CPU架构。 你的架构可能包含像这样处理按位操作的指令(以及比单个汇编指令更简单的操作)。

如果这样的指令不可用,那么我会build议去查找表路线。 您可以编写一个脚本/程序为您生成表格,查找操作将比此处的任何位反转algorithm更快(以必须在某处存储查找表为代价)。

一个更慢但更简单的实现:

 static int swap_bit(unsigned char unit) { /* * swap bit[7] and bit[0] */ unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f)); unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01))) | (unit & 0xfe)); unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f)); /* * swap bit[6] and bit[1] */ unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf)); unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02))) | (unit & 0xfd)); unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf)); /* * swap bit[5] and bit[2] */ unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf)); unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04))) | (unit & 0xfb)); unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf)); /* * swap bit[4] and bit[3] */ unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef)); unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08))) | (unit & 0xf7)); unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef)); return unit; } 

这可以快速解决?

 int byte_to_be_reversed = ((byte_to_be_reversed>>7)&0x01)|((byte_to_be_reversed>>5)&0x02)| ((byte_to_be_reversed>>3)&0x04)|((byte_to_be_reversed>>1)&0x08)| ((byte_to_be_reversed<<7)&0x80)|((byte_to_be_reversed<<5)&0x40)| ((byte_to_be_reversed<<3)&0x20)|((byte_to_be_reversed<<1)&0x10); 

摆脱使用循环的喧嚣! 但专家请告诉我,如果这是有效的,更快?

  xor ax,ax xor bx,bx mov cx,8 mov al,original_byte! cycle: shr al,1 jnc not_inc inc bl not_inc: test cx,cx jz,end_cycle shl bl,1 loop cycle end_cycle: 

反转的字节将在bl寄存器

 #include <stdio.h> #include <stdlib.h> int main() { int i; unsigned char rev = 0x70 ; // 0b01110000 unsigned char tmp = 0; for(i=0;i<8;i++) { tmp |= ( ((rev & (1<<i))?1:0) << (7-i)); } rev = tmp; printf("%x", rev); //0b00001110 binary value of given number return 0; } 

这是一个古老的问题,但似乎没有人显示清楚简单的方法(最接近edW)。 我用C#(和美妙的LinqPad来testing这个),但是这个例子中没有任何东西不能在C中轻易完成。

将以下内容粘贴到美妙的LinqPad( https://www.linqpad.net/ )中(这是我testing的地方):

 void PrintBinary(string prompt, int num, int pad = 8) { Debug.WriteLine($"{prompt}: {Convert.ToString(num, 2).PadLeft(pad, '0')}"); } int ReverseBits(int num) { int result = 0; int saveBits = num; for (int i = 1; i <= 8; i++) { // Move the result one bit to the left result = result << 1; //PrintBinary("saveBits", saveBits); // Extract the right-most bit var nextBit = saveBits & 1; //PrintBinary("nextBit", nextBit, 1); // Add our extracted bit to the result result = result | nextBit; //PrintBinary("result", result); // We're done with that bit, rotate it off the right saveBits = saveBits >> 1; //Debug.WriteLine(""); } return result; } void PrintTest(int nextNumber) { var result = ReverseBits(nextNumber); Debug.WriteLine("---------------------------------------"); PrintBinary("Original", nextNumber); PrintBinary("Reverse", result); } void Main() { // Calculate the reverse for each number between 1 and 255 for (int x = 250; x < 256; x++) PrintTest(x); } 
 #define BITS_SIZE 8 int reverseBits ( int a ) { int rev = 0; int i; /* scans each bit of the input number*/ for ( i = 0; i < BITS_SIZE - 1; i++ ) { /* checks if the bit is 1 */ if ( a & ( 1 << i ) ) { /* shifts the bit 1, starting from the MSB to LSB * to build the reverse number */ rev |= 1 << ( BITS_SIZE - 1 ) - i; } } return rev; } 

这个是基于BobStein-VisiBone提供的

 #define reverse_1byte(b) ( ((uint8_t)b & 0b00000001) ? 0b10000000 : 0 ) | \ ( ((uint8_t)b & 0b00000010) ? 0b01000000 : 0 ) | \ ( ((uint8_t)b & 0b00000100) ? 0b00100000 : 0 ) | \ ( ((uint8_t)b & 0b00001000) ? 0b00010000 : 0 ) | \ ( ((uint8_t)b & 0b00010000) ? 0b00001000 : 0 ) | \ ( ((uint8_t)b & 0b00100000) ? 0b00000100 : 0 ) | \ ( ((uint8_t)b & 0b01000000) ? 0b00000010 : 0 ) | \ ( ((uint8_t)b & 0b10000000) ? 0b00000001 : 0 ) 

我非常喜欢这个,因为编译器自动为你处理工作,因此不需要更多的资源。

这也可以扩展到16位…

 #define reverse_2byte(b) ( ((uint16_t)b & 0b0000000000000001) ? 0b1000000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000000010) ? 0b0100000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000000100) ? 0b0010000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000001000) ? 0b0001000000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000010000) ? 0b0000100000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000000100000) ? 0b0000010000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000001000000) ? 0b0000001000000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000010000000) ? 0b0000000100000000 : 0 ) | \ ( ((uint16_t)b & 0b0000000100000000) ? 0b0000000010000000 : 0 ) | \ ( ((uint16_t)b & 0b0000001000000000) ? 0b0000000001000000 : 0 ) | \ ( ((uint16_t)b & 0b0000010000000000) ? 0b0000000000100000 : 0 ) | \ ( ((uint16_t)b & 0b0000100000000000) ? 0b0000000000010000 : 0 ) | \ ( ((uint16_t)b & 0b0001000000000000) ? 0b0000000000001000 : 0 ) | \ ( ((uint16_t)b & 0b0010000000000000) ? 0b0000000000000100 : 0 ) | \ ( ((uint16_t)b & 0b0100000000000000) ? 0b0000000000000010 : 0 ) | \ ( ((uint16_t)b & 0b1000000000000000) ? 0b0000000000000001 : 0 ) 
 typedef struct { uint8_t b0:1; uint8_t b1:1; uint8_t b2:1; uint8_t b3:1; uint8_t b4:1; uint8_t b5:1; uint8_t b6:1; uint8_t b7:1; } bits_t; uint8_t reverse_bits(uint8_t src) { uint8_t dst = 0x0; bits_t *src_bits = (bits_t *)&src; bits_t *dst_bits = (bits_t *)&dst; dst_bits->b0 = src_bits->b7; dst_bits->b1 = src_bits->b6; dst_bits->b2 = src_bits->b5; dst_bits->b3 = src_bits->b4; dst_bits->b4 = src_bits->b3; dst_bits->b5 = src_bits->b2; dst_bits->b6 = src_bits->b1; dst_bits->b7 = src_bits->b0; return dst; } 

这个怎么样…

 int value = 0xFACE; value = ((0xFF & value << 8) | (val >> 8); 

如果只是XOR与0xFF的字节。

unsigned char reverse(unsigned char b) { b ^= 0xFF; return b; }