劍指Offer__11、二進制中1的個數

題目描述

輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

思路：

先來看一下wangdongli_1993部落格中總結的原碼、反碼、補碼的知識：

數字在計算機中都是二進制來存在，以位元組為機關，一個位元組是8位，這個題目是int類型就是32位

原碼：最高位是符号位，剩下的表示機器數的值

+1：0000 0001

-1：1000 0001

反碼：對于整數，反碼同原碼，對于負數符号位不變，剩下的位取反

+1：0000 0001

-1：1111 1110

補碼：對于整數，補碼同源，對于負數反碼的基礎加1

+1：0000 0001

-1：1111 1111

之後看到了Cytues部落格的分析覺得說的很明白，我在這裡再啰嗦一番：

當n不為0的時候，n的二進制至少有一位是1。

第一種方法比較簡單暴力，因為輸入是整數，int型整數是32位，是以利用for循環，用n和1進行按位與操作(低位依次相與)，然後将n右移，進行32次這樣的操作之後就能得到n中1的個數。

第二種方法相比第一種更有技巧一些，我們先來看正數的情況，由預備知識可知，正數的最高位為0，且原碼、反碼、補碼相同，有一個技巧是先将n減一操作，這個時候n的二進制表示從右向左數的第一個1将變成0，而其右側的所有0将變成1，其左側所有數不變。舉個例子，比如整數12，二進制為1100，在減一之後變成1011，可以看到，12在減1之後，其右側第一個1變成0，且1右邊所有0變成1，1左側所有數不變。我們将1100與1011進行與操作，可以發現變成1000，這個時候12的二進制表示最右側1消失了，這個方法的關鍵就在于此，對整數進行多次減1相與的操作，會将整數二進制中1逐漸消除，最終變為0，是以我們的結論是，一個正數，能進行多少次這樣的與操作，其二進制表示就會有多少個1。

我們再來看一下負數的情況，負數以補碼的形式存儲在計算機中，其最高位為符号位，始終為1，是以對負數進行上述操作的時候會出現一個問題，往右移，符号位不變，符号位1往右移，最終可能會出現全1的情況，導緻死循環。與0xffffffff相與，就可以消除負數的影響。

Solution：

Python
(1)
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        for i in range(32):
            if n&1 ==1:
                count += 1
            n = n>>1
        return count

(2)
# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        if n < 0:
            n = n&0xffffffff
        count = 0
        while n:
            n = n&(n-1)
            count += 1
        return count
           

Reference:

wangdongli_1993： https://blog.csdn.net/wangdongli_1993/article/details/81123424

Cytues：https://blog.csdn.net/qq_41805514/article/details/82709154