如何更有效地区分大数的奇数和偶数？

Question

如果已经有一些类似的问题，请通过评论告诉我。

当我们通常尝试区分奇数和偶数时，我们可以尝试以下 C++ 代码。

    int main() {
        int n=10;
        
        for(n; n>0; n--){
            
            if(n%2==0) std::cout<< "even" << '\n';
            if(n%2==1) std::cout<< "odd" << '\n';      
        }   
    }

我确信超过 99% 的本科生，甚至专业人士，都会使用条件“if (n%2==0)...else”来区分奇数和偶数。

然而，当数字范围足够大时，在我看来，“if (n%2==0)...else”方法可能效率很低。让我来解释一下原因。

 int main() {
        int n=100000;
        
        for(n; n>0; n--){
            
            if(n%2==0) std::cout<< "even" << '\n';
            if(n%2==1) std::cout<< "odd" << '\n';      
        }   
    }

当整数“n”很小时，除以每个小于它的正整数并不是什么大问题。

但是，当它变大时，除了分割之外，难道没有其他更有效的方法吗？

我们人类通常不会计算模 2 来知道“10^1000 + 1”是奇数还是偶数。对于“10^1000 + 2”、“10^1000 + 3”等也是如此。我们只需查看整数的最后一位就可以知道答案。

我不是计算机科学方面的专家，所以尽管我不确定这些信息，但我听说机器对二进制数比人类友好得多。如果是这样，计算机是否可以仅通过查看输入的最后一位数字（无论是 0 还是 1）来更快地区分奇数和偶数？

如果对此有一些直接的答案，我相信许多中级数值算法可以从答案中受益。期待有人的帮助。

谢谢。

Answer 1

50000000%2和5%2的执行时间真的一样吗？

这是假设编译器“查看数字”并“知道”它的值有多大。分裂的情况并非如此。编译器看到 anint并对其执行一些操作int。不同的值只是不同的位设置，在int执行除法时总是需要考虑相同的字节数。

另一方面，%2这是一个如此常见的操作，编译器确实“知道去哪里寻找”：最后一位。

考虑这两个函数：

bool is_odd1(int n) { return (n%2);} 
bool is_odd2(int n) { return (n&1);}

true当n奇数时两者都会返回。

is_odd1使用%它定义为除法后的余数。不过，仅仅因为它是这样定义的并不意味着它必须这样实现。编译器将生成根据定义生成结果的代码，并且该代码预计非常高效。

is_odd2只考虑最低位n来检查是否已设置。

打开优化后，gcc 会为两者生成完全相同的输出：

is_odd1(int):
        mov     eax, edi
        and     eax, 1
        ret
is_odd2(int):
        mov     eax, edi
        and     eax, 1
        ret

这两个函数除了检查最低位是否n已设置外什么都不做。

现场演示。

结论：不用担心这种微观优化。如果可能的话，它们会在编译器中实现。而是为了清晰和可读性而编写代码。

但是，不要大规模引入低效率的情况。例如，如果您像这样编写代码，则无需依赖编译器优化：

    for(; n>0; n-=2){
        std::cout<< "even" << '\n';
        std::cout<< "odd" << '\n';      
    } 

不过，这无论如何都不是一个好例子，因为将某些内容打印到控制台比检查单个位是否设置要昂贵得多。