热门：培训标准变量字符串环境数字数据工具名称基础工作密码信息设备元素单位管理文件位置标签应用程序学习文档设置服务状态

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

2023-04-15 09:56:00

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

1
while(value)

你的选择

反转字节序整数忽略

推荐阅读

    linux查看大小命令？

    linux查看大小命令？

    linux查看大小命令？，系统，设备，档案，电脑，信息，软件，单位，状态，大小，文件夹，

    linux命令分大小写吗？

    linux命令分大小写吗？

    linux命令分大小写吗？，系统，名称，命令，大小写，设备，目录，文件名，变量，语言，

    linux判断大小端命令？

    linux判断大小端命令？

    linux判断大小端命令？，地址，工作，代码，地方，设计，命令，目录，标准，系统，文件，L

    linux中分命令大小写？

    linux中分命令大小写？

    linux中分命令大小写？，系统，工作，地址，大小写，命令，目录，管理，名称，信息，文

    linux命令行字体大小？

    linux命令行字体大小？

    linux命令行字体大小？，系统，等级，图片，数字，工具，终端，字体，字符，图形界面，

    linux内存大小命令？

    linux内存大小命令？

    linux内存大小命令？，系统，情况，电脑，信息，工具，状态，命令，内存，环境，分析，Lin

    linux命令忽略错误？

    linux命令忽略错误？

    linux命令忽略错误？，系统，地址，工作，信息，设备，命令，设计，灵活，观察，标准，lin

    linux命令按大小排序？

    linux命令按大小排序？

    linux命令按大小排序？，数字，地址，时间，工作，标准，系统，命令，信息，单位，软件，l

    linux命令显示总大小？

    linux命令显示总大小？

    linux命令显示总大小？，系统，情况，信息，命令，单位，服务，第一，档案，大小，文件

    linux查看命令大小？

    linux查看命令大小？

    linux查看命令大小？，系统，档案，情况，大小，命令，名称，电脑，单位，地址，时间，lin

    linux命令空间大小？

    linux命令空间大小？

    linux命令空间大小？，系统，信息，情况，单位，命令，设备，公司，地址，大小，空间，如

    linux的命令大小写？

    linux的命令大小写？

    linux的命令大小写？，系统，大小写，数字，信息，命令，名称，文件，目录，文件夹，文

    linux命令行文件大小？

    linux命令行文件大小？

    linux命令行文件大小？，情况，档案，系统，单位，信息，文件，大小，文件夹，命令，文

    python之转换大小写

    python之转换大小写

    python之转换大小写，预期，数字，培训，字符串，方法，大小写，结果，下面，不得而

    python如何调节音量大小

    python如何调节音量大小

    python如何调节音量大小，系统，电脑，代码，音量，公式，培训，时间，代表，数值，静