英文:
Should I check for parity of a number in a different way?
问题
在Java以及其他编程语言中，我通常使用 N % 2 == 0 的技巧来获取一个数字的奇偶性，但我相当肯定在时间复杂度方面存在更好的解决方案。
使用 N & 1 == 0 可能已经更好了，但它是否在常数时间内运行，即它是否只进行右侧比特的比较，还是会处理N的所有log(N)位组成？
是否有可能以某种方式只读取数字的最后一位比特，这肯定是在常数时间内的？
英文:
In Java, as well as other languages, I always use the N % 2 == 0 trick to obtain the parity of a number, but I'm pretty sure that in terms of time complexity there is some better solution.
It's probably better already by using N & 1 == 0, but does this run in constant time, i.e. does it just do the rightmost bit comparison, or does it do all of the log(N) bits composing N?
Is it possible to somehow just read the last bit of the number, which would be in constant time for sure?
答案1
得分: 3
通常，& 操作符在硬件电路中实现。电路会一次性并行运行在数字的所有位上，而不是逐位查看。
另一方面，整数除法和取余操作要复杂得多。流行的CPU不会为此提供特殊电路，而是在微码中实现。很难找到主要信息源，但互联网上的不同来源将整数除法的代价约为按位运算符如 AND 的20-40倍。
编译器编写者非常了解除法和取余指令的昂贵，会尽一切可能避免生成使用这些指令的代码 - 详见例如 https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi 很可能，但不能保证，N%2==0 会编译成 N&1==0。要确保，您需要检查编译器生成的机器代码。在Java中，您最关心的编译器应该是JIT编译器。它会即时生成本机机器代码。检查其输出是可能的，但不容易。此外，它所做的优化可能会从一个版本到另一个版本变化，或者在不同的CPU型号之间有所不同。
如果您真的想知道在您的应用程序中在您的硬件上哪个更快，您应该创建一个基准测试并自行测试。
英文:
Typically, the & operator is implemented in hardware circuitry. The circuitry runs over all the bits of the number in parallel in one single step. It does not look at bits one by one.
Integer division and remainder operations on the other hand are a lot more complex. Popular CPUs don't have special circuitry for it, instead it's implemented in microcode. It's hard to find a primary source, but different sources on the internet put integer division at about 20-40 times as expensive as bitwise operators like AND.
Compiler writers are well aware how expensive the division and remainder instructions are, and do everything possible to avoid generating code that uses these instructions - see for example https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi It is very likely, but not guaranteed, that N%2==0 is compiled to N&1==0. To make sure, you would have to examine the machine code generated by the compiler. In Java, the compiler you should most care about is the JIT compiler. It generates native machine code on the fly. Examining its output is possible, but not easy. Also, the optimizations it does may change from one version to the next, or vary between CPU models.
If you really want to know which is faster in your application with your hardware, you should create a benchmark and test it yourself.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论