关于C#：整数的位反转，忽略整数的大小和字节序

Bit reversal of an integer, ignoring integer size and endianness

给定一个整数typedef：

1	typedef unsigned int TYPE;

要么

1	typedef unsigned long TYPE;

我有以下代码来反转整数的位：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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()的算法更好/更精简？

谢谢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#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的增加，每次迭代的计数必须减少。

希望事实证明对理解代码有帮助...

下面的程序用于演示用于反转位的精简算法，该算法可以轻松扩展以处理64位数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
int32_t x;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal
", 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
",x);
return 0;
}

该代码不应包含错误，并且已使用0x12345678进行了测试，以产生0x1e6a2c48，这是正确的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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掉下来而不是盘旋！

该代码可能证明是含糊的：如果您有兴趣并需要解释，请不要犹豫-我将它放在某个地方。

这是一个更有用的变体。它的优点是可以在需要反转的值(代码字)的位长未知的情况下工作，但可以保证不超过我们称为maxLength的值。这种情况的一个很好的例子是霍夫曼代码解压缩。

以下代码适用于1到24位长度的代码字。它已针对奔腾D上的快速执行进行了优化。请注意，每次使用该表最多可访问3次。我尝试了许多变体，但以较大的表(4096和65,536个条目)为代价将该数字减少到2。带有256字节表的该版本无疑是赢家，部分原因是它对于将表数据存储在缓存中非常有优势，也许还因为处理器具有8位表查找/转换指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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));
}
}

http://graphics.stanford.edu/~seander/bithacks.html上有许多不错的" Bit Twiddling Hacks"，其中包括各种用C编码的简单和不太简单的位反转算法。

我个人喜欢"显而易见的"算法(http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious)，因为很明显。其他一些可能需要较少的指令来执行。如果我真的需要优化某些东西，我可以选择不太明显但较快的版本。否则，出于可读性，可维护性和可移植性的考虑，我将选择"显而易见的"。

为了回应ΤζΩΤΙΙΙΟΥ的评论，我提出了上面的修改版本，具体取决于比特宽度的上限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#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
", argv[0]);
return 1;
}
for(bits=1;b;b<<=1,bits++);
--bits;
printf("TYPE has %d bits
", bits);
sscanf(argv[1],"%x", &x);

printf("0x%x
",reverse(x, bits));
return 0;
}

笔记：

gcc将警告64位常量
printfs也会生成警告
如果您需要超过64位，则代码应足够简单以扩展

对于我在上面犯下的编码罪行，我预先表示歉意-先生，好！

这是我对自由空间解决方案的概括(以防万一我们有一天获得128位计算机)。当使用gcc -O3编译时，它会产生无跳动的代码，并且显然对健全机器上的foo_t的定义不敏感。不幸的是，它确实取决于移位是否为2的幂！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <limits.h>
#include <stdio.h>

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
", reverse(0x12345678L));
}

如果位反转是时间紧迫的，并且主要与FFT结合使用，则最好是存储整个位反转阵列。无论如何，该数组的大小将小于必须在FFT Cooley-Tukey算法中预先计算的单位根。一种简单的计算数组的方法是：

1
2
3
4
5
6
7
8
9
10

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

通用方法适用于任何大小的任何类型的对象，即反转对象的字节序，并反转每个字节中的位序。在这种情况下，位级算法与具体的位数(一个字节)相关联，而"可变"逻辑(关于大小)则提升到整个字节级。

这是对TK解决方案的一种变型和更正，它可能比sundar的解决方案更清晰。它从t中获取单个位并将其推入return_val：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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);
}

我们可以将所有可能的1字节序列反转的结果存储在一个数组中(256个不同的条目)，然后将对表的查找与某些或逻辑的组合使用以获得整数的反转。

怎么样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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"方式是说：