每日一道 LeetCode (43):翻转二进制数

技术文章 1年前 (2020) 完美者
1,204 0

标签:eve   cat   表示   dig   循环   for   digg   git   指定   

技术图片

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:翻转二进制数

题目来源:https://leetcode-cn.com/problems/reverse-bits/

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

示例 1:

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
     因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。

示例 2:

输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
?    因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示:

  • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
  • 在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的?示例 2?中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。

解题方案一:暴力翻转

常规的线型思维是拿到一个数,直接翻转就好了,比如下面这样:

技术图片

这么干看起来简单,实际上并不是那么好实现。

  • 比如一个数 001 ,我们翻转以后的结果是 1 ,并不会是 001 ,前面的 0 会省去。
  • 这种方案还需要考虑是否会整形溢出, Java 的整数溢出后的二进制数会表示成负数。

这就很坑了,由于是二进制数,解决方案可以使用移位运算,而不是除法运算。

先定义一个结果 res 为 0 ,然后对 110 进行翻转操作,把每一步的结果都存在 res 中,最后得到的 res 就是我们想要的结果。

第一步:
res 左移一位,res = 0
110 的最低位为 0 ,加到 res 上,结果为 0 
110 右移一位,结果为 11

第二步:
res 左移一位,res = 0
11 的最低位为 1 ,加到 res 上,结果为 1
11 右移一位,结果为 1

第三步:
res 左移一位,res = 10
1 的最低位为 1 ,加到 res 上,结果为 11
1 右移一位,结果为 0 ,操作结束

第一个问题来了,如何获取 n 的最低位?

可以使用位运算的 & ,使用 (n & 1) 可以得到 n 的最低位,原理的话我就不说了,看不懂的可以查查位运算 & 是如何计算的。

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        // 获取 n 的最低位加到 res 上
        res = (res << 1) + (n & 1);
        // n 右移一位
        n >>= 1;
    }
    return res;
}

技术图片

这感觉第一步就结束了啊,直接超过 100% 了,不管那么多,接着往下看答案还是。

解题方案二:分治合并

答案上这个方案简直秀到家了,从第一眼看一脸懵逼,到后面打断点一步一步看下来赞叹不已,只留下大写的 「牛逼」 两个字。

先放代码,我觉得大多数人第一眼看到代码的人都是一脸懵。

public int reverseBits_1(int n) {
    n = ((n & 0xffff0000) >>> 16) | ((n & 0x0000ffff) << 16);
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
    return n;
}

技术图片

看到这段代码我第一个感觉是:我是谁?我在哪?我去哪?

人称三大哲学问题。

这个解题思路是这样的:

  • 总共 32 个数,先把这 32 个数从中间拆分成 2 组,每组 16 个数,然后反转这两组进行合并。
  • 然后再把 16 个数拆分成 2 组,每组 8 个数,再反转这两组合并。
  • 接着进行查分,直至拆分成每组 1 个数,然后进行反转合并。

我知道,配合这段解释大多数人还是看不懂,我就用题上的一个数举例子吧,人肉帮你们 debug 一下:

第一次拆分,是通过两个 16 进制的数进行的,分别是 0xffff00000x0000ffff ,这两个数如果转换成 2 进制的结果如下:

0b11111111_11111111_00000000_00000000
0b00000000_00000000_11111111_11111111

实际上第二个数前面的 0 是应该省略掉的,方便理解我手动补 0 。

  • 第一次进行了位运算的 & 运算,相当于直接取到了左边的 16 个数字和右边的 16 个数字。
  • 然后对得到的结果分别进行位移操作,左边的结果进行右移 16 位,右边的结果左移 16 位。
  • 接下来使用 | 将左右两边的结果合并起来。
  • 使用一些有规律的 16 进制的数,分别取到左右 8 位,左右 4 位,左右 2 位 和左右 1 位,进行反转合并。
  • 重复这个过程,最终就得到了整个二进制数的反转后的结果。

注意: >>> 在 Java 的含义是无符号位移,无论是正数还是负数,高位通通补 0 。

这是一个无需循环就能原地翻转二进制数的方案,真心是服了啊,不过感觉在如果是在面试中出这道题,进行 & 操作的时候这些 16 进制数不大好写,直接写 2 进制可能来的更为简单一点。

每日一道 LeetCode (43):翻转二进制数

标签:eve   cat   表示   dig   循环   for   digg   git   指定   

原文地址:https://www.cnblogs.com/babycomeon/p/13649712.html

版权声明:完美者 发表于 2020-09-17 21:35:31。
转载请注明:每日一道 LeetCode (43):翻转二进制数 | 完美导航

暂无评论

暂无评论...