[LeetCode] 191. Number of 1 Bits

轉自LeetCode

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

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

<Solution>
當 32-bit 的 unsigned integer 用 binary 表示的時候，找出有幾個 1

直覺解法，歷遍一次記算即可

code如下

也可以用內建函式來解

code如下


也可以使用 n & (n-1) 的方式來加點速

n & (n-1) 會將最右邊為 1 的 bit 變成 0

所以只要一直將最右邊的 bit 變成 0 來檢查就好，不用 32 個 bit 都去檢查

code 如下

這題有專門的演算法，叫做 Hamming Weight

參考解法在此，下面是目前最快的實作方式

code 如下