未分類

Counting Bits

BitManipulation, DynamicProgramming, Go, LeetCode

Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

For example:

For num = 5 you should return [0,1,1,2,1,2].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
提示 解題應用
BitManipulation AND

Default:

1
2
3
func countBits(num int) []int {
}

解答思路:

要計算某數的二進制有多少個1出現，有一個小技巧是不斷的將”該數”與”該數-1”做AND直到0為止共做了多少次就會是有多少個1，而這次要求的是0~某數的二進制分別有多少個1出現，當然就是利用一迴圈取出0~某數來分別做計算，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
var n int
var count int
result := make([]int, num+1)
for i := 0; i <= num; i++ {
	n = i
	count = 0
	for n != 0 {
		n = n & (n - 1)
		count++
	}
	result[i] = count
}
return result

而這樣的時間複雜度會是O(n*[Number of 1’s])，不過題目希望我們能在O(n)之內，既然有一路記下先前數字的二進制有多少個1，那麼當然就要好好重覆使用，每次求某數i的二進制有多少個1時，陣列中取出index為i&(i-1)的值再+1就會是我們要的結果，如此一來便能在規定的時間內找出0~某數的所有個數。

程式碼解說:

一開始先初始化一個n+1的陣列用來儲存0~n的結果，接著就是利用迴圈分別取出1~n(0的個數為0不需計算)，每次求某數i的二進制有多少個1時，陣列中取出index為i&(i-1)的值再+1就會是我們要的結果，最後個數全數找出後便能向上回傳整個陣列

1
2
3
4
5
result := make([]int, num+1)
for i := 1; i <= num; i++ {
	result[i] = result[i&(i-1)] + 1
}
return result

完整程式碼:

1
2
3
4
5
6
7
func countBits(num int) []int {
	result := make([]int, num+1)
	for i := 1; i <= num; i++ {
		result[i] = result[i&(i-1)] + 1
	}
	return result
}

總結:

要求出0~n的二進制分別有多少個1出現，則要先計算某數的二進制有多少個1出現，有一個小技巧是不斷的將”該數”與”該數-1”做AND直到0為止共做了多少次就會是有多少個1，至於0~n當然就是利用一迴圈取出來分別做計算，而這樣的時間複雜度會是O(n*[Number of 1’s])，如果要在O(n)之內，既然有一路記下先前數字的二進制有多少個1，那麼當然就要好好重覆使用，每次求某數i的二進制有多少個1時，陣列中取出index為i&(i-1)的值再+1就會是我們要的結果，如此一來便能在規定的時間內找出0~某數的所有個數。

分享到