如何在C程序中查找M是否实际上是2power(2n)+1的输出
我在项目中有一个棘手的要求，要求编写函数，如果给定一个可表示为2 2n +1的整数，该函数将返回值 1（否则为 0）。其中n是任何非负整数。
int find_pow_2n_1(int M);
例如：返回 1，当 M=5 时，因为当 n=1 -> 2 1*2 +1时输出 5 。
我正在尝试评估方程，但它导致日志函数，在 google 浏览时也无法找到任何类型的提示。
回答
解决方案
int find_pow_2n_1(int M)
{
return 1 < M && !(M-1 & M-2) && M % 3;
}
解释
首先，我们丢弃小于 2 的值，因为我们知道第一个匹配的数字是 2。
然后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是二加一的偶次幂时，其模三的余数为二，而当M是二加一的奇次幂时，其模三的余数为零：
- 2 0 +1 = 2 模 3 的余数是 2。
- 2 1 +1 = 3 模 3 的余数是 0。
- 2 2 +1 = 5 模 3 的余数是 2。
- 2 3 +1 = 9 模 3 的余数是 0。
- 2 4 +1 = 17 模 3 的余数是 2。
- 2 5 +1 = 33 模 3 的余数是 0。
- …
因此，M % 3测试M模三的余数是否M-1为非零的 ，测试是否为 2 的偶次幂。