Does gcc (or any other compiler) change (n%2==1) for (n&1==1)?

Question

To test if a number is odd or even, It is my understanding that a test using

(n%2==1)

Is the same thing as

(n&1==1)

I assume the first test is faster (please correct me if I'm wrong), but does any compiler recognize this and "correct" it? Does this makes any difference in performance?

I can't speak with confidence here because I've never tried to look into this, but my instinct tells me, "No." The reason is that the compiler doesn't "know" that you want to find odd numbers, it just knows that you want the remainder (modulus). — David Hoelzer, May 14 '15 at 00:01
@DavidHoelzer http://tech.michaelaltfield.net/2009/12/02/gcc-optimizations-for-arithmetic-operations-using-bit-shifts/ would claim differently, I haven't tried it out myself though. I'd be a little bit surprised if any major C/C++ compilers *didn't* do this on the highest optimization settings. — Commander Coriander Salamander, May 14 '15 at 00:09
I'm interested in knowing this as well. I would hope it optimizes something like this, similar to multiplying an integer by 2. — Epic Byte, May 14 '15 at 00:10
Some made comments about this here http://stackoverflow.com/questions/29110752/what-is-the-correct-way-to-obtain-1n , from them I understand that the they should be *optimized* to the same code. — alfC, May 14 '15 at 08:30

score 0 · Accepted Answer · answered May 14 '15 at 00:18

0

void main()
{
    int n = 5;
    int i = n & 1;
}
    call    __main
    movl    $5, -4(%rbp)
    movl    -4(%rbp), %eax
    andl    $1, %eax
    movl    %eax, -8(%rbp)
    addq    $48, %rsp
    popq    %rbp
    ret

void main()
{
    int n = 5;
    int i = n % 2;
}
    call    __main
    movl    $5, -4(%rbp)
    movl    -4(%rbp), %eax
    cltd
    shrl    $31, %edx
    addl    %edx, %eax
    andl    $1, %eax
    subl    %edx, %eax
    movl    %eax, -8(%rbp)
    addq    $48, %rsp
    popq    %rbp
    ret

Tried with gcc.exe (GCC) 4.9.2 using -S -O0
So it seams that & 1 to check parity is slightly better.

answered May 14 '15 at 00:18

Zereges

5,139
1
25
49

Looks good for my gut instinct. What does it do at highest optimization? – David Hoelzer May 14 '15 at 00:23
1

You shouldn't use `void main()`, and with enough optimization, the whole body of the function can be optimized out. You'd do better with `return i;`, but since the compiler can compute the answer at compile time, that won't help either. So, make sure your calculation depends on user input, such as a command line argument: `int main(int argc, char **argv) { int n = (argc > 1) ? atoi(argv[1]) : 5; int i = n & 1; return i; }` or equivalent. – Jonathan Leffler May 14 '15 at 00:30
1

@zerges How a compiler optimizes code when you don't enable optimization is usually not that interesting. – nos May 14 '15 at 00:33

fghj · Answer 2 · 2015-05-14T03:00:56.853

Actually
(n%2==1) is not the same as (n&1==1) if type of n is signed int, so the compiler code(gcc 5.1, -Ofast, 64bit):

int f(int n)
{
    return (n % 2) == 1;
0:   89 f8                   mov    %edi,%eax
2:   c1 e8 1f                shr    $0x1f,%eax
5:   01 c7                   add    %eax,%edi
7:   83 e7 01                and    $0x1,%edi
a:   29 c7                   sub    %eax,%edi
c:   31 c0                   xor    %eax,%eax
e:   83 ff 01                cmp    $0x1,%edi
11:   0f 94 c0                sete   %al
}
14:   c3                      retq

So main part looks like(pseudo code):

 uint64_t edi = eax;
 eax >>= 0x1f;
 edi += eax;
 edi &= 1;
 edi -= eax;

But if type of n is "unsigned int" all looks great(gcc 5.1, -Ofast):

0000000000000000 <f>:
unsigned char f(unsigned int n)
{
    return (n % 2) == 1;
0:   83 e7 01                and    $0x1,%edi
}
3:   89 f8                   mov    %edi,%eax
5:   c3                      retq

Does gcc (or any other compiler) change (n%2==1) for (n&1==1)?

2 Answers2