计算小于 n 的最大 2 次方

Question

我正在尝试使用 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;

我使用了来自 Bit Twiddling Hacks 的以下 hack在nextHighestPowerOf2()中。

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

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

这两种替代方法可以在这里发挥作用:

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

但我想不出任何解决办法。有谁知道实现这一目标的其他方法吗？

Answer 1

这应该可以解决您的问题

unsigned long long int res = n - 1ULL<<( (int)log2(n-1) );

当然，当n<=1时，你必须设置特殊条件