2

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

4

5 回答 5

6

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

使用以下公式关闭最右边的 1 位连续字符串(例如,01011000 ⇒ 01000000):

((x | (x – 1)) + 1) & x

这可用于查看对于某些jk ≥ 0的非负整数是否为 2 j – 2 k形式;应用公式,然后对结果进行 0 检验。

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

于 2010-01-14T17:57:21.653 回答
1

一两个提示:

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

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

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

于 2010-01-14T18:20:50.220 回答
0

在二进制中,2 的幂是形式的数字100...0(A1后跟x 0s,其中x是指数)

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

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

于 2010-01-14T17:47:47.637 回答
0

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

于 2010-01-14T17:48:52.050 回答
0

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

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