0

问题：检查一个非负整数的形式，2^j - 2^k where j>=k>=0即 2 的幂差。我的解决方案：该数字n (say)可以表示为 1 的连续序列for eg. 00011110。我将关闭 1 的连续序列（最右边）并对n. 我在这里所做的是，steps for solution 00011110 00011111(turn on trailing 0's) 00000000(then turn off trailing 1's). 使用这个公式(x | (x - 1)) & ((x | (x - 1)) + 1)。但是一个不使用文字的更有效的公式（可能是因为操作次数较少）((x & -x) + x) & x后面跟着一个零检查。而且我无法理解这一点，但它被写成它做同样的事情，但无法从我的结果中得出公式。谁可以给我解释一下这个？

编辑：32 位字，2 的补码

4

2 回答 2

2

给定即-x，~x + 1如果一个数的形式为 2^j - 2^k 则：

  • -x=2^k加上所有 1 >= 2^j，因为进位会向上波动，直到达到 2^k，然后停止；
  • 因此x & -x= 2^k;
  • 因此(x & -x) + x= 2^k; 和
  • 因此((x & -x) + x) & x= 0。

您可以按照该逻辑向后工作：

  • ((x & -x) + x) & x = 0 => ((x & -x) + x) 和 x 之间没有公共位；
  • x 和 ((x & -x) + x) 之间没有公共位意味着对于 x 中的连续 1 组， (x & -x) 必须设置这些位中的最低位，而其他位均不设置；
  • ... 鉴于携带涟漪的方式，实现这一目标的唯一方法是如果只有一组连续的 1。
于 2020-06-14T04:44:04.503 回答
1

你要求一个连接这两个表达式的代数证明，所以这是一个，但有一些不简单的步骤

((x | (x - 1)) + 1) & (x | (x - 1))
// rename x | (x - 1) into blsfill(x)
(blsfill(x) + 1) & blsfill(x)
// the trailing zeroes that get filled on the right side of the & don't matter,
// they end up being reset by the & anyway
(blsfill(x) + 1) & x
// filling the trailing zeroes and adding 1,
// is the same thing as skipping the trailing zeroes and adding the least-set-bit
(x + blsi(x)) & x
// rewrite blsi into elementary operations
(x + (x & -x)) & x
于 2020-06-14T14:07:26.280 回答