class Solution1(object):
"""
traditional ways , in each step, we count 1 of number use bit operation
"""
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
result = []
for i in range(num+1):
result.append(self.count_bit_1(i))
return result
def count_bit_1(self, n):
count = 0
while(n):
if n & 1 == 1:
count += 1
n >>= 1
return count
class Solution2(object):
"""
a binary number , to calc how many 1 it contains, we can separate it into last bit and front bits
in this case, we can use dynamic programming to solve it
"""
def countBits(self, nums):
dp = [0, 1]
if nums <= 1: return dp[:nums+1]
else:
for i in range(2, nums+1):
dp.append(dp[i//2] + dp[i % 2])
return dp
class Solution3(object):
"""
two points
4, 5 ,6 => 100, 101, 110
the first is bit is 1, and the remain is 00, 01, 10, that is 0, 1, 2
so if we meet a number is power of two then the next number's bit count equals to 1+ bit(0), 1+ bit(1) .. until meet next number which is power of two
"""
def countBits(self, nums):
dp = [0, 1]
if nums <= 1 : return dp[:nums+1]
power2 = 2
index = 0
for n in range(2,nums+1):
if n == power2:
dp.append(1)
power2 *= 2
index = 1
else:
dp.append(1 + dp[index])
index += 1
return dp
