c - 计算小于n的2的最大幂

我正在尝试使用C中的位操作来执行此操作。

From a number n, substract the largest power of 2 smaller than n.

For example:
6 - 4 = 2
11 - 8 = 3

我的方法是：

next2power = nextHighestPowerOf2(n)
previous2power = next2power >> 1;
result = n - previous2power;

我曾使用nextHighestPowerOf2()中Bit Twiddling Hacks的以下技巧。

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v |= v >> 32;
v++;

问题是即使我使用next2power，unsigned long long也会溢出。 n的顺序为2^64。所以这种方法对我不起作用。

这两种替代方法可以在这里工作：


通过将前导1翻转为0。
以某种方式计算小于n的2的最大功率而不会溢出，然后从n减去它


但是我想不出任何解决方案。有人知道实现此目标的其他方法吗？

最佳答案

我认为您在输入或打印值时可能会犯一个错误；您问题中的代码对我有用：

#include <stdio.h>
int main() {
        unsigned long long input, v;

        input = 7597026128958891522ULL;
        v = input;
        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        v |= v >> 32;
        v++;
        v= v>>1;
        printf("Input %llu, next lower power of 2 %llu\n", input, v);
}

屈服

Input 7597026128958891522, next lower power of 2 4611686018427387904

关于c - 计算小于n的2的最大幂，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37238759/