338.counting-bits.go

/*
 * @lc app=leetcode id=338 lang=golang
 *
 * [338] Counting Bits
 *
 * https://leetcode.com/problems/counting-bits/description/
 *
 * algorithms
 * Medium (64.44%)
 * Total Accepted:    162.6K
 * Total Submissions: 252.3K
 * Testcase Example:  '2'
 *
 * 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.
 * 
 * Example 1:
 * 
 * 
 * Input: 2
 * Output: [0,1,1]
 * 
 * Example 2:
 * 
 * 
 * Input: 5
 * Output: [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.
 * 
 */

 // 循环遍历，统计每个数中1的个数，统计方式采用191题的汉明权重
func countBits(num int) []int {
	rnt := []int{}
	for i:=int(0);i<=num; i++{		
		rnt = append(rnt,hmweight(i))
	}
	return rnt
}

func hmweight(num int)int{
	var cnt int 
	for ;num != 0; num &=(num-1){
		cnt++
	}
	return cnt
}