整数的位反转，忽略整数的大小和字节序
时间：2020-03-05 18:53:41 来源:igfitidea点击:
给定一个整数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)
max_bit= bits;
}
TYPE reverse_int(TYPE arg)
{
TYPE bit_setter= 1, bit_tester= max_bit, result= 0;
for (result= 0; bit_tester; bit_tester>>= 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()的算法更好/更精简？
谢谢。
解决方案
回答
怎么样：
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个不同的条目)中，然后使用对表的查找和一些逻辑运算的组合来获取整数的反转。
回答
下面的程序用于演示用于反转位的精简算法，该算法可以轻松扩展以处理64位数字。
#include <stdio.h>
#include <stdint.h>
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<<i; /*this is used to find how many positions
to the left (or right, for the other bit)
we gotta move the bits in this iteration*/
count = 0;
while(k << 1 && k << 1 != 1)
{
k <<= 1;
count++;
}
nrevbit1 = n & (1<<(i/2));
nrevbit1 <<= count;
nrevbit2 = n & 1<<((i/2) + count);
nrevbit2 >>= count;
nrev |= nrevbit1;
nrev |= nrevbit2;
}
return nrev;
}
在Windows下的gcc中，这可以正常工作，但是我不确定它是否完全独立于平台。一些值得关注的地方是：
- for循环中的条件-假设当我们将shift 1移到最左边的位之外时，我们会得到0且其中的1个"掉出"(我期望的是什么，以及旧Turbo C给出的iirc是什么)，或者绕1圈，我们得到1(这似乎是gcc的行为)。
- 内部while循环中的条件：请参见上文。但是这里发生了一件奇怪的事情：在这种情况下，gcc似乎会让1掉下来而不是盘旋！
该代码可能证明是含糊的：如果我们有兴趣并需要解释，请不要犹豫，我将它放在某个地方。
回答
#include<stdio.h>
#include<limits.h>
#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循环)。我希望这次代码的加密性也有所降低。 :)
使用count的需要是，在每次迭代中，我们必须移动一位的位置数会有所不同，我们必须将最右边的位移动31个位置(假设为32位)，将最右边的第二位移动29个位置，依此类推。 。因此，随着i的增加，每次迭代的计数都必须减少。
希望能证明一点点信息对理解代码有所帮助...
回答
这是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);
}
回答
@
为了回应的评论，我介绍了以上版本的修改版本，具体取决于比特宽度的上限。
#include <stdio.h>
#include <stdint.h>
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位，则代码应足够简单以扩展
对于因犯下善意的先生而犯下的编码罪行，我事先表示歉意！
回答
http://graphics.stanford.edu/~seander/bithacks.html上有很多不错的" Bit Twiddling Hacks"，其中包括各种用C编码的简单和不太简单的位反转算法。
我个人喜欢"显而易见的"算法(http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious)，因为很明显。其他一些可能需要较少的指令来执行。如果我真的需要优化某些东西，我可以选择不太明显但较快的版本。否则，出于可读性，可维护性和可移植性的考虑，我将选择"显而易见的"。
回答
这是一个更普遍有用的变体。它的优势在于它可以在以下情况下工作：待反转的值(代码字)的位长未知，但保证不超过我们称为maxLength的值。这种情况的一个很好的例子是霍夫曼代码解压缩。
以下代码适用于长度为1到24位的代码字。它已针对奔腾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));
}
}
回答
通用方法适用于任何大小的任何类型的对象，即反转对象的字节序，并反转每个字节中的位序。在这种情况下，位级算法与具体的位数(一个字节)相关联，而"可变"逻辑(关于大小)则提升到整个字节级。
回答
如果位反转是时间紧迫的，并且主要与FFT结合使用，则最好是存储整个位反转阵列。无论如何，此数组的大小将小于必须在FFT Cooley-Tukey算法中预先计算的单位根。一种简单的计算数组的方法是：
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
