检查一个数字是否可以表示为 x 次方 2 的总和

Question

有没有一点技巧来检查一个数字是否可以表示为 2 的 x 次方之和？

示例：对于 x=3 n=21，数字为 16、4 和 1。 如果 n=30，则应该是假的，因为没有 3 的 2 次方来表示 30。

Answer 1

对于数字 n ...

• 。最小 x 是 n 中1位的位数。这个数字称为popcount(n).
  示例：二进制数0b1011至少需要popcount(0b1011)=2的3次方才能求和(0b1000+0b0010+0b0001)。
• 。最大值 x 为 n。因为1是 2 的幂，所以你可以加1n 次得到 n。

现在来了一个难题。如果 x 介于 popcount(n) 和 n？
之间，那么所有这些 x 都是可能的。要构建 x 次方 2 的总和...

• 从最小和(n 的二进制表示)开始
如果添加数
• 少于 x 个，请将任何大于 1 的加法拆分为两个加法，将加法数增加一个。这可以完成，直到你到达 x=n。

示例：11=0b1011可以表示为 x=7 的 2 次方之和吗？

是的，因为popcount(n)=3 <= x=7 <= n=11。

要构建 x=7 的 2 次方的总和，我们使用
11 =0b1011=0b1000+0b10+0b1| 只有 3 个加法，所以拆分一个
= (0b100+0b100)+0b10+0b1| 只有 4 个加法，所以拆分另一个
= ((0b10+0b10)+0b100)+0b10+0b1| 只有 5 个加法， 所以拆分另一个
= (((0b1+0b1)+0b10)+0b100)+0b10+0b1|只有 6 个加法，所以再拆分一个
= ((0b1+0b1)+(0b1+0b1))+0b100)+0b10+0b1|7 个补充，已完成

实现

要实现检查"n可以表示为x次方2的总和吗？

isSumOfXPowersOfTwo(n, x) {
return x<=n && x>=popcount(n).
}

有关popcount的高效位摆动实现，请参阅此问题。一些处理器甚至有这方面的指令。