[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如下

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

view raw howMany1BitsInTheInt_1.cpp hosted with ❤ by GitHub

也可以用內建函式來解

code如下

	class Solution {
	public:
	int hammingWeight(uint32_t n) {
	return bitset<32>(n).count();
	}
	};

view raw howMany1BitsInTheInt_3.cpp hosted with ❤ by GitHub

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

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

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

code 如下

	public class Solution {
	// you need to treat n as an unsigned value
	public int hammingWeight(int n) {
	int ans = 0;
	while(n != 0) {
	++ans;
	n &= (n-1);
	}
	return ans;
	}
	}

view raw hammingWeight_4.java hosted with ❤ by GitHub

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

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

code 如下

	class Solution {
	public:
	int hammingWeight(uint32_t n) {
	n -= (n >> 1) & 0x55555555; // put count of each 2 bits into those 2 bits
	n = (n & 0x33333333) + (n >> 2 & 0x33333333); // put count of each 4 bits into those 4 bits
	n = (n + (n >> 4)) & 0x0F0F0F0F; // put count of each 8 bits into those 8 bits
	return n * 0x01010101 >> 24; // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24)
	}
	};

view raw howMany1BitsInTheInt_2.cpp hosted with ❤ by GitHub