bit twiddling ：检查非负整数作为 2 的幂的差
bit twiddling : checking non-negative integers as difference of powers of 2
问题：检查非负整数是否具有 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 的补码
鉴于 -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) 必须设置这些位中的最低位并且 none 其他的;
- ...考虑到携带涟漪的方式，实现这一目标的唯一方法是如果只有一组连续的 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
问题：检查非负整数是否具有 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 的补码
鉴于 -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) 必须设置这些位中的最低位并且 none 其他的;
- ...考虑到携带涟漪的方式，实现这一目标的唯一方法是如果只有一组连续的 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