language-agnostic - 使用按位运算符检查整数是否为 2^1-2^j 形式的单行器

Question

我想要一个单行代码来检查给定整数是否为 2 ⁱ - 2 ^j形式。（使用位运算符）

score 6 · Accepted Answer

正如 AndreyT 所说，答案可以在Hacker's Delight中找到：

使用以下公式关闭最右边的 1 位连续字符串（例如，01011000 ⇒ 01000000）：
((x | (x – 1)) + 1) & x
这可用于查看对于某些j ≥ k ≥ 0的非负整数是否为 2 ^j – 2 ^k形式；应用公式，然后对结果进行 0 检验。

（正在讨论是否发布这个问题，因为这是一个家庭作业问题，但正如 AndreyT 已经提到的那样，它很容易谷歌搜索，我认为直接引用更有帮助；我会让提问者处理接受帮助的伦理问题作业，我希望如果他的答案取决于此，他会自己写下它是如何工作的解释）

score 1 · Accepted Answer

一两个提示：

其他人指出，您正在寻找的是一个由一串一和一串零组成的数字。

如果您翻转其中的所有位，您将得到一串 0，后跟一串 1。如果你增加它，所有的 1 位都将变为 0，而恰好高于这些位的 1 位将变为 1。

如果你和最后两个一起，你会得到零。

score 0 · Accepted Answer

在二进制中，2 的幂是形式的数字100...0（A1后跟x 0s，其中x是指数）

^{因此，任何形式为 2 i} - 2 ^j的二进制数都将是一个1s 字符串，后跟一个0s 字符串。

Windows 计算器（二进制模式）是一个很好的试验方法。

score 0 · Accepted Answer

让我们看一下。如果 i=j，那么答案是检查整数是否为 0。否则，关键是查看位切换的频率我认为你想要看到的是，如果所有 1 一起作为一个组，集体，因为这里的算术真的很简单。如果切换为 2，那么它就是这种形式。

score 0 · Accepted Answer

0

左移直到你得到一个 0，一旦你得到一个零，你不应该再得到 1

于 2010-01-14T17:55:04.767 回答

5 回答 5