Hacker News Reader

Comment by Cyph0n | Hacker News Reader

I’d assume any decent compiler would optimize a “% 2” (or any power of 2) into a bitwise op. Could be wrong though!

Tested it! In C: https://godbolt.org/z/7xTrhGasc GCC uses &1 even using -O0. LLVM using -O0 still does the modulo, but at -O1 it does a clever &-2.

And even C#: https://godbolt.org/z/5WPfT8e5G Does use the &-2 strategy.

Dart also uses and: https://godbolt.org/z/1437df4En

So most of languages compiled to native binaries seem to do it. Languages like Ruby and Python don't seem to optimize this, which is hardly surprising. Ruby has a JIT now, and the JIT might do it.

And I'm not sure what the haskell version does, can someone explain: https://godbolt.org/z/xPP4E1a6h ?

If you change the code from "n `mod` n" to "n `mod` 2", and add "-O" as a compiler flag, you'll see an "and" with 1 pop up in the assembly.

Without -O, what's happening is that "mod" is a method from the Integral type class (for the non-haskellers: read "interface"/"abstract class"), and thus the program just reads the corresponding field from the stafically allocated copy of the Integral dictionary for Int, and subsequently calls it. Of course one should just inline this known function call, and that's precisely what -O lets ghc do.

Nice, thanks!

Can someone explain what's the &-2 method, and why it should be better than &1 ?

In two's complement, -2 means all bit are 1, except for the lowest. 1 is all bits are zero, except for the lowest. So it's basically the same, just negated. If you look at the generated code, this is used to the opposite: Keep all bits, except the least significant.

Btw, it's a lot simpler if you use only unsigned ints. Both GCC and clang add a couple more instructions to make it work with negative numbers. With unsigned ints, both gcc and clang generate this simple assembly code:

    is_even:
        mov     eax, edi
        and     eax, 1
        ret

And those additional instructions are there only because C modulo is defined to have the same sign as the dividend (so that e.g. -5 % 2 == -1 instead of 1). Had it been defined as being always positive, &1 would have been sufficient in all cases (that would also have the effect of making integer division round to negative infinity instead of zero which too can be implemented simply by >>1, for both signed and unsigned numbers).

Thank you, today I've learned something new.

So the easiest answer to the original question (whether a number is even or odd) likely involves &1, not %2. Note taken.

Why "even C#"? Nowadays we often can trade blows with LLVM and GCC :)

I'm mostly a C# dev, so I would like this to be true! But, you know, I'm skeptical...

But that probably isn't the function you want, because that will return -1 if the input is negative.

What you want to return is a boolean. And in that case the code generated is much simpler https://godbolt.org/z/5dq7MnrEx

Thanks for trying this out! It's the same with Rust: https://godbolt.org/z/89z9rEz9a

I once saw that the only thing writing &1 instead of %2 does is making your computer yawn

Easy enough to check with even the indecent compilers!

https://godbolt.org/

Reply on news.ycombinator.com