题目描述

给定一个整数$n$，求出 $1$ 到 $n$ 中有多少个数满足其二进制表示中恰好有 $k$ 个 1。

输入格式

• 输入一行：两个整数 $n$ 和 $k$。

输出格式

• 输出一个整数表示答案。

7 2

3

数据范围

• 对于 $30 \%$ 的数据, $1 \leq n \leq 10^{4}, 1 \leq k \leq 10$ 。
• 对于 $60 \%$ 的数据, $1 \leq n \leq 10^{9}, 1 \leq k \leq 30$ 。
• 对于 $100 \%$ 的数据, $1 \leq n \leq 10^{18}, 1 \leq k \leq 60$ 。