# When trying to find out if a number is even or odd: AND 1 or OR 0

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?

• `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
• 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
• @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

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