I recently learned of the trick for finding out if a binary number is odd or even.
If the last bit in the number is 0, then the number is even. If it ends in a 1, then the number is odd.
In the tutorial in which I read this, is stated that this could be applied to programming if you “AND” the number with the binary number 1.
In another tutorial that I read, they said that is could applied if you “OR” the number with binary 0.
In regards to efficiency, which method would be more efficient for finding out if a number is odd or even?
5
Ultimately, this depends on the processor or the interpreter you are using. I have not encountered a situation in which these operations differed respectably in execution time.
A GMP developer maintains a paper on x86/amd64 instruction latencies and throughput. This paper shows that both AND and OR instructions have the same timings when both arguments are registers. When one of the operands is a memory address, of course timing might change when that memory is not in cache. But this is not a function of the instruction.
Unfortunately, I can’t speak to other processors or whether people have done asinine things in interpreters that would cause a performance disparity.
There is a Bit Test instruction in the x86 instruction set (since 80386):
BT copies a bit from a given register to the carry flag.
As I understand it, you can then execute a JC (jump if carry) instruction to make a decision based on the carry flag. That’s a total of two elemental instructions and uses only one register.
However, I doubt that’s more efficient than using AND with 1 and jump if the zero flag is set. Both alternatives are two elemental CPU instructions. It’s possible the constant to specify the bit in the BT instruction uses fewer bits than the constant operand of the AND instruction, but I’m not going to bother looking it up. 🙂
That probably means the OR method is less efficient because you’d have to do the OR, then a compare to the original number and jump if equal or not equal, which at the very least is tying up 2 registers instead of 1.
A slightly better alternative than AND might be the TEST instruction because it performs an AND but throws away the result of the operation and only keeps the flags set. Since you don’t actually want to keep the result, then TEST eax, 1 followed by jump if zero (JZ) might be your best bet (since it’s possible you might want to do something else with the original value and this leaves it loaded in the register).