目标
给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x …… 等位置处 set bit(指在某数的二进制表示中值为 1 的二进制位) 的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。
| x | num | Binary Representation | Price |
|---|---|---|---|
| 1 | 13 | 000001101 | 3 |
| 2 | 13 | 000001101 | 1 |
| 2 | 233 | 011101001 | 3 |
| 3 | 13 | 000001101 | 1 |
| 3 | 362 | 101101010 | 2 |
num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。
请你返回 最大 的廉价数字。
示例 1：
输入：k = 9, x = 1
输出：6
解释：由下表所示，6 是最大的廉价数字。| x | num | Binary Representation | Price | Accumulated Price |
|---|---|---|---|---|
| 1 | 1 | 001 | 1 | 1 |
| 1 | 2 | 010 | 1 | 2 |
| 1 | 3 | 011 | 2 | 4 |
| 1 | 4 | 100 | 1 | 5 |
| 1 | 5 | 101 | 2 | 7 |
| 1 | 6 | 110 | 2 | 9 |
| 1 | 7 | 111 | 3 | 12 |
示例 2：
输入：k = 7, x = 2
输出：9
解释：由下表所示，9 是最大的廉价数字。| x | num | Binary Representation | Price | Accumulated Price |
|---|---|---|---|---|
| 2 | 1 | 0001 | 0 | 0 |
| 2 | 2 | 0010 | 1 | 1 |
| 2 | 3 | 0011 | 1 | 2 |
| 2 | 4 | 0100 | 0 | 2 |
| 2 | 5 | 0101 | 0 | 2 |
| 2 | 6 | 0110 | 1 | 3 |
| 2 | 7 | 0111 | 1 | 4 |
| 2 | 8 | 1000 | 1 | 5 |
| 2 | 9 | 1001 | 1 | 6 |
| 2 | 10 | 1010 | 2 | 8 |
说明：
1 <= k <= 10^151 <= x <= 8
提示：
- Binary search the answer.
- In each step of the binary search you should calculate the number of the set bits in the ith position. Then calculate the sum of them.
思路
给定步长x，数字的价值定义为从最低有效位开始，以步长x遍历数字的二进制表示，并记录bit为1的个数。数字n的累加价值定义为 1 ~ n 的价值之和。给定数字k，求累加价值不超过k的最大数字。
先尝试模拟暴力求解。注意到返回值是 long 类型，说明n的规模超过了10^9，即便是 O(n) 的解法也会超时，并且每个数字都要循环bit位计数，肯定超时。我们需要要找一种 O(logn) 的解法。
提示说使用二分查找，问题的关键是如何直接计算出给定数字的累加价值。
// todo
代码