Would you use num%2 or num&1 to check if a number is even?

Question

Well, there are at least two low-level ways of determining whether a given number is even or not:

 1. if (num%2 == 0) { /* even */ } 
 2. if ((num&1) == 0) { /* even */ }

I consider the second option to be far more elegant and meaningful, and that's the one I usually use. But it is not only a matter of taste; The actual performance may vary: usually the bitwise operations (such as the logial-and here) are far more efficient than a mod (or div) operation. Of course, you may argue that some compilers will be able to optimize it anyway, and I agree...but some won't.

Another point is that the second one might be a little harder to comprehend for less experienced programmers. On that I'd answer that it will probably only benefit everybody if these programmers take that short time to understand statements of this kind.

What do you think?

The given two snippets are correct only if num is either an unsigned int, or a negative number with a two's complement representation. - As some comments righfuly state.

Answer 1

I code for readability first so my choice here is num % 2 == 0. This is far more clear than num & 1 == 0. I'll let the compiler worry about optimizing for me and only adjust if profiling shows this to be a bottleneck. Anything else is premature.

I consider the second option to be far more elegant and meaningful

I strongly disagree with this. A number is even because its congruency modulo two is zero, not because its binary representation ends with a certain bit. Binary representations are an implementation detail. Relying on implementation details is generally a code smell. As others have pointed out, testing the LSB fails on machines that use ones' complement representations.

Another point is that the second one might be a little harder to comprehend for less experienced programmers. On that I'd answer that it will probably only benefit everybody if these programmers take that short time to understand statements of this kind.

I disagree. We should all be coding to make our intent clearer. If we are testing for evenness the code should express that (and a comment should be unnecessary). Again, testing congruency modulo two more clearly expresses the intent of the code than checking the LSB.

And, more importantly, the details should be hidden away in an isEven method. So we should see if(isEven(someNumber)) { // details } and only see num % 2 == 0 once in the definition of isEven.

Answer 2

If you're going to say that some compilers won't optimise %2, then you should also note that some compilers use a ones' complement representation for signed integers. In that representation, &1 gives the wrong answer for negative numbers.

So what do you want - code which is slow on "some compilers", or code which is wrong on "some compilers"? Not necessarily the same compilers in each case, but both kinds are extremely rare.

Of course if num is of an unsigned type, or one of the C99 fixed-width integer types (int8_t and so on, which are required to be 2's complement), then this isn't an issue. In that case, I consider %2 to be more elegant and meaningful, and &1 to be a hack that might conceivably be necessary sometimes for performance. I think for example that CPython doesn't do this optimisation, and the same will be true of fully interpreted languages (although then the parsing overhead likely dwarfs the difference between the two machine instructions). I'd be a bit surprised to come across a C or C++ compiler that didn't do it where possible, though, because it's a no-brainer at the point of emitting instructions if not before.

In general, I would say that in C++ you are completely at the mercy of the compiler's ability to optimise. Standard containers and algorithms have n levels of indirection, most of which disappears when the compiler has finished inlining and optimising. A decent C++ compiler can handle arithmetic with constant values before breakfast, and a non-decent C++ compiler will produce rubbish code no matter what you do.

Answer 3

I define and use an "IsEven" function so I don't have to think about it, then I chose one method or the other and forget how I check if something is even.

Only nitpick/caveat is I'd just say that with the bitwise operation, you're assuming something about the representation of the numbers in binary, with modulo you are not. You are interpreting the number as a decimal value. This is pretty much guaranteed to work with integers. However consider that the modulo would work for a double, however the bitwise operation would not.

Answer 4

You conclusion about performance is based on the popular false premise.

For some reason you insist on translating the language operations into their "obvious" machine counterparts and make the performance conclusions based on that translation. In this particular case you concluded that a bitwise-and & operation of C++ language must be implemented by a bitwise-and machine operation, while a modulo % operation must somehow involve machine division, which is allegedly slower. Such approach is of very limited use, if any.

Firstly, I can't imagine a real-life C++ compiler that would interpret the language operations in such a "literal" way, i.e. by mapping them into the "equivalent" machine operations. Mostly because more often than one'd think the equivalent machine operations simply do not exist.

When it comes to such basic operations with an immediate constant as an operand, any self-respecting compiler will always immediately "understand" that both num & 1 and num % 2 for integral num do exactly the same thing, which will make the compiler generate absolutely identical code for both expressions. Naturally, the performance is going to be exactly the same.

BTW, this is not called "optimization". Optimization, by definition, is when the compiler decides to deviate from the standard behavior of abstract C++ machine in order to generate the more efficient code (preserving the observable behavior of the program). There's no deviation in this case, meaning that there's no optimization.

Moreover, it is quite possible that on the given machine the most optimal way to implement both is neither bitwise-and nor division, but some other dedicated machine-specific instruction. On top of that, it is quite possible that there won't be any need for any instruction at all, since even-ness/odd-ness of a specific value might be exposed "for free" through the processor status flags or something like that.

In other words, the efficiency argument is invalid.

Secondly, to return to the original question, the more preferable way to determine the even-ness/odd-ness of a value is certainly the num % 2 approach, since it implements the required check literally ("by definition"), and clearly expresses the fact that the check is purely mathematical. I.e. it makes clear that we care about the property of a number, not about the property of its representation (as would be in case of num & 1 variant).

The num & 1 variant should be reserved for situations when you want access to the bits of value representation of a number. Using this code for even-ness/odd-ness check is a highly questionable practice.

Answer 5

It's been mentioned a number of times that any modern compiler would create the same assembly for both options. This reminded me of the LLVM demo page that I saw somewhere the other day, so I figured I'd give it a go. I know this isn't much more than anecdotal, but it does confirm what we'd expect: x%2 and x&1 are implemented identically.

I also tried compiling both of these with gcc-4.2.1 (gcc -S foo.c) and the resultant assembly is identical (and pasted at the bottom of this answer).

Program the first:

int main(int argc, char **argv) {
  return (argc%2==0) ? 0 : 1;
}

Result:

; ModuleID = '/tmp/webcompile/_27244_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

Program the second:

int main(int argc, char **argv) {
  return ((argc&1)==0) ? 0 : 1;
}

Result:

; ModuleID = '/tmp/webcompile/_27375_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

GCC output:

.text
.globl _main
_main:
LFB2:
  pushq %rbp
LCFI0:
  movq  %rsp, %rbp
LCFI1:
  movl  %edi, -4(%rbp)
  movq  %rsi, -16(%rbp)
  movl  -4(%rbp), %eax
  andl  $1, %eax
  testl %eax, %eax
  setne %al
  movzbl  %al, %eax
  leave
  ret
LFE2:
  .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support
EH_frame1:
  .set L$set$0,LECIE1-LSCIE1
  .long L$set$0
LSCIE1:
  .long 0x0
  .byte 0x1
  .ascii "zR\0"
  .byte 0x1
  .byte 0x78
  .byte 0x10
  .byte 0x1
  .byte 0x10
  .byte 0xc
  .byte 0x7
  .byte 0x8
  .byte 0x90
  .byte 0x1
  .align 3
LECIE1:
.globl _main.eh
_main.eh:
LSFDE1:
  .set L$set$1,LEFDE1-LASFDE1
  .long L$set$1
ASFDE1:
  .long LASFDE1-EH_frame1
  .quad LFB2-.
  .set L$set$2,LFE2-LFB2
  .quad L$set$2
  .byte 0x0
  .byte 0x4
  .set L$set$3,LCFI0-LFB2
  .long L$set$3
  .byte 0xe
  .byte 0x10
  .byte 0x86
  .byte 0x2
  .byte 0x4
  .set L$set$4,LCFI1-LCFI0
  .long L$set$4
  .byte 0xd
  .byte 0x6
  .align 3
LEFDE1:
  .subsections_via_symbols

Answer 6

It all depends on context. I actually prefer the &1 approach myself if it's a low level, system context. In many of these kinds of contexts, "is even" basically means has low bit zero to me, rather than is divisible by two.

HOWEVER: Your one liner has a bug.

You must go

if( (x&1) == 0 )

not

if( x&1 == 0 )

The latter ANDs x with 1==0, ie it ANDs x with 0, yielding 0, which always evaluates as false of course.

So if you did it exactly as you suggest, all numbers are odd!

Answer 7

Any modern compiler will optimise away the modulo operation, so speed is not a concern.

I'd say using modulo would make things easier to understand, but creating an is_even function that uses the x & 1 method gives you the best of both worlds.

Answer 8

They're both pretty intuitive.

I'd give a slight edge to num % 2 == 0, but I really don't have a preference. Certainly as far as performance goes, it's probably a micro-optimization, so I wouldn't worry about it.

Answer 9

I spent years insisting that any reasonable compiler worth the space it consumes on disk would optimize num % 2 == 0 to num & 1 == 0. Then, analyzing disassembly for a different reason, I had a chance to actually verify my assumption.

It turns out, I was wrong. Microsoft Visual Studio, all the way up through version 2013, generates the following object code for num % 2 == 0:

    and ecx, -2147483647        ; the parameter was passed in ECX
    jns SHORT $IsEven
    dec ecx
    or  ecx, -2
    inc ecx
$IsEven:
    neg ecx
    sbb ecx, ecx
    lea eax, DWORD PTR [ecx+1]

Yes, indeed. This is in Release mode, with all optimizations enabled. You get virtually equivalent results whether building for x86 or x64. You probably won't believe me; I barely believed it myself.

It does essentially what you would expect for num & 1 == 0:

not  eax                        ; the parameter was passed in EAX
and  eax, 1

By way of comparison, GCC (as far back as v4.4) and Clang (as far back as v3.2) do what one would expect, generating identical object code for both variants. However, according to Matt Godbolt's interactive compiler, ICC 13.0.1 also defies my expectations.

Sure, these compilers are not wrong. It's not a bug. There are plenty of technical reasons (as adequately pointed out in the other answers) why these two snippets of code are not identical. And there's certainly a "premature optimization is evil" argument to be made here. Granted, there's a reason it took me years to notice this, and even then I only stumbled onto it by mistake.

But, like Doug T. said, it is probably best to define an IsEven function in your library somewhere that gets all of these little details correct so that you never have to think about them again—and keep your code readable. If you regularly target MSVC, perhaps you'll define this function as I've done:

bool IsEven(int value)
{
    const bool result = (num & 1) == 0;
    assert(result == ((num % 2) == 0));
    return result;   
}

Answer 10

Both approaches are not obvious especially to someone who is new to programming. You should define an inline function with a descriptive name. The approach you use in it won't matter (micro optimizations most likely won't make your program faster in a noticeable way).

Anyway, I believe 2) is much faster as it doesn't require a division.

Answer 11

I don't think the modulo makes things more readable. Both make sense, and both versions are correct. And computers store numbers in binary, so you can just use the binary version.

The compiler may replace the modulo version with an efficient version. But that sounds like an excuse for prefering the modulo.

And readability in this very special case is the same for both versions. A reader that is new to programming may not even know that you can use modulo 2 to determine the even-ness of a number. The reader has to deduce it. He may not even know the modulo operator!

When deducing the meaning behind the statements, it could even be easier to read the binary version:

if( ( num & 1 ) == 0 ) { /* even */ }
if( ( 00010111b & 1 ) == 0 ) { /* even */ }
if( ( 00010110b & 1 ) == 0 ) { /* odd */ }

(I used the "b" suffix for clarification only, its not C/C++)

With the modulo version, you have to double-check how the operation is defined in its details (e.g. check documentation to make sure that 0 % 2 is what you expect).

The binary AND is simpler and there are no ambiguities!

Only the operator precedence may be a pitfall with binary operators. But it should not be a reason to avoid them (some day even new programmers will need them anyway).

Answer 12

At this point, I may be just adding to the noise, but as far as readability goes, the modulo option makes more sense. If your code is not readable, it's practically useless.

Also, unless this is code to be run on a system that's really strapped for resources (I'm thinking microcontroller), don't try to optimize for the compiler's optimizer.