iT邦幫忙

2021 iThome 鐵人賽

DAY 8
1
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 8

Leetcode 挑戰 Day 08 [191. Number of 1 Bits]

191. Number of 1 Bits


今天這一題是有關於二進制的概念和其與十進位之間的轉換,如何將一個十進位整數轉換成二進位的型態,可以說是非常基本但重要的。

題目


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

Example 1:

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

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

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

這題的題目是希望我們算出題目所給的整數,以二進位表示的話,會出現多少個一。

Decimal to Binary


如何從十進位轉換成二進位?我們在現實生活上,實際可以透過短除法不斷除二,如果有餘數1的那欄位就填1,沒有就填寫0,直到最後出現被除數變為零。
而在程式上我們可以透過以下的程式碼來呈現上述的想法,通過迴圈,取餘數,除以二(取整數),不斷重複做,如果取餘數不為零,就在變數ans加一,如此一來我們便可以知道一個十進位的數字中有多少個一了。

以下為python3的程式碼

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n>0:
            if n % 2 != 0:  # 也可以寫成 ans += n % 2
                ans += 1 
            n = n // 2   # n //= 2
        return ans

Bit shiftting


除了上述直觀的想法,我們也可以用更接近電腦語言的方式,那便是通過對題目給我們的數字不斷往右shift,與1做&邏輯運算,這樣一來我們可以得知,只有出現1的地方與1做&運算才會是1,這麼一來,我們也能算出來有多少個1。

以下是python3的程式碼

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n > 0:
            if (1 & n):  # AND邏輯運算
                ans += 1
            n >>= 1  # 往右Shift
        return ans

以下是C++的程式碼

class Solution {
public:
    int hammingWeight(uint32_t n) 
{
	int ans = 0;
	while(n > 0)
	{
		if(n & 1UL)
			ans++;
		n >>= 1;
	}
	return count;
}
};

上一篇
Leetcode 挑戰 Day 07 [118. Pascal's Triangle]
下一篇
Leetcode 挑戰 Day 09 [344. Reverse String]
系列文
試煉之地 Leetcode 的挑戰19
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言