It may be worth pointing out: these are equivalent comparisons when testing for even numbers but cannot be extrapolated to testing for odd numbers. The reason being that a negative odd number modulus 2 is -1, not 1.

So `n % 2 == 1` should probably [1] be replaced with `n % 2 != 0`.

While this may be obvious with experience, if the code says `n % 2 == 0`, then a future developer who is trying to reverse the operation for some reason must know that they need to change the equality operator not the right operand. Whereas, with `n % 1 == 0`, they can change either safely and get the same result.

This feels problematic because the business logic that necessitated the change may be "do this when odd" and it may feel incorrect to implement "don't do this when even".

I really disfavor writing code that could be easily misinterpreted and modified in future by less-experienced developers; or maybe just someone (me) who's tired or rushing. For that reason, and the performance one, I try to stick to the bitwise operator.

[1] Of course, if for some reason you wanted to test for only positive odd numbers, you could use `n % 2 == 1`, but please write a comment noting that you're being clever.

Optimizing compilers have been able to recognize pretty complicated patterns for many years.

For instance if you're making a loop to count the bits that are set in a number, the compiler can recognize the entire loop and turn it into a single popcnt instruction (e.g. https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... )

The interesting thing about testing values (like testing whether a number is even) is that at the assembly level, the CPU sets flags when the arithmetic happens, rather than needing a separate "compare" instruction.

gcc likes to use `and edi,1` (logical AND between 32-bit edi register and 1). Meanwhile, clang uses `test dil,1` which is similar, except the result isn't stored back in the register, which isn't relevant in my test case (it could be relevant if you want to return an integer value based on the results of the test).

After the logical AND happens, the CPU's ZF (zero) flag is set if the result is zero, and cleared if the result is not zero. You'd then use `jne` (jump if not equal) or maybe `cmovne` (conditional move - move register if not equal). Note again that there is no explicit comparison instruction. If you don't use O3, the compiler does produce an explicit `cmp` instruction, but it's redundant.

Now, the question is: Which is more efficient, gcc's `and edi,1` or clang's `test dil,1`? The `dil` register was added for x64; it's the same register as `edi` but only the lower 8 bits. I figured `dil` would be more efficient for this reason, because the `1` operand is implied to be 8 bits and not 32 bits. However, `and edi,1` encodes to 3 bytes while `test dil,1` encodes to 4 bytes. I guess the `and` instruction lets you specify the bit size of the operand regardless of the register size.

There is one more option, which neither compiler used: `shr edi,1` will perform a right shift on EDI, which sets the CF (carry) flag if a 1 is shifted out. That instruction only encodes to 2 bytes, so size-wise it's the most efficient.

The right-shift option fascinates me, because I don't think there's really a C representation of "get the bit that was right-shifted out". Both gcc and clang compile `(i >> 1) << 1 == i` the same as `i & 1 == 0` and `i % 2 == 0`.

Which of the above is most efficient on CPU cycles? Who knows, there are too many layers of abstraction nowadays to have a definitive answer without benchmarking for a specific use case.

I code a lot of Motorola 68000 assembly. On m68k, shifting right by 1 and performing a logical AND both take 8 CPU cycles. But the right-shift is 2 bytes smaller, because it doesn't need an extra 16 bits for the operand. That makes a difference on Amiga, because (other than size) the DMA might be shared with other chips, so you're saving yourself a memory read that could stall the CPU while it's waiting its turn. Therefore, at least on m68k, shifting right is the fastest way to test if a value is even.

> Much better :) But what about C? Let’s try it:

> I tried both versions (modulo 2 and bitwise AND) and got the same result. I think the optimizer recognizes modulo 2 and converts it to bitwise AND.

Yes, even without specifying optimizations - https://godbolt.org/z/9se9c6qKT

You can see that the output of the compiler is identical whether you use `i%2 == 0` or `(i&1) == 0`. The bitwise AND is instruction 12 in the output.

Using -O3 like in the post actually compiles to SIMD instructions on x86-64 - https://godbolt.org/z/dWbcK947G

> I think the optimizer recognizes modulo 2 and converts it to bitwise AND.

A quick check in the compiler explorer (godbolt.org) confirms that this is indeed true for GCC on x86_64 and aarch64, but not for clang on the same (clang does optimize it with -O3).

"Premature optimization is the root of all evil." -- Donald Knuth [0]

[0]: https://www.youtube.com/watch?v=74RdET79q40

Why write redundant code? I just depend on an external is-even library, which depends on an is-odd library ;)

(https://news.ycombinator.com/item?id=38791094)

I like the algorithms that are the opposite of this where they try to find the slowest possible way to determine if a number is even.

I did some testing and even in python both approaches are nearly identical in speed:

    def isEven_modulus(num):
        return num % 2 == 0

    def isEven_bit(num):
        return (num & 1) == 0

    import random, time

    testSet = random.choices(range(0, 100), k=10)
    iterations = range(1000)

    print("These are our test numbers: ", testSet)

    mod_start = time.perf_counter_ns()
    for z in iterations:
        for n in testSet:
            isEven_modulus(n)
            
    mod_end = time.perf_counter_ns()
    for z in iterations:
        for n in testSet:
            isEven_bit(n)

    bit_end = time.perf_counter_ns()

    print("Modulus method: ", mod_end - mod_start, "ns")
    print("Bitwise method: ", bit_end - mod_end, "ns")

An example:

    These are our test numbers:  [45, 88, 55, 52, 40, 70, 62, 47, 78, 30]
    Modulus method:  757341 ns
    Bitwise method:  698872 ns

When I wrote in ASM, I always used to look at the LSB (Least Significant Bit). If it was zero, then the number was even.

Things are probably different, these days, so maybe that isn’t effective.

You can actually generalize i % 2 == i & 1 to larger powers of 2.

Using C Syntax,

i % (1 << n) == i & ((1 << n) - 1)

holds for unsigned integer n and (1 << n) is 2 to the power of n.

> I think the optimizer recognizes modulo 2 and converts it to bitwise AND.

You don't have to guess, you could turn or O3 or look at the disassembly.

I'm quite surprised that it wasn't recognized by scalar evolution, a common optimization pass to detect induction variables and their relations to other variables. Of course that requires the compiler to reason about `i % 2 == 0` or `(i & 1) == 0` first, but modern compilers do have tons of patterns recognized by that pass...

Does the C compiler optimise out the branch from the if() statement?

I'd write it more like this:

    int main(int argc, char **argv) {
      int total = 0;
      for (int i=2147483647; i; --i) {
        total += i & 1;
      }
      printf("%d\n", total);
      return 0;
    }

Just test if last bit == 0

Wait until you hear what C compilers try to do if you divide by a constant. Hint: they don't need to use a division instruction in most cases.

I'm nowhere near an APL-level programmer, but that C example already looks ridiculously verbose to me; the body of the loop could be simply written branchlessly as:

    total += !(i&1);

    test dl, 1
    setnz bl
    add eax, ebx

That’s not “even” wrong!

Now try `!(n & 1)`.

In Javascript, NaN (not a number) is a number:

  >> typeof NaN
  <- "number"

  >> (NaN % 2) == 0
  <- false

(And if you're thinking "you gotta equals harder":

  >> (NaN % 2) === 0
  <- false

Both of the infinities are also odd by the same logic, too, if you were curious.

null and false are even. true is odd. [] is even, [0] is even, [1] is odd.)