我想要一个单行代码来检查给定整数是否为 2 i - 2 j形式。(使用位运算符)
5 回答
正如 AndreyT 所说,答案可以在Hacker's Delight中找到:
使用以下公式关闭最右边的 1 位连续字符串(例如,01011000 ⇒ 01000000):
((x | (x – 1)) + 1) & x
这可用于查看对于某些j ≥ k ≥ 0的非负整数是否为 2 j – 2 k形式;应用公式,然后对结果进行 0 检验。
(正在讨论是否发布这个问题,因为这是一个家庭作业问题,但正如 AndreyT 已经提到的那样,它很容易谷歌搜索,我认为直接引用更有帮助;我会让提问者处理接受帮助的伦理问题作业,我希望如果他的答案取决于此,他会自己写下它是如何工作的解释)
一两个提示:
其他人指出,您正在寻找的是一个由一串一和一串零组成的数字。
如果您翻转其中的所有位,您将得到一串 0,后跟一串 1。如果你增加它,所有的 1 位都将变为 0,而恰好高于这些位的 1 位将变为 1。
如果你和最后两个一起,你会得到零。
在二进制中,2 的幂是形式的数字100...0
(A1
后跟x
0
s,其中x
是指数)
因此,任何形式为 2 i - 2 j的二进制数都将是一个1
s 字符串,后跟一个0
s 字符串。
Windows 计算器(二进制模式)是一个很好的试验方法。
让我们看一下。如果 i=j,那么答案是检查整数是否为 0。否则,关键是查看位切换的频率我认为你想要看到的是,如果所有 1 一起作为一个组,集体,因为这里的算术真的很简单。如果切换为 2,那么它就是这种形式。
左移直到你得到一个 0,一旦你得到一个零,你不应该再得到 1