math - 检查一个数是否可​​以表示为 2 的 x 次幂之和

Question

是否有一些小技巧可以检查一个数字是否可以表示为 2 的 x 次幂之和？

示例:对于 x=3 n=21，数字为 16、4 和 1。如果 n=30，则应该为 false，因为不存在 3 的 2 的幂来表示 30。

Answer 1

对于数字 n ...

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

现在来了一个难题。如果 x 介于 popcount(n) 和 n 之间怎么办？
事实证明，所有这些 x 都是可能的。求 2 的 x 次方之和……

• 从最短的总和(n 的二进制表示)开始
• 如果加数少于 x 个，则将任何大于 1 的加数分成两个加数，将加数的数量增加 1。可以一直这样做，直到到达 x=n。

示例:Can 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 。有些处理器甚至有相关指令。