Day32 - 190.reverse bits

Day32 - 190.颠倒二进制位

LeetCode 190.颠倒二进制位

题目链接：

https://leetcode.cn/problems/reverse-bits/

1. 题目描述

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

举个例子：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

2. 知识回顾

1. 左移运算符 <<，可以将一个对象的二进制向左移n位，左边n位丢弃，右边n位补0。比如，a = 1101。

a << 2 = 0100

1. 右移运算符 >>，可以将一个对象的二进制向右移n位，右边n位丢弃，左边n位补0。比如，a = 1101。

a >> 2 = 0011

3. 思路解析

3.1. 方法一 按位颠倒

我们先将题目简化一下，对于一个8位的二进制10110111，如何进行颠倒成11101101呢？

先定义一个8位无符号的res = 0，我们将二进制的第i位，放到res的第7 - i位（位数从0开始）就可以完成整个过程的翻转。过程如下图：

针对上面的结论稍加修改就可以应用到32位无符号整数上面。

先定义一个存放结果的32位无符号变量 res = 0，循环遍历原串二进制的第i位，将其放到res的第31-i位，遍历完原串即得到最终翻转后的结果res。

3.2. C++代码

class Solution
{
public:
    uint32_t reverseBits(uint32_t n)
    {
        uint32_t res = 0;
        for(int i = 0; i < 32; i++)
        {
            // 取出第 i 位
            int bit = (n >> i) & 1;
            // 或运算只会改变第 i 位的数
            res = res | (bit << (31 - i));
        }
        return res;
    }
};

因为 res 原来都是 0。所以可以用或运算来进行元素的放置。

• 本质上并不是交换

• 而是利用空间，直接对数组进行颠倒放置。

3.3. 方法二 分治

下面介绍另一种分治方法，对一些刚刷题的同学来说可能比较难理解。

• 把32位分成左右两部分16位，左右两部分交换。可以通过n = (n >> 16) | (n << 16)来做到。

• 把16位分成左右两部分8位，左右两部分交换。可以通过n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)来做到。16进制0x00ff00ff和32位二进制0000 0000 1111 1111 0000 0000 1111 1111是等价的，0xff00ff00和1111 1111 0000 0000 1111 1111 0000 0000是等价的。

• 把8位分成左右两部分4位，左右交换。可以通过n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)来做到。16进制0xf0f0f0f0和二进制1111 0000 1111 0000 1111 0000 1111 0000是等价的，0x0f0f0f0f和0000 1111 0000 1111 0000 1111 0000 1111是等价的。

• 把4位分成左右两部分2位，左右交换。可以通过n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)来做到。16进制0xcccccccc和二进制1100 1100 1100 1100 1100 1100 1100 1100等价，0x33333333和二进制0011 0011 0011 0011 0011 0011 0011 0011等价。

• 把2位分成左右两部分1位，左右交换。可以通过 n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)来实现。其中16进制0xaaaaaaaa和二进制1010 1010 1010 1010 1010 1010 1010 1010等价，0x55555555和0101 0101 0101 0101 0101 0101 0101 0101等价。

3.4. C++代码

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        //左右16位交换
        n = (n >> 16) | (n << 16);
        //左右8位交换
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        //左右4位交换
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        //左右2位交换
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        //左右1位交换
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};

冗杂的16进制表示实在令人厌恶。可以进行如下修改：

• 宏定义 define / 掩码定义 const 出 相应的16进制表示，减少行中冗余项。

• 封装为函数。

4. 复杂度分析

时间复杂度： 后两种方法都是 O(1)，最多处理32位，分治是log32位，都是常量时间。

空间复杂度： 后两种方法都是 O(1)，只使用有限个整型变量。

5. Redo. 02/15

按位移动

• 移位运算符

• & 1 运算，判断某一位是 0 还是 1

• | 运算，res 初始值为 0，则 res 由 | 之后的值来决定。

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