0191. Number of 1 Bits (Easy)

Question

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1

1
2
3

Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2

1
2
3

Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3

1
2
3

Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

分析/解題

給定一個unsigned integer(正整數或0)，試回傳其位元為1的個數。

這題其實比上一題還要再簡單一點XD
假設我們將數字稱為n，要計算其位元為1的個數的方式一般有兩個：

1. 看當前的位數是否為1 來決定是否遞增記錄累積的cnt(count)，
   再將n向右位移1位，直到做完全部32個位元。

2. 將n每次和n-1相AND，可以去掉最低次的位元。
   舉例來說：
   n=11100 => 11100 & 11011 = 11000
   (減1時最低位的1會被借位，導致該位變成0，
   其後的位數變成1，從而在相AND時全都會變成0)
   n=10011 => 10011 & 10010 = 10010
   (最低位的1一開始就在最右邊，顯然減完最右邊變成0，
   同樣會符合去掉最低次的位元的特性)

Java

Python的部份，也可以轉成二進位以後再用count去數'1’。
(不需要考慮前面的0b因為沒差XD)

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(1)/O(1)，因最多32次迴圈就結束了XD)

相似及延伸

Special Thanks suggestions/corrections from viewers: 這題其實一樣可以有更精妙的解法，但同樣不建議在面試時使用。
(除非你要面試的就是非常在乎效能加速的公司)請參見JDK所使用的Integer.bitCount() 函式原始碼講解：
https://juejin.im/post/5c3969b76fb9a049a5712060

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~