2024-05-15：用 go 语言，考虑一个整数 k 和一个整数 x。

对于一个数字 num，

在其二进制表示中，

从最低有效位开始，

我们计算在 x，2x，3x 等位置处设定位的数量来确定其价值。

举例说明，

若对于 x=1，num=13，则二进制表示为 000001101，对应的价值为 3。

又如，当 x=2，num=13，二进制表示依然为 000001101，但对应的价值是 1。

另一个例子是当 x=3，num=362，二进制表示为 101101010，价值为 2。

一个数字的累加价值是从 1 到该数字的所有数字的总价值。

如果一个数字的累加价值小于或等于 k，则我们认为它是廉价的。

现在，我们需要找到最大的廉价数字。

输入：k = 9, x = 1。

输出：6。

答案 2024-05-15：

chatgpt

题目来自 leetcode3007。

大体步骤如下：

1.将输入的整数 k 转换为 int 类型，并初始化变量 num 和 pre1 为 0。

2.使用 bits.Len() 函数来计算 (k+1) << x 的二进制表示的位数，将结果减去 1，得到最高有效位的索引 i。

3.从 i 开始遍历到 0，每次循环减少 i 的值。

4.在每次循环中，计算 cnt 的值，cnt = pre1 << i + (i / x) << i >> 1。

5.如果 cnt 大于 k，则跳过当前循环。

6.否则，将 k 减去 cnt，并且通过位运算将 num 的第 i 位设置为 1。

7.如果 (i+1) 是 x 的倍数，则将 pre1 的值加 1。

8.循环结束后，返回 num - 1。

总的时间复杂度：O(log(k+1) * log((k+1)<<x))，其中 log(k+1) 是计算 (k+1) 的二进制表示的位数，log((k+1)<<x) 是计算 (k+1)<<x 的二进制表示的位数。

总的额外空间复杂度：O(1)，只使用了常数级别的额外空间。

Go 完整代码如下：

package main
import (  "fmt"  "math/bits")
func findMaximumNumber(K int64, x int) int64 {  k := int(K)  num, pre1 := 0, 0  for i := bits.Len(uint((k+1)<<x)) - 1; i >= 0; i-- {    cnt := pre1<<i + i/x<<i>>1    if cnt > k {      continue    }    k -= cnt    num |= 1 << i    if (i+1)%x == 0 {      pre1++    }  }  return int64(num - 1)}
func main() {  k := int64(9)  x := 1  result := findMaximumNumber(k, x)  fmt.Println(result)}