劍指offer(十一)-二進位制中1的個數(Java版)

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

示例1

輸入：10

返回值：2

首先我們學習一下幾個常用運算子

& 與運算子， 當&兩側是int時，要先把運算子兩側的數轉化為二進位制數再進行運算，相同位進行比較，是1才為1，否則為0

例如 10 & 2，10轉換為2進製為 1010，而2轉換為二進位制為0010 所以10&2=1010&0010=0010=2

>>：右移運算子，num>>1，相當於num除於2的一次方，即num/2

例如 10>>1 ，10的二進位制數為1010，右移一位，空出來的位置用0填充，則1010右移兩位為0101 即為5

8>>2，相當於8除於2的平方，即8/4 = 2， 8的二進位制數為1000，右移兩位，空出來的位置用0填充，則1000右移兩位為0010 即為2

第一種解法，我們可以每次判斷num轉換為二進位制數的最後一位數是否為1，然後依次右移即可，程式碼如下

public int firstNumberOf1（int n） { int sum = 0； for （int i= 0； i < 32；i++）{ int result = n & 1； sum += result； n = n >> 1； } return sum； }

第二種解法，上面我們理解了&運算子的含義，利用n & n-1

用10來作為例子，10 & 9 ，10的二進位制為1010，9的二進位制為1001，10&9 = 1010&1001=1000 = 8，這個時候剛好把最右邊的1消去，只要&不為零，依次判斷即可

public int secondNumberOf1（int n） { int sum = 0； while （n ！= 0）{ sum++； n &= n-1； } return sum； }

第三種解法，熟悉Java Integer物件方法的同學，可以知道Integer。bitCount（n）方法，此方法就是計算 統計二進位制中1的個數，程式碼如下

public int thirdNumberOf1（int n） { return Integer。bitCount（n）； }