# 应该以不同的方式检查一个数字的奇偶性吗？

go评论54阅读模式

Should I check for parity of a number in a different way?

# 问题

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 &amp; 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

Typically, the `&amp;` 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&amp;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.

• 本文由 发表于 2020年7月31日 23:20:34
• 转载请务必保留本文链接：https://go.coder-hub.com/63194658.html
• bit
• bit-manipulation
• java
• parity
• time-complexity

go 33

go 44

go 52