整数的位反转，忽略整数大小和字节顺序
给定一个整数typedef：
typedef unsigned int TYPE; 要么
typedef unsigned long TYPE;
我有以下代码来反转整数的位：
TYPE max_bit= (TYPE)-1; void reverse_int_setup() { TYPE bits= (TYPE)max_bit; while (bits <>= 1, bit_setter<<= 1) if (arg & bit_tester) result|= bit_setter; return result; }
首先需要运行reverse_int_setup（），它存储一个打开最高位的整数，然后对reverse_int（ arg ）的任何调用返回arg ，其位反转（用作二叉树的一个键，取自一个增加反击，但这或多或少无关紧要）。
在调用reverse_int_setup（）之后，是否存在一种与平台无关的方法在编译时为max_int提供正确的值; 否则，是否有一个算法比你对reverse_int（） 更好/更精简 ？
谢谢。
#include #include #define TYPE_BITS sizeof(TYPE)*CHAR_BIT typedef unsigned long TYPE; TYPE reverser(TYPE n) { TYPE nrev = 0, i, bit1, bit2; int count; for(i = 0; i < TYPE_BITS; i += 2) { /*In each iteration, we swap one bit on the 'right half' of the number with another on the left half*/ count = TYPE_BITS - i - 1; /*this is used to find how many positions to the left (and right) we gotta move the bits in this iteration*/ bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/ bit1 <<= count; /*Shift it to where it belongs*/ bit2 = n & 1<<((i/2) + count); /*Find the 'left half' bit*/ bit2 >>= count; /*Place that bit in bit1's original position*/ nrev |= bit1; /*Now add the bits to the reversal result*/ nrev |= bit2; } return nrev; } int main() { TYPE n = 6; printf("%lu", reverser(n)); return 0; }
这次我使用了来自TK的’位数’的想法，但是假设一个字节包含8位而不是使用CHAR_BIT宏，它使它更具可移植性。 现在代码更高效（删除了内部for循环）。 我希望这次代码也略显神秘。 🙂
使用计数的需要是我们必须在每次迭代中移位一点的位置数量 – 我们必须将最右边的位移动31个位置（假设32位数），第二个最右位移动29个位置等等上。 因此，随着i的增加，计数必须随着每次迭代而减少。
希望有点信息certificate有助于理解代码……
以下程序用于演示用于反转位的更精简算法，可以轻松扩展以处理64位数。
#include #include int main(int argc, char**argv) { int32_t x; if ( argc != 2 ) { printf("Usage: %s hexadecimal\n", argv[0]); return 1; } sscanf(argv[1],"%x", &x); /* swap every neigbouring bit */ x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1; /* swap every 2 neighbouring bits */ x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2; /* swap every 4 neighbouring bits */ x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4; /* swap every 8 neighbouring bits */ x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8; /* and so forth, for say, 32 bit int */ x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16; printf("0x%x\n",x); return 0; }
此代码不应包含错误，并使用0x12345678进行测试以生成0x1e6a2c48，这是正确的答案。
typedef unsigned long TYPE; TYPE reverser(TYPE n) { TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2; int count; for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2) { /*In each iteration, we swap one bit on the 'right half' of the number with another on the left half*/ k = 1<>= count; nrev |= nrevbit1; nrev |= nrevbit2; } return nrev; }
这在Windows下的gcc中工作正常，但我不确定它是否完全独立于平台。 一些值得关注的地方是：
-
for循环中的条件 – 它假设当你离开第1位超出最左边的位时，你得到一个0，1’掉出来’（我期望的和旧的Turbo C给出的iirc），或者1圈，你得到1（似乎是gcc的行为）。
-
内部while循环中的条件：见上文。 但是这里发生了一件奇怪的事情：在这种情况下，gcc似乎让1掉线而不是绕圈！
代码可能会被certificate是神秘的：如果您有兴趣并需要解释，请不要犹豫 – 我会把它放在某个地方。
@ΤΖΩΤΖΙΟΥ
在回答ΤΖΩΤΖΙΟΥ的评论时，我提出了上面的修改版本，它取决于位宽的上限。
#include #include typedef int32_t TYPE; TYPE reverse(TYPE x, int bits) { TYPE m=~0; switch(bits) { case 64: x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16; case 32: x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16; case 16: x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8; case 8: x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4; x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2; x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1; } return x; } int main(int argc, char**argv) { TYPE x; TYPE b = (TYPE)-1; int bits; if ( argc != 2 ) { printf("Usage: %s hexadecimal\n", argv[0]); return 1; } for(bits=1;b;b<<=1,bits++); --bits; printf("TYPE has %d bits\n", bits); sscanf(argv[1],"%x", &x); printf("0x%x\n",reverse(x, bits)); return 0; }
笔记：
- gcc将警告64位常数
- printfs也会生成警告
- 如果您需要超过64位，则代码应该足够简单以扩展
我提前为上面提到的编码犯罪道歉 - 怜悯先生！
有一个很好的“Bit Twiddling Hacks”集合，包括在http://graphics.stanford.edu/~seander/bithacks.html用C编码的各种简单且不那么简单的位反转算法。
我个人喜欢“明显的”算法（ http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious ），因为它很明显。 其他一些可能需要较少的指令来执行。 如果我真的需要优化一些东西，我可能会选择不那么明显但速度更快的版本。 否则，为了便于阅读，可维护性和可移植性，我会选择明显的一个。
这是一个更普遍有用的变体。 它的优点是能够在需要反转的值的位长度 – 代码字 – 未知但仍保证不超过我们称之为maxLength的值的情况下工作。 这种情况的一个很好的例子是霍夫曼代码解压缩。
下面的代码适用于长度为1到24位的代码字。 它已针对Pentium D的快速执行进行了优化。请注意，每次使用时它会访问查找表多达3次。 我尝试了许多变体，以较大的表（4096和65,536个条目）为代价将该数量减少到2。 具有256字节表的这个版本是明显的赢家，部分原因是它对于表数据在高速缓存中是如此有利，并且可能还因为处理器具有8位表查找/转换指令。
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}; const unsigned short masks[17] = {0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00}; unsigned long codeword; // value to be reversed, occupying the low 1-24 bits unsigned char maxLength; // bit length of longest possible codeword (<= 24) unsigned char sc; // shift count in bits and index into masks array if (maxLength <= 8) { codeword = table[codeword << (8 - maxLength)]; } else { sc = maxLength - 8; if (maxLength <= 16) { codeword = (table[codeword & 0X00FF] << sc) | table[codeword >> sc]; } else if (maxLength & 1) // if maxLength is 17, 19, 21, or 23 { codeword = (table[codeword & 0X00FF] << sc) | table[codeword >> sc] | (table[(codeword & masks[sc]) >> (sc - 8)] << 8); } else // if maxlength is 18, 20, 22, or 24 { codeword = (table[codeword & 0X00FF] << sc) | table[codeword >> sc] | (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1)); } }
怎么样：
long temp = 0; int counter = 0; int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary) while(value > 0) // loop until value is empty { temp <<= 1; // shift whatever was in temp left to create room for the next bit temp |= (value & 0x01); // get the lsb from value and set as lsb in temp value >>= 1; // shift value right by one to look at next lsb counter++; } value = temp; if (counter < number_of_bits) { value <<= counter-number_of_bits; }
（我假设你知道有多少位值，它存储在number_of_bits中）
显然，temp需要是最长的可想象的数据类型，当你将temp复制回值时，temp中所有无关的位都应该神奇地消失（我想！）。
或者，'c'方式是说：
while(value)
你的选择
我们可以存储将所有可能的1字节序列反转到一个数组中的结果（256个不同的条目），然后使用查找组合到这个表和一些oring逻辑来获得整数的反转。
这是TK解决方案的变化和修正，可能比sundar的解决方案更清晰。 它需要来自t的单个位并将它们推送到return_val：
typedef unsigned long TYPE; #define TYPE_BITS sizeof(TYPE)*8 TYPE reverser(TYPE t) { unsigned int i; TYPE return_val = 0 for(i = 0; i < TYPE_BITS; i++) {/*foreach bit in TYPE*/ /* shift the value of return_val to the left and add the rightmost bit from t */ return_val = (return_val << 1) + (t & 1); /* shift off the rightmost bit of t */ t = t >> 1; } return(return_val); }
通用方法帽适用于任何类型的任何类型的对象将是反转对象的字节，并且反转每个字节中的位的顺序。 在这种情况下，位级算法与具体的位数（一个字节）相关联，而“变量”逻辑（关于大小）则被提升到整个字节的水平。
这是我对freespace解决方案的概括（如果我们有一天得到128位机器）。 当使用gcc -O3编译时，它会产生无跳转代码，并且显然对理智机器上foo_t的定义不敏感。 不幸的是，它确实取决于转变是2的力量！
#include #include typedef unsigned long foo_t; foo_t reverse(foo_t x) { int shift = sizeof (x) * CHAR_BIT / 2; foo_t mask = (1 << shift) - 1; int i; for (i = 0; shift; i++) { x = ((x & mask) << shift) | ((x & ~mask) >> shift); shift >>= 1; mask ^= (mask << shift); } return x; } int main() { printf("reverse = 0x%08lx\n", reverse(0x12345678L)); }
如果位反转是时间关键的，并且主要与FFT结合，则最好存储整个位反转arrays。 在任何情况下，该arrays的尺寸都小于必须在FFT Cooley-Tukey算法中预先计算的单位根。 计算arrays的简单方法是：
int BitReverse[Size]; // Size is power of 2 void Init() { BitReverse[0] = 0; for(int i = 0; i < Size/2; i++) { BitReverse[2*i] = BitReverse[i]/2; BitReverse[2*i+1] = (BitReverse[i] + Size)/2; } } // end it's all