LeetCode Q338 Counting Bits

Q338 Counting Bits



 num:    1        binary:    00000001
 num:    2        binary:    00000010
 num:    3        binary:    00000011
 num:    4        binary:    00000100
 num:    5        binary:    00000101
 num:    6        binary:    00000110
 num:    7        binary:    00000111
 num:    8        binary:    00001000
 num:    9        binary:    00001001
 num:    10        binary:    00001010
 num:    11        binary:    00001011
 num:    12        binary:    00001100
 num:    13        binary:    00001101
 num:    14        binary:    00001110
 num:    15        binary:    00001111

 Define f(n) number of 1s in binary presentation for n
 for number  2^i<= n < 2^(i-1)
 f(n) = 1 + f(n % 2^i)

Example Solution

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q338CountingBits.playground/Contents.swift