时间戳

首页 > 解决方案 > 检查一个数字是否可以表示为 x 的 2 次方之和？

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

问题描述

是否有任何技巧可以检查一个数字是否可以表示为 2 的 x 次方之和？例如：x=3 n=21 如果 n=30，数字是 16,4,1 它应该是假的，因为没有 3 的 2 的幂来表示 30

标签： mathbinarybit-manipulation

解决方案

对于一个数字 n ...</p>

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

现在来了一个难题。如果 x 在 popcount(n) 和 n 之间怎么办？
事实证明，所有这些 x 都是可能的。构建两个的 x 次方的总和……</p>

  • 从最短的和开始（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请参阅此问题。一些处理器甚至有一个指令。

推荐阅读