整数的位反转,忽略整数大小和字节顺序

Question

给定一个整数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()更好/更精简？

谢谢.

Answer 1

以下程序用于演示用于反转位的更精简算法,可以轻松扩展以处理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,这是正确的答案.

Answer 2

#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循环).我希望这次代码也略显神秘.:)

使用计数的需要是我们必须在每次迭代中移位一点的位置数量 - 我们必须将最右边的位移动31个位置(假设32位数),第二个最右边的位移动29个位置等等上.因此,随着i的增加,计数必须随着每次迭代而减少.

希望有点信息证明有助于理解代码......