20分鐘入門位運(yùn)算

freedom?攝影作品?烏云

這是一道位運(yùn)算題目，對(duì)于非科班出身的人來說，第一次是有點(diǎn)難度的。基礎(chǔ)知識(shí)點(diǎn)的掌握的過程在此處省略了。。。因?yàn)檫@個(gè)過程本身可能比做這題還要難一點(diǎn)。不過，我寫這篇文章的目的就是帶你入門，不帶任何包袱！

題目描述

編寫一個(gè)函數(shù)，輸入是一個(gè)無符號(hào)整數(shù)（以二進(jìn)制串的形式），返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 '1' 的個(gè)數(shù)（也被稱為漢明重量）。

提示：

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

示例 1：

輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進(jìn)制串?00000000000000000000000000001011 中，共有三位為?'1'。

示例 2：

輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進(jìn)制串?00000000000000000000000010000000?中，共有一位為?'1'。

示例 3：

輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進(jìn)制串 11111111111111111111111111111101 中，共有 31 位為?'1'。

提示：

• 輸入必須是長(zhǎng)度為 32 的 二進(jìn)制串 。

進(jìn)階：

• 如果多次調(diào)用這個(gè)函數(shù)，你將如何優(yōu)化你的算法？

題解

因?yàn)?code style="font-size: 14px;overflow-wrap: break-word;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;color: rgb(19, 148, 216);padding: 2px 6px;word-break: normal;">&運(yùn)算只在這種情況下會(huì)得到0，就是類似于這樣11&00、01&10以及01&00，它們都會(huì)得到00。也就是說，&的兩邊對(duì)應(yīng)的二進(jìn)制位必須全是1，形成的新二進(jìn)制數(shù)的對(duì)位二進(jìn)制位才會(huì)是1，否則就是0，對(duì)一個(gè)二進(jìn)制數(shù)據(jù)來說，如果每一位都是0，那結(jié)果就是十進(jìn)制的0了！

有了上面的思路，那就先定義一個(gè)全是0的32位二進(jìn)制數(shù)x，然后在其任意位置上放個(gè)值是1的游標(biāo)，與輸入?yún)?shù)n進(jìn)行與(&)運(yùn)算。根據(jù)題目描述，入?yún)?code style="font-size: 14px;overflow-wrap: break-word;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;color: rgb(19, 148, 216);padding: 2px 6px;word-break: normal;">n的二進(jìn)制位上本身可能至少有一個(gè)1，也可能全是0。再次回到上文，復(fù)習(xí)下&運(yùn)算機(jī)制，那個(gè)有游標(biāo)的二進(jìn)制數(shù)x（只有一個(gè)1），只有在一種情況下與n的與運(yùn)算不會(huì)是0，就是x的游標(biāo)位置所對(duì)應(yīng)的二進(jìn)制數(shù)n的位置上，它們的值恰好都是1。

所以，根據(jù)以上分析，完整代碼就出來了：

/**
?*?@param?{number}?n?-?a?positive?integer
?*?@return?{number}
?*/
var?hammingWeight?=?function(n)?{
????let?ret?=?0;
????for?(let?i?=?0;?i?32;?i++)?{
????????if?((n?&?(1?<0)?{
????????????ret++;
????????}
????}
????return?ret;
};

要注意的是，這里還有一個(gè)知識(shí)點(diǎn)。

1?<0?=?1?//?00001
1?<1?=?2?//?00010
1?<2?=?4?//?00100

<<也是一種位運(yùn)算，表示把二進(jìn)制數(shù)據(jù)向左移動(dòng)，這個(gè)方向也好記，可以把尖括號(hào)形象地理解成箭頭方向。右邊是當(dāng)前值，左邊是移動(dòng)位數(shù)，算起來比較簡(jiǎn)單，你直接把數(shù)值轉(zhuǎn)成二進(jìn)制形式，然后根據(jù)移動(dòng)位數(shù)移動(dòng)到指定位置，再換算成十進(jìn)制就行了。這樣就實(shí)現(xiàn)了上文提到的游標(biāo)效果。

復(fù)雜度分析

時(shí)間復(fù)雜度：O(32)，32二進(jìn)制數(shù)的位數(shù)，遍歷 32 次。

空間復(fù)雜度：O(1)，變量數(shù)是常數(shù)級(jí)的。

鏈接：https://leetcode-cn.com/problems/number-of-1-bits