C++实现LeetCode 190：颠倒二进制位的五种解法解析

问题背景与核心逻辑

题目要求输入一个32位的无符号整数，输出其二进制表示颠倒后的结果。例如，输入 00000010100101000001111010011100（十进制43261596），输出应为其逆序 00111001011110000010100101000000（十进制964176192）。

在Java等语言中，若无无符号整数类型，需将输入输出均视为有符号整数处理，但内部二进制补码表示不变，因此逻辑上不受影响。关键在于如何逐位提取并重组。

解法一：基础逐位遍历

最直观的方法是通过循环32次，每次检查当前数字 n 的最低位是否为1。如果是，则在结果 res 左移一位后加1；如果为0，则仅左移。同时将 n 右移一位以准备处理下一位。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            if (n & 1 == 1) {
                res = (res << 1) + 1;
            } else {
                res = res << 1;
            }
            n = n >> 1;
        }
        return res;
    }
};

解法二：简化条件分支

可以去除if-else结构，统一先对结果左移一位。然后判断原数字最低位，若为1则结果加1，最后原数字右移。这减少了嵌套逻辑，使代码更扁平化。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res <<= 1;
            if ((n & 1) == 1) ++res;
            n >>= 1;
        }
        return res;
    }
};

解法三：位或运算替代加法

进一步精简，利用按位或 | 结合提取最低位 (n & 1)。因为 n & 1 的结果只能是0或1，直接通过或运算添加到已左移的 res 中即可，这是最常见的标准写法。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res = (res << 1) | (n & 1);
            n >>= 1;
        }
        return res;
    }
};

解法四：基于索引位移提取

此方法不修改 n 的值，而是通过循环变量 i 控制。每次将 n 右移 i 位后与1相与，提取出原始第i位的值，将其作为新位累加到 res 中（res 每次都左移）。这种方式避免了修改输入变量的副作用。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res = (res << 1) + (n >> i & 1);
        }
        return res;
    }
};

解法五：目标位置直接放置

另一种视角是计算每一位在翻转后应该所在的位置。将第 i 位提取出来后，左移 (31 - i) 位，使其到达最终的倒序位置，然后通过或运算拼接到 res。这种方法逻辑上更贴近“映射”的思想。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res |= ((n >> i) & 1) << (31 - i);
        }
        return res;
    }
};

性能对比与优化建议

上述前四种解法时间复杂度均为 O(1)（固定32次迭代），空间复杂度 O(1)。在实际面试或竞赛中，解法三和解法四是较优且易读的写法。若函数被频繁调用，可考虑使用查表法（Lookup Table）或分治策略（如位段交换）来进一步优化，但这通常用于更高阶的性能场景。

总结

本题重点考察对位运算符 <<, >>, &, | 的熟练运用。掌握逐位处理的核心思想，并结合具体的语言特性（如C++的uint32_t），即可高效解决二进制反转问题。以上就是C++实现LeetCode 190颠倒二进制位的详细内容，更多关于C++位操作算法的资料请关注本站其它相关文章！