我应该以不同的方式检查数字的奇偶校验吗？
Should I check for parity of a number in a different way?
在 Java 以及其他语言中，我总是使用 N % 2 == 0 技巧来获取数字的奇偶校验，但我很确定在时间复杂度方面有一些更好的解决方案。
使用 N & 1 == 0 可能已经更好了，但是 运行 是在恒定时间内执行的， 即 是否只进行最右边的位比较，或者它是否完成组成 N 的所有 log(N) 位？
是否有可能以某种方式只读取数字的最后一位，这肯定是恒定时间？
通常，& 运算符是在硬件电路中实现的。该电路在一个步骤中并行遍历数字的所有位。它不会一位一位地查看。
另一方面，整数除法和取余运算要复杂得多。流行的 CPU 没有专门的电路，而是在 microcode 中实现。很难找到主要来源，但互联网上的不同来源表明整数除法的成本大约是 AND.
等位运算符的 20-40 倍
编译器编写者很清楚除法和求余指令的开销有多大，并尽一切可能避免生成使用这些指令的代码 - 请参见示例 Why does GCC use multiplication by a strange number in implementing integer division? 很可能但不能保证N%2==0 被编译为 N&1==0。为了确定，您必须检查编译器生成的机器代码。在Java中，你最应该关心的编译器就是JIT编译器。它动态生成本机机器代码。检查其输出是可能的，但并不容易。此外，它所做的优化可能会从一个版本更改为下一个版本，或者在 CPU 个型号之间有所不同。
如果您真的想知道在您的应用程序中哪个硬件更快，您应该创建一个基准测试并自己进行测试。
在 Java 以及其他语言中，我总是使用 N % 2 == 0 技巧来获取数字的奇偶校验，但我很确定在时间复杂度方面有一些更好的解决方案。
使用 N & 1 == 0 可能已经更好了，但是 运行 是在恒定时间内执行的， 即 是否只进行最右边的位比较，或者它是否完成组成 N 的所有 log(N) 位？
是否有可能以某种方式只读取数字的最后一位，这肯定是恒定时间？
通常，& 运算符是在硬件电路中实现的。该电路在一个步骤中并行遍历数字的所有位。它不会一位一位地查看。
另一方面，整数除法和取余运算要复杂得多。流行的 CPU 没有专门的电路，而是在 microcode 中实现。很难找到主要来源，但互联网上的不同来源表明整数除法的成本大约是 AND.
编译器编写者很清楚除法和求余指令的开销有多大，并尽一切可能避免生成使用这些指令的代码 - 请参见示例 Why does GCC use multiplication by a strange number in implementing integer division? 很可能但不能保证N%2==0 被编译为 N&1==0。为了确定，您必须检查编译器生成的机器代码。在Java中，你最应该关心的编译器就是JIT编译器。它动态生成本机机器代码。检查其输出是可能的，但并不容易。此外，它所做的优化可能会从一个版本更改为下一个版本，或者在 CPU 个型号之间有所不同。
如果您真的想知道在您的应用程序中哪个硬件更快，您应该创建一个基准测试并自己进行测试。