跳转至

LeetCode: 190. 颠倒二进制位

1、题目描述

颠倒给定的 32 位无符号整数的二进制位。

示例:

输入: 43261596
输出: 964176192
解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ,
     返回 964176192,其二进制表示形式为 00111001011110000010100101000000 。

进阶: 如果多次调用这个函数,你将如何优化你的算法?

2、解题思路

2.1 移位交换法

​ 我们可以这样进行考虑,先将高16位和第16位进行交换

​ 然后将高低16位中的高低8位进行交换

​ 然后每8位中的4位进行交换

​ 然后是每4位中的2位交换位置

​ 然后是每两位交换位置

​ 总结起来,以最高位为例,先右移6位,然后是8位,在来4位,2位,1位

uint32_t reverseBits(uint32_t n) {
    uint32_t temp = n;
    temp = (temp & 0xffff0000) >> 16 | (temp & 0x0000ffff) << 16;
    temp = (temp & 0xff00ff00) >> 8 | (temp & 0x00ff00ff) << 8;
    temp = (temp & 0xf0f0f0f0) >> 4 | (temp & 0x0f0f0f0f) << 4;
    temp = (temp & 0xcccccccc) >> 2 | (temp & 0x33333333) << 2;
    temp = (temp & 0xaaaaaaaa) >> 1 | (temp & 0x55555555) << 1;

    return temp;
}

2.2 依次移位法

uint32_t reverseBits(uint32_t n) {
    uint32_t temp = 0;
    for (int i = 0; i < 32; i++) {
        temp = (temp << 1) + n % 2;
        n = n >> 1;
    }
    return temp;
}