1

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
    OR'ing any number with 0 will only give you the same number back, so I think your second tutorial may have been incorrect. Using AND with 1 is the normal path here, and if the result is 0, then it's even. If you wanted to go the OR path you'd have to OR with 1 and check if the result matches the original number, in which case it's odd, but that's a weird way to do it. – Scott Whitlock Jan 3 '15 at 18:48
  • 2
    you could OR with -2 (if 2's complement) and test if the result is -1 or -2 – ratchet freak Jan 3 '15 at 18:55
  • 3
    @ratchetfreak - it's definitely a good way to make the next programmer to read your code really annoyed. – Scott Whitlock Jan 3 '15 at 19:01
  • I'm voting to cancel the down-vote because even though I originally thought this was a poor quality question as well, I now think there are enough nuances to make it an interesting exercise in thinking about the instruction set. – Scott Whitlock Jan 3 '15 at 19:17
  • @ratchetfreak While it's not generally a good idea to puzzle the next programmer, it's nice to have in your arsenal the tools to do so. Thanks. Besides, "useless" tricks like this have a curious habit of proving themselves unexpectedly useful. I never reject an idea just because it's novel. – ganbustein Jan 4 '15 at 0:34
2

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.

1

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.