c++ - 整数的反向位

This question already has answers here:

Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C

(26个答案)


2年前关闭。




我遇到一个面试问题。 32位无符号整数的反向位。我写的这段代码是完全可以的:

uint32_t reverseBits(uint32_t n) {
    for(int i = 0, j = 31; i < j; i++, j--) {
        bool iSet = (bool)(n & (1 << i));
        bool jSet = (bool)(n & (1 << j));
        n &= ~(1 << j);
        n &= ~(1 << i);
        if(iSet) n |= (1 << j);
        if(jSet) n |= (1 << i);
    }
    return n;
}

此后，还有一个后续问题-如果多次调用此函数，您将如何对其进行优化？ 我无法弄清楚在这种情况下应如何优化解决方案。

最佳答案

您可以使用反向查找表来优化循环。
有关更多详细信息，您可以遵循this URL，我从下面的代码中获取了URL。

// Generate a lookup table for 32bit operating system
// using macro
#define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )

// Lookup table that store the reverse of each table
unsigned int lookuptable[256] = { R6(0), R6(2), R6(1), R6(3) };

/* Function to reverse bits of num */
int reverseBits(unsigned int num)
{
    int reverse_num = 0;

     // Reverse and then rearrange

                   // first chunk of 8 bits from right
     reverse_num = lookuptable[ num & 0xff ]<<24 |

                   // second chunk of 8 bits from  right
                   lookuptable[ (num >> 8) & 0xff ]<<16 |

                   lookuptable[ (num >> 16 )& 0xff ]<< 8 |
                   lookuptable[ (num >>24 ) & 0xff ] ;

    return reverse_num;
}

关于c++ - 整数的反向位，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52506679/