每日一道 LeetCode (43)：翻轉(zhuǎn)二進制數(shù)

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

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

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

題目：翻轉(zhuǎn)二進制數(shù)

題目來源：https://leetcode-cn.com/problems/reverse-bits/

顛倒給定的 32 位無符號整數(shù)的二進制位。

示例 1：

輸入:?00000010100101000001111010011100
輸出:?00111001011110000010100101000000
解釋:?輸入的二進制串?00000010100101000001111010011100?表示無符號整數(shù)?43261596，
?????因此返回 964176192，其二進制表示形式為?00111001011110000010100101000000。

示例 2：

輸入：11111111111111111111111111111101
輸出：10111111111111111111111111111111
解釋：輸入的二進制串 11111111111111111111111111111101 表示無符號整數(shù) 4294967293，
?????因此返回 3221225471 其二進制表示形式為 10111111111111111111111111111111 。

提示：

• 請注意，在某些語言（如 Java）中，沒有無符號整數(shù)類型。在這種情況下，輸入和輸出都將被指定為有符號整數(shù)類型，并且不應影響您的實現(xiàn)，因為無論整數(shù)是有符號的還是無符號的，其內(nèi)部的二進制表示形式都是相同的。
• 在 Java 中，編譯器使用二進制補碼記法來表示有符號整數(shù)。因此，在上面的?示例 2 中，輸入表示有符號整數(shù) -3，輸出表示有符號整數(shù) -1073741825。

解題方案一：暴力翻轉(zhuǎn)

常規(guī)的線型思維是拿到一個數(shù)，直接翻轉(zhuǎn)就好了，比如下面這樣：

這么干看起來簡單，實際上并不是那么好實現(xiàn)。

• 比如一個數(shù) 001 ，我們翻轉(zhuǎn)以后的結(jié)果是 1 ，并不會是 001 ，前面的 0 會省去。
• 這種方案還需要考慮是否會整形溢出， Java 的整數(shù)溢出后的二進制數(shù)會表示成負數(shù)。

這就很坑了，由于是二進制數(shù)，解決方案可以使用移位運算，而不是除法運算。

先定義一個結(jié)果 res 為 0 ，然后對 110 進行翻轉(zhuǎn)操作，把每一步的結(jié)果都存在 res 中，最后得到的 res 就是我們想要的結(jié)果。

第一步：
res?左移一位，res?=?0
110?的最低位為?0?，加到?res?上，結(jié)果為?0?
110?右移一位，結(jié)果為?11

第二步：
res?左移一位，res?=?0
11?的最低位為?1?，加到?res?上，結(jié)果為?1
11?右移一位，結(jié)果為?1

第三步：
res?左移一位，res?=?10
1?的最低位為?1?，加到?res?上，結(jié)果為?11
1?右移一位，結(jié)果為?0?，操作結(jié)束

第一個問題來了，如何獲取 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;
}

這感覺第一步就結(jié)束了啊，直接超過 100% 了，不管那么多，接著往下看答案還是。

解題方案二：分治合并

答案上這個方案簡直秀到家了，從第一眼看一臉懵逼，到后面打斷點一步一步看下來贊嘆不已，只留下大寫的 「牛逼」 兩個字。

先放代碼，我覺得大多數(shù)人第一眼看到代碼的人都是一臉懵。

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 個數(shù)，先把這 32 個數(shù)從中間拆分成 2 組，每組 16 個數(shù)，然后反轉(zhuǎn)這兩組進行合并。
• 然后再把 16 個數(shù)拆分成 2 組，每組 8 個數(shù)，再反轉(zhuǎn)這兩組合并。
• 接著進行查分，直至拆分成每組 1 個數(shù)，然后進行反轉(zhuǎn)合并。

我知道，配合這段解釋大多數(shù)人還是看不懂，我就用題上的一個數(shù)舉例子吧，人肉幫你們 debug 一下：

第一次拆分，是通過兩個 16 進制的數(shù)進行的，分別是 0xffff0000 和 0x0000ffff ，這兩個數(shù)如果轉(zhuǎn)換成 2 進制的結(jié)果如下：

0b11111111_11111111_00000000_00000000
0b00000000_00000000_11111111_11111111

實際上第二個數(shù)前面的 0 是應該省略掉的，方便理解我手動補 0 。

• 第一次進行了位運算的 & 運算，相當于直接取到了左邊的 16 個數(shù)字和右邊的 16 個數(shù)字。
• 然后對得到的結(jié)果分別進行位移操作，左邊的結(jié)果進行右移 16 位，右邊的結(jié)果左移 16 位。
• 接下來使用 | 將左右兩邊的結(jié)果合并起來。
• 使用一些有規(guī)律的 16 進制的數(shù)，分別取到左右 8 位，左右 4 位，左右 2 位 和左右 1 位，進行反轉(zhuǎn)合并。
• 重復這個過程，最終就得到了整個二進制數(shù)的反轉(zhuǎn)后的結(jié)果。

?

注意：>>> 在 Java 的含義是無符號位移，無論是正數(shù)還是負數(shù)，高位通通補 0 。

?

這是一個無需循環(huán)就能原地翻轉(zhuǎn)二進制數(shù)的方案，真心是服了啊，不過感覺在如果是在面試中出這道題，進行 & 操作的時候這些 16 進制數(shù)不大好寫，直接寫 2 進制可能來的更為簡單一點。