如何在 C 程序中查找 M 是否实际上是 2power(2n) + 1 的输出

Question

我在项目中有一个棘手的要求，要求编写 return 值为 1（否则为 0）的函数，如果给定一个可表示为 2^{2n[=21 的整数=]+1}。其中 n 是任何非负整数。

int find_pow_2n_1(int M);

例如：return 1，当M=5时，因为当n=1时输出5 -> 2^1*2+1 .

我正在尝试计算方程式，但结果是对数函数，在 google 中浏览时也找不到任何类型的提示。

Answer 1

只有几个数字属性：创建一个 table 查找数组 :-)

$ bc
for(n=0;n<33;n++)2^(2*n)+1
2
5
17
65
257
1025
4097
16385
65537
262145
1048577
4194305
16777217
67108865
268435457
1073741825
4294967297
17179869185
68719476737
274877906945
1099511627777
4398046511105
17592186044417
70368744177665
281474976710657
1125899906842625
4503599627370497
18014398509481985
72057594037927937
288230376151711745
1152921504606846977
4611686018427387905
18446744073709551617

上面的最后一个数字是 2^64 + 1，可能不适合您的实施中的 int。

Answer 2

这里我留给你一个伪代码（或者我没有测试过的代码），我认为它可以帮助你想出解决问题的方法:)

#include <math.h>
#include <stdlib.h>

#define EPSILON 0.000001


int find_pow_2n_1(int M) {
    M--;   // M = pow 2n now
    double val = log2(M);    // gives us 2n
    val /= 2;    // now we have n
    if((val * 10) / 10 - val) <= EPSILON) return 1;   // check whether n is an integer or not
    else return 0;
}

Answer 3

解决方案

int find_pow_2n_1(int M)
{
    return 1 < M && !(M-1 & M-2) && M % 3;
}

说明

首先，我们丢弃小于二的值，因为我们知道第一个匹配的数字是二。

然后M-1 & M-2测试M-1中是否设置了多于一位：

M-1 不能设置零位，因为 M 大于一，所以 M-1 不为零。
如果 M-1 设置了一位，则该位在 M-2 中为零并且所有低位都已设置，因此 M-1 和 M-2 没有设置位共同点，所以 M-1 & M-2 为零。
如果 M-1 设置了多个位，则 M-2 清除了最低的设置位，但较高的设置位保持设置。所以 M-1 和 M-2 有共同的设置位，所以 M-1 & M-2 是非零的。

所以，如果测试 !(M-1 & M-2) 通过，我们就知道 M-1 是 2 的幂。所以 M 比二的幂大一。

我们剩下的问题是这是否是 2 的偶数次幂。我们可以看到，当M是2加1的偶次方时，它的余数模3是2，而当M是2加1的奇数次方时，它的余数模3是0：

2⁰+1 = 2 模 3 的余数是 2.
2¹+1 = 3 模 3 的余数为 0.
2²+1 = 5 模 3 的余数是 2.
2³+1 = 9 模 3 的余数为 0.
2⁴+1 = 17 模 3 的余数是 2.
2⁵+1 = 33 模 3 的余数为 0.
…

因此，M % 3，它测试 M 模 3 的余数是否非零，测试 M-1 是否是 2 的偶次方。

Answer 4

所有提出的解决方案都太复杂或性能太差。试试更简单的：

static int is_power_of_2(unsigned long n)
{
  return (n != 0 && ((n & (n - 1)) == 0));
}

static int is_power_of_2n(unsigned long n)
{
  return is_power_of_2(n) && (__builtin_ffsl(n) & 1);
}

int main(void)
{
  int x;

  for (x = -3; x < 20; x++)
    printf("Is %d = 2^2n + 1? %s\n", x, is_power_of_2n(x - 1) ? "Yes" : "no");
  return 0;
}

实现__builtin_ffsl()，如果你用的是古老的编译器，我把它留作作业（可以不用表格或除法）。

示例：https://wandbox.org/permlink/gMrzZqhuP4onF8ku

在评论@Lundin 的评论时，我意识到您可能会读到斯坦福大学的一套非常好的 bit twiddling hacks。

更新。由于 @grenix 注意到最初的问题是关于直接检查的，所以可以通过引入额外的包装器使用上面的代码来完成，所以基本上没有什么变化：

...

static int is_power_of_2n_plus_1(unsigned long n)
{
  return is_power_of_2n(n - 1);
}

int main(void)
{
  int x;

  for (x = -3; x < 20; x++)
    printf("Is %d = 2^2n + 1? %s\n", x, is_power_of_2n_plus_1(x) ? "Yes" : "no");
  return 0;
}

如何在 C 程序中查找 M 是否实际上是 2power(2n) + 1 的输出

how to find if M is actually an output of 2power(2n) + 1 in C program

c

embedded

解决方案

说明