4 ms·

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

Tested it! In C: https://godbolt.org/z/7xTrhGasc 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 https://godbolt.org/z/5WPfT8e5G Does use the &-2 strategy. Dart also uses and: https://godbolt.org/z/1437df4En 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 https://godbolt.org/z/xPP4E1a6h ?

tomsmeding 3y ago
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.
- roetlich 3y ago
  Nice, thanks!
teo_zero 3y ago
Can someone explain what's the &-2 method, and why it should be better than &1 ?
- roetlich 3y ago
  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
  - Joker_vD 3y ago
    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).
    - teo_zero 3y ago
      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.
neonsunset 3y ago
Why "even C#"? Nowadays we often can trade blows with LLVM and GCC :)
- roetlich 3y ago
  I'm mostly a C# dev, so I would like this to be true! But, you know, I'm skeptical...
IAmLiterallyAB 3y ago
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 https://godbolt.org/z/5dq7MnrEx
Cyph0n 3y ago
Thanks for trying this out! It's the same with Rust: https://godbolt.org/z/89z9rEz9a https://godbolt.org/z/89z9rEz9a

tomsmeding 3y ago

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.

roetlich 3y ago
Nice, thanks!

teo_zero 3y ago

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

roetlich 3y ago
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
- Joker_vD 3y ago
  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).
  - teo_zero 3y ago
    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.

neonsunset 3y ago

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

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

IAmLiterallyAB 3y ago

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 https://godbolt.org/z/5dq7MnrEx

Cyph0n 3y ago

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