检查一个数字是否可以表示为两个的 x 次幂之和？
check wheather a number can be expressed as sum of x powers of two?
是否有任何小技巧来检查一个数字是否可以表示为 2 的 x 次幂之和？
示例：x=3 n=21 数字是 16,4,1 如果 n=30 它应该是假的，因为没有 3 的 2 次方来表示 30
对于数字 n …
- …最小的x是n中
1位的个数。这个数字叫做 popcount(n)。
例子：二进制数0b1011至少需要popcount(0b1011)=3次方求和(0b1000+0b0010+0b0001)。
- …最大x为n。因为
1 是 2 的幂，所以您可以将 1 n 次相加得到 n.
难题来了。如果 x 在 popcount(n) 和 n 之间怎么办？
事实证明，所有这些 x 都是可能的。计算两个的 x 次方的总和……
- 从最短和（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 次幂之和吗？« 使用
isSumOfXPowersOfTwo(n, x) {
return x<=n && x>=popcount(n).
}
有关 popcount 的有效位旋转实现，请参阅 this question。有些处理器甚至有一个指令。
是否有任何小技巧来检查一个数字是否可以表示为 2 的 x 次幂之和？ 示例：x=3 n=21 数字是 16,4,1 如果 n=30 它应该是假的，因为没有 3 的 2 次方来表示 30
对于数字 n …
- …最小的x是n中
1位的个数。这个数字叫做 popcount(n)。
例子：二进制数0b1011至少需要popcount(0b1011)=3次方求和(0b1000+0b0010+0b0001)。 - …最大x为n。因为
1是 2 的幂，所以您可以将1n 次相加得到 n.
难题来了。如果 x 在 popcount(n) 和 n 之间怎么办？
事实证明，所有这些 x 都是可能的。计算两个的 x 次方的总和……
- 从最短和（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 次幂之和吗？« 使用
isSumOfXPowersOfTwo(n, x) {
return x<=n && x>=popcount(n).
}
有关 popcount 的有效位旋转实现，请参阅 this question。有些处理器甚至有一个指令。