计算2的最大幂,它在C中均匀地除以数

Question

给定偶数,我需要写一些逻辑来确定.两个最高的力量均匀地划分它.输入%2 ^ n == 0时,2 ^ n的最大值是多少？

IE:
输入 - >输出

4  (0100)  -> 4

8  (1000)  -> 8

12 (1100)  -> 4

14 (1110)  -> 2

24 (11000) -> 8

etc....

看起来有一些按位逻辑可能会解决:当以二进制查看输入时,最右边的一位似乎是解决方案.如何在C中确定此值？还有其他解决方案可能更容易吗？

谢谢 - 乔纳森

Answer 1

如果你愿意假设2的补码算术:

x & -x

如果你做了很多这类事情(或者即使你觉得它很有趣),找一本书"Hacker's Delight"的副本.

编辑: avakar正确地指出,如果类型是无符号的,这不依赖于2的补码.该标准的相关部分是§6.2.5,第9段:

涉及无符号操作数的计算永远不会溢出,因为无法通过生成的无符号整数类型表示的结果将以比结果类型可以表示的最大值大1的数量为模.

"大于最大值的一个"为一个特别不正确的实现留下了一些摆动空间(例如,一个不使用二进制的实现),但是你很可能不会遇到这种情况.

+1.为了记录,你不必假设2的补码.只要`x`是无符号算术类型,这将适用于任何架构. (3认同)
假设我们有一个带有1的补码算法的32位类型:如果x是1,那么`-x`是`0xfffffffe`,而`x&-x`是0,这不是提问者想要的答案.正如JF Sebastian指出的那样,你可以通过使用`x&(~x + 1)`来解决这个问题,这只是2的恭维否定扩展为两个操作. (2认同)
对于`x` unsigned,`-x`对于某些`k`将是'2 ^ kx`.在你的例子中,`k`将是32而`-x`将是`0xffffffff`.同样,`unsigned`是这里的关键,对于签名的`x`,所有的赌注都是关闭的. (2认同)

Answer 2

不使用浮点运算:

((x ^ (x - 1)) >> 1) + 1

简化和边缘情况留给读者练习.

Answer 3

我们可以替换(-x)为(~x + 1):

x & (~x+1)