輸入一個(gè)整數(shù)大渤，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示祠锣。
思路
- 需要一個(gè)循環(huán)結(jié)構(gòu)酷窥，不斷對輸入數(shù)進(jìn)行
無符號(hào)右移動(dòng)。 - 在循環(huán)體的結(jié)構(gòu)當(dāng)中伴网，使用適當(dāng)?shù)倪^濾器（1 這個(gè)整數(shù)）對輸入數(shù)進(jìn)行
邏輯與（&）操作：結(jié)構(gòu)為 1 的時(shí)候計(jì)數(shù)（count）增加 1蓬推；否則選擇跳過繼續(xù)執(zhí)行循環(huán) 結(jié)構(gòu)。 - 當(dāng)
無符號(hào)右移操作執(zhí)行到終點(diǎn)時(shí)候（輸入數(shù)變成 0）澡腾，終止循環(huán)沸伏，同時(shí)返回最終計(jì)數(shù)的變量。
位運(yùn)算基礎(chǔ)知識(shí)
計(jì)算機(jī)對有符號(hào)數(shù)（包括浮點(diǎn)數(shù)）的表示有三種方法：原碼动分、反碼和補(bǔ)碼（補(bǔ)碼 =反碼 + 1）毅糟。在 二進(jìn)制里，是用 0 和 1 來表示正負(fù)的澜公，最高位為符號(hào)位姆另，最高位為 1 代表負(fù)數(shù)，最高位為 0 代表正數(shù)坟乾。以 8 位的 byte 為例迹辐，最大值為：0111,1111，最小值為 1000,0000甚侣。
以此類推右核，在 Integer 的情況下，-5（toBinaryString）的結(jié)果為：1111,1111, 1111,1111,1111,1111,1111,1011渺绒。
右移
打印 -3 >> 1：-2贺喝。這里看一下具體的計(jì)算過程（正數(shù)左補(bǔ) 0，負(fù)數(shù)左補(bǔ) 1）：
- Integer.toHexString(-3) 得到 3 的 16 進(jìn)制：0xfffffffd（此為-3的補(bǔ)碼,計(jì)算機(jī)中負(fù)數(shù)用補(bǔ)碼表示）宗兼。
- 將其轉(zhuǎn)換成2進(jìn)制為1111,1111,1111,1111,1111,1111,1111,1101躏鱼。
- 右移一位得到：1111,1111,1111,1111,1111,1111,1111,1110，顯而易見此為-2補(bǔ)碼殷绍。
左移
打印 -3<<1：-6染苛。左移相對來說比較簡單（正負(fù)數(shù)皆右補(bǔ) 0）：
- -3 的二進(jìn)制為：1111,1111,1111,1111,1111,1111,1111,1101。
- 左移一位為：1111,1111,1111,1111,1111,1111,1111,1010，其為-6的補(bǔ)碼茶行。
無符號(hào)右移
打印 -3<<1：2147483646躯概。遵循的原則：正數(shù)左補(bǔ) 0，負(fù)數(shù)左補(bǔ) 1：
- -3 的二進(jìn)制為：1111,1111,1111,1111,1111,1111,1111,1101畔师。
- 無符號(hào)右移娶靡，高位補(bǔ) 0 得到：0111,1111,1111,1111,1111,1111,1111,1110，其為 2147483646 的補(bǔ)碼/原碼（正數(shù)的原碼和補(bǔ)碼相同）看锉。
消失的無符號(hào)左移
為什么沒有無符號(hào)左移姿锭？
因?yàn)樽笠剖窃诤竺嫜a(bǔ) 0，而右移是在前面邊補(bǔ) 1 或 0伯铣，有無符號(hào)是取決于數(shù)的第一位是 0 還是 1呻此，所以右移是會(huì)產(chǎn)生到底補(bǔ)1還是0的問題。而左移始終是在右邊補(bǔ)腔寡，不會(huì)產(chǎn)生符號(hào)問題焚鲜，所以沒有必要無符號(hào)左移 <<<。因此放前，無符號(hào)左移 <<< 和左移 << 是一樣的概念恃泪。
常規(guī)代碼實(shí)現(xiàn)
根據(jù)上述的思路和基本概念，這里用 JS 來對這道題進(jìn)行解答：
function NumberOf1(n) {
// write code here
let count = 0
for(;n != 0; n >>>= 1) {
if(n & 1) {
count++
}
}
return count
}
Python 中遇到的問題和解決方法
Python 中沒有無符號(hào)右移
在 JS 中犀斋，可以使用 a >>> b 來實(shí)現(xiàn)無符號(hào)位移贝乎，Python 中沒有這個(gè)運(yùn)算符，只能自己實(shí)現(xiàn)了
無符號(hào)右移 >>>：就是將有符號(hào) int a 和 b 轉(zhuǎn)為無符號(hào) uint 后叽粹，再進(jìn)行普通右移 >> 運(yùn)算览效。比如 -1 的有符號(hào) int 就是 -1，無符號(hào) int 就是 4294967295虫几。
因?yàn)?Python 中沒有 無符號(hào)右移锤灿，因而不能對最高位補(bǔ) 0，對于 負(fù)數(shù) 還是繼續(xù)用 1 補(bǔ)進(jìn)辆脸，這樣就沒有辦法正確的統(tǒng)計(jì) 1 的個(gè)數(shù)但校。
解決方法
解決前：
- Python：打印 -3 >> 1，輸出 -2（不符合要求）
- JavaScript：打印 -3 >>> 1啡氢，輸出 2147483646（符合要求）
解決后：
- Python：打印 (-3 & 0xffffffff) >> 1状囱，輸出 2147483646（符合要求）
原理：負(fù)數(shù)與邊界數(shù)按位與（&） 操作后 得到的是對應(yīng)二進(jìn)制數(shù)的真值：
-3 & 0xffffffff —> 4294967293
此時(shí)再在 Python 當(dāng)中對其進(jìn)行正常右移 >> 操作則是對一正數(shù)進(jìn)行右移，前面補(bǔ) 0倘是，符合要求亭枷；如果沒進(jìn)行這一步操作，右移依然是針對負(fù)數(shù)來進(jìn)行操作的搀崭，前面補(bǔ) 1叨粘，不符合要求。
代碼實(shí)現(xiàn)
有了以上的原理鋪墊，在 Python 的代碼當(dāng)中升敲，在第一次右移操作之前答倡，先對被操作數(shù)進(jìn)行和邊界數(shù) 0xffffffff 的 與 & 運(yùn)算，可得到正確的執(zhí)行結(jié)果：
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
n = n & 0xffffffff
while n != 0:
if (n & 1) == 1:
count += 1
n = n >> 1
return count
其他的解決辦法
class Solution:
def NumberOf1(self, n):
# write code here
M1 = 0x55555555
M2 = 0x33333333
M4 = 0x0f0f0f0f
M8 = 0x00ff00ff
M16 = 0x0000ffff
n = (n & M1) + ((n >> 1) & M1)
n = (n & M2) + ((n >> 2) & M2)
n = (n & M4) + ((n >> 4) & M4)
n = (n & M8) + ((n >> 8) & M8)
n = (n & M16) + ((n >> 16) & M16)
return n
