Numbers With Exactly K One Bits

Write count_k_bits(N, k) that returns how many whole numbers x with 1 <= x <= N have exactly k ones in their binary form.

N can be as large as 10^18, so counting the numbers one by one would take far too long.

Examples

count_k_bits(10, 2)   # returns 5
count_k_bits(7, 3)    # returns 1
count_k_bits(100, 1)  # returns 7
count_k_bits(5, 0)    # returns 0

The five numbers up to 10 with two 1 bits are 3 (11), 5 (101), 6 (110), 9 (1001) and 10 (1010). Up to 100, the numbers with a single 1 bit are the powers of two 1, 2, 4, 8, 16, 32 and 64. No number from 1 upwards has zero 1 bits.

Constraints

• 0 <= N <= 10**18
• 0 <= k <= 64