Solution1

• odd number ends with 1

• even number ends with 0

if n is odd: bits of n is one more then bits of n-1 e.g. 3-011 2-010 elif n is even: bits of n is same as bits of n // 2, just emagine left shift out that 0, 1's count remain same.