代码训练LeetCode(13)颠倒二进制位

代码训练(13)LeetCode之颠倒二进制位

Author: Once Day Date: 2024年4月9日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 190. 颠倒二进制位 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

• • • 代码训练(13)LeetCode之颠倒二进制位

1. 原题

原题目要求实现一个函数，输入是一个32位无符号整数，输出也是一个32位无符号整数，它是输入数字二进制表示的颠倒。

例如，若输入的整数的二进制表示是0000010100101000001111010011100。

则输出应为00111001011110000010100101000000，即将输入的二进制位从右向左排列后得到的结果。

2. 分析

颠倒一个整数的二进制位，可以通过多次将原数字右移并取出最低位，然后将这个位左移相应的位置添加到新数字中去的方法来实现。我们可以用一个循环，每次迭代处理一个位。

分析步骤：

1. 初始化一个变量，用于存储最终颠倒后的结果。
2. 进行32次循环，因为我们处理的是一个32位的整数。
3. 在每次循环中，将结果变量向左移动一位，为即将添加的最低位腾出空间。
4. 使用按位与操作取得原始整数的最低位。
5. 将这个最低位添加到结果变量中。
6. 将原始整数右移一位，丢弃已经处理过的最低位。
7. 循环结束后，结果变量中存储的就是颠倒后的整数。

假设输入整数为2，二进制表示为00000000000000000000000000000010。

1. 初始化结果变量为0：00000000000000000000000000000000。
2. 第一次循环：
   • 结果左移：00000000000000000000000000000000。
   • 输入右移：00000000000000000000000000000001，取得最低位为2（10）。
   • 结果变量现在为：00000000000000000000000000000010。
3. 继续这个过程，直到处理完32次。

性能优化关键点：

1. 执行速度优化：由于只需要进行固定次数的位操作，所以算法的执行速度已经很快。确保没有不必要的操作或函数调用。
2. 内存使用优化：只需要存储输入整数和结果整数，所以内存使用已经很少。

3. 代码实现

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

在上面的代码中，reverseBits函数是进行颠倒操作的核心。使用了一个for循环来迭代32次，每次将结果变量result左移一位，并将原始整数n的最低位使用按位与（&）操作取出，通过按位或（|）操作添加到result中。原始整数通过右移操作丢弃最低位。函数最终返回颠倒后的结果。

运行结果如下所示(仅供参考):

4. 总结

这个问题考察了对位操作的掌握，包括左移、右移、按位与和按位或。这些操作是底层编程、嵌入式系统开发和性能优化中的重要工具。