获得 power-of-2 相关结果的优雅方式

Question

First-off，抱歉标题含糊。这是我的问题：

设n > 0为自然数。确定正数 k 使得 2^i + k = n 最大可能 i.

我如何在 C 中优雅地做到这一点？

Answer 1

求2小于n的最大次方。（通过向下取整 log2n）调用数字 x.
你要找的k是n - 2^x.

或

您可以编写一个循环来检查每一个小于 n 的 2 的幂。

第一种方法更快。（恒定时间与 O(n) 时间）

Answer 2

int i = 0; j = 1, k, n = (your value);

if ( n > 0 )
{
    while ( 2 * j < n) 
    {
        j = 2 * j; 
        i++;
    }

    k = n - j;
}

// replace '<' with '<=' if k = 0 is desired where n is a pure power of 2

（注意：标准 C 中没有求幂运算符）

Answer 3

见仁见智

unsigned long find_remnant(unsigned long n) {
  for (unsigned long j, k = 0;
       (j = n&-n) != n;
       n -= j, k += j ) {
  }
  return k;
}

这是基于n&-n是n的二进制表示中的最低位1这一事实。所以循环从 n 中剥离一位，一次一个，将它们累加到 k 中，直到只剩下一个一位，它必须是 2^i.

由于循环在 n 中每个设置位执行一次，而不是在 n 中每个位执行一次，因此它可能更快。

万一这是一个问题，因为 0&-0 是 0，如果用参数 0 调用（与问题说明相反），该函数将简单地 return 0，这不是一个不合理的结果。

Answer 4

unsigned long fn(unsigned long n) {
    int x;
    frexp(n, &x);
    return n - (1UL << (x-1)); }

请注意，如果 n == 0（给出未定义的结果），这将失败，但您确实指定了 n > 0

获得 power-of-2 相关结果的优雅方式

Elegant way of getting a power-of-2-related result

c