通过位移找到奇数

Question

（此题参考thisCodeforces题）我想知道 n (2 ≤ n ≤ 10¹⁴) 是否有奇数。使用 C++11，我认为可以通过遍历每个奇数直到 n 并检查 % 是否可整除来强制解决方案。例如：

for(unsigned long long i=3;i<n;i+=2){
   if(n%i==0) return true; //It has an odd divisor
}
return false; //n%j==0 was never true so it doesn't have an odd divisor

当然，如果给出任何大数字，结果会非常慢。我发现人们通过移位来解决它，并检查最后一位是否为 1，类似于此：

while(!(n&1))n>>=1;
if(n==1) return false; else return true;

如果我没记错的话，最后一段代码是通过执行 n=n/2ⁿ 检查它是否与最后一位 (n&1) 奇数。计算 n=n/2ⁿ 在解决问题方面如何与检查每个奇数具有相同的准确性？（我怎么知道我不是''skipping''除数？）。

Answer 1

这个更优化的解决方案有效地去除了任何 2 的幂，如果余数不是 1 的因数，它必须涉及其他一些因数。

因为所有偶数因子本身都有 2 作为因子，这只是将数字“煮沸”直到有余数因子，或者 1.

举个例子：

0b11010 (26) -> 0b1101 (13)
0b11000 (24) -> 0b11 (3)
0b10000 (16) -> 0b1 (1)

你还可以有几个 prime 因子，如：

0b1111110000 (1008) -> (63)

那是 9 x 7，但您可以将 63 视为唯一相同的非偶数因子。

Answer 2

要理解这一点，您必须了解奇数和偶数最右边的位是如何工作的。
基本上任何奇数都有它的第 0 位（最右边）为 1（记住位从右开始计数，即最右边的位是第 0 位，然后你一个一个地向左移动，即第 1 位，第 2 位等等）和任何偶数它的第 0 位为 0.
所以当你这样做时

int value = n & 1;

你在做什么是你在做 n 和 1 的 'AND'，所以如果 n 是奇数，那么它的第 0 位将是 1，所以当你假设例如

int result = 5 & 1;

现在看起来像这样

(101) & (001)

所以你得到 1 作为结果（因为 1 的所有其他位都是 0，所以 5 和 1 的所有其他位的 AND 的结果将是 0，所以基本上你仍然是 1），但是如果n为偶数，则第0位为0，例如

int result = 10 & 1;

看起来像这样

1010 & 0001

现在根据前面的例子，你可以看到在偶数的情况下结果总是0。这就是为什么用这种方式检查一个数字是奇数还是偶数要快得多，因为你不进入所有模数和其他更高级别的东西，你在这里做的是低级别的东西。

所以来到重点，发生的事情是我们必须检查一个数字是否包含任何奇数除数，让我们逐步看一下
一个数字只不过是它的除数的倍数，例如

30 = 10 * 3;
30 = 15 * 2;
30 = 5 * 6

但如果你仔细观察，你会发现它总是相同的唯一质数的组合，即

30 = 2 * 5 * 3;
30 = 3 * 5 * 2;
30 = 5 * 2 * 3;

所以现在让我们看看质数中的一个事实，我们看到2是唯一一个不奇数的质数。
如果我们接受这个事实，我们可以确定如果 2 乘以任何其他素数，那么所得数字将始终是奇数（记住偶数 * 奇数 = 奇数）。所以如果我们想要一个没有任何奇数除数的数字，那么我们不希望它的乘法组合中有任何奇素数，那么这个数字应该只是 2 的乘法组合，换句话说就是 2 的幂。（我们可以忽略 1 的情况，因为问题中提供了不将其视为输入）

所以如果我们只是检查一个数字是否是 2 的幂，我们的问题就解决了，即如果它是 2 的幂，那么它不包含任何奇数除数，否则它包含奇数。
现在我们如何确定一个数字是否是 2 的幂。
所以我们看到的任何数字都可以是二进制表示中不同位的组合
例如

10 = (1010) (2^3 * 1 + 2^2 * 0 + 2^1 * 1 + 2^0 * 0)

如果任何数字是 2 的幂，那么它在二进制表示中将只有一个位为 1，所有其他位将为 0（对于 2^0 = 1 的情况，您可以看到我们已经给出 x > 1 的约束，因此我们可以忽略 1)

的案例处理

现在让我们看看这段代码

// it runs the while loop until all the right bits of first 1 bit is 0, that is it runs till we shift our rightmost 1 bit to 0th bit
while(!(n & 1)) { 
    n >>= 1; // if we are inside the loop, it means rightmost 1 is still not at 0th bit position, as the AND is done for 0th bit like I explained above, so doing this will right shift our rightmost 1, i.e if it was at 2nd position, it will now come at 1st position 
}

if(n == 1) {
   // if it is 1, it means only 1 bit is there in whole binary representation of the number which is at 0th position, it means it is a power of two(remember that this n is calculated based on sum of all the power of 2)
    return false; 
} else {
    return true;
}

Answer 3

!(n & 1)等价于n & 1 == 0，判断n是否为偶数，因为n & 1奇数为1，偶数为0[=41] =] n >>= 1 整数除以二。
（作为旁注，几十年来，编译器完全有能力对 n % 2 == 0 和 n /= 2 进行这种优化，并且在确定它何时真正有益方面比人类要好得多。）

接下来，数学：

最小的奇约数也是最小的奇质因数。

如果x是奇数，我们知道它至少有一个奇质因数，因此至少有一个奇数约数。

如果x是偶数，可以写成2 * y，其中y就是x/2.
我们还知道，我们可以将 x 写为其质因数 2 * f0 * f1 * ... * fn.
的乘积因此，y是f0 * f1 * ... * fn，x/2的奇数与x的奇数完全相同。

重复 x/2，直到达到 1 或大于 2 的奇数。

Answer 4

问题本身有些歧义。
在所有情况下，问题的答案都很简单 true，因为奇数 1 是任何整数 n.
的约数因此，我怀疑其目的是找到 1.

的一些奇数除数

根据算术基本定理，一个正整数可以唯一分解为所有素数乘积的非负整数次幂。

例如，数字600被分解为2*2*2*3*5*5的乘积。
唯一的偶数引物数是2，因此，n除以其素数分解的所有等于2的因子后，只剩下奇数素数。

如果n有一些与1不同的奇数，那么将n除以2尽可能多的次数，我们将得到除以[=13=的最大奇数].

另一方面，除以 2 相当于平移 1:
(n/2) == (n >> 1)

因此，尽可能多地移位得到这样的最大奇数就足够了。

int odd_divisor = n;
while (odd_divisor % 2 == 0)
  odd_divisor /= 2;
return odd_divisor;  // This number is odd,
                     // it is a divisor of n,
                     // and do with it
                     // whatever you want.

如果数字odd_divisor == 1表示n的唯一奇数除数是1，因此在这种情况下问题的答案似乎是false .
否则，答案是 true.

可以替换操作odd_divisor /= 2
通过 odd_divisor >>= 1、
你也可以替换 odd_dividor % 2 == 0
通过条件 odd_dividor & 1 == 0.

正如其他人已经提到的，整数在内存中的表示是在基数2中完成的，因此检查它的最后一位等同于检查其奇偶校验。

通过位移找到奇数

Finding odd divisors with bit-shifting

c++

c++11

bit-shift