What is the most efficient way to detect even numbers in Java?

Question

What would be the most efficient manner to determine that a number is even using Java, and why?

Would it be using modulo or subtraction, or some other manner that I haven't actually thought of?

One imagines I could determine this doing a simple test class - and I can - but that really wouldn't explain why, would it?

I'm not doing some crazy-pants performance tuning for some lofty goal of processing that many items faster. But I was curious if one method should be preferred over the other as common practice. In the same way we wouldn't use & in place of &&, why use % when we can use &?

The only thing we know about even numbers is that they left 0 when divided by two, isn't it? — A-SM, Jun 06 '13 at 18:15
Im curious: is this for a real application? I can't imagine one where you need to optimize it at this level. I usually let the compiler do its magic, and then measure. — tilpner, Jun 06 '13 at 18:17
You'll find it hard to do much better than %. Of course all you can really do is profile. More important than that, though, is that chances are you'll be spending more time pulling from memory than anything you're going to do with the actual mod, so I wouldn't get too hung up. — Joel, Jun 06 '13 at 18:18
TLDR -- don't worry about it until you've determined this is a choke point in your app. — Joel, Jun 06 '13 at 18:18
On my machine, both methods from PSR take ~2.9 nanoseconds. Don't optimize. If it proves too slow, you can again take a look at it. If you need more speed, check if you can do less checks! — tilpner, Jun 06 '13 at 18:25
see here http://strangelights.com/blog/archive/2011/08/24/modulus-amp-integer-division-are-ldquoslowrdquo.aspx — PSR, Jun 06 '13 at 18:30
@StackOverflowException: How did you check that? On my machine the modulo version takes almost twice as long as the bitwise and version... See my benchmark below. — jlordo, Jun 06 '13 at 19:02
@StackOverflowException not, not for a real problem. I was just curious as to what - or if, really - there was a most effective method to implement. Instead of blindly doing mod 2, when, say, & 1 would be faster - a lot or a little. — bharal, Jun 06 '13 at 19:29
@PSR Not sure why you link that blog: it is F# and the results are oviously wrong (good processor run at 3 or 4 GHz meaning that even an operation that takes half a cycle needs at least 0.1 nanosecond). The first comment explains why the methodology is flawed. — assylias, Jun 06 '13 at 21:33
Not really a duplicate, considering this is asking for the optimal method, not just any method. — arkon, Aug 13 '14 at 18:44

assylias · Accepted Answer · 2015-03-02T10:22:30.847

If you check the assembly generated by hotspot 7 of these two methods:

public static boolean isEvenBit(int i) {
    return (i & 1) == 0;
}
public static boolean isEvenMod(int i) {
    return i % 2 == 0;
}

you will see that although the mod is optimised and basically does a bitwise and but it has a few extra instructions because the two operations are not strictly equivalent*. Other JVMs might optimise it differently. The assembly is posted below for reference.

I also ran a micro benchmark which confirms our observation: isEventBit is marginally faster (but both run in about 2 nanoseconds so probably won't have much of an inmpact on a typical program as a whole):

Benchmark                     Mode  Samples  Score   Error  Units
c.a.p.SO16969220.isEvenBit    avgt       10  1.869 ± 0.069  ns/op
c.a.p.SO16969220.isEvenMod    avgt       10  2.554 ± 0.142  ns/op

isEvenBit

  # {method} 'isEvenBit' '(I)Z' in 'javaapplication4/Test1'
  # parm0:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000026c2580: sub    rsp,0x18
  0x00000000026c2587: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                ; - javaapplication4.Test1::isEvenBit@-1 (line 66)
  0x00000000026c258c: and    edx,0x1
  0x00000000026c258f: mov    eax,edx
  0x00000000026c2591: xor    eax,0x1            ;*ireturn
                                                ; - javaapplication4.Test1::isEvenBit@11 (line 66)
  0x00000000026c2594: add    rsp,0x10
  0x00000000026c2598: pop    rbp
  0x00000000026c2599: test   DWORD PTR [rip+0xfffffffffdb6da61],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x00000000026c259f: ret

isEvenMod

  # {method} 'isEvenMod' '(I)Z' in 'javaapplication4/Test1'
  # parm0:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000026c2780: sub    rsp,0x18
  0x00000000026c2787: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                ; - javaapplication4.Test1::isEvenMod@-1 (line 63)
  0x00000000026c278c: mov    r10d,edx
  0x00000000026c278f: and    r10d,0x1           ;*irem
                                                ; - javaapplication4.Test1::isEvenMod@2 (line 63)
  0x00000000026c2793: mov    r11d,r10d
  0x00000000026c2796: neg    r11d
  0x00000000026c2799: test   edx,edx
  0x00000000026c279b: cmovl  r10d,r11d
  0x00000000026c279f: test   r10d,r10d
  0x00000000026c27a2: setne  al
  0x00000000026c27a5: movzx  eax,al
  0x00000000026c27a8: xor    eax,0x1            ;*ireturn
                                                ; - javaapplication4.Test1::isEvenMod@11 (line 63)
  0x00000000026c27ab: add    rsp,0x10
  0x00000000026c27af: pop    rbp
  0x00000000026c27b0: test   DWORD PTR [rip+0xfffffffffdb6d84a],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x00000000026c27b6: ret

_{* as pointed out in the comments, % isn't really modulo; it's the remainder. So (i % 2) != (i & 1) if i < 0. The extra instructions in the isEvenMod code sets the sign of the result to the sign of i (and then just compares it to zero, so the effort is wasted).}

One reason for extra instructions is to check if a division by 0 is happening. — jlordo, Jun 06 '13 at 19:08
because 0 isn't even technically, i suppose. Or some weird math rulez, anyway. As it happens, 0 & 1 == 0 on my jvm - although i have no idea if that is a guaranteed thing. To be fair, I think for something like a 2-way load balancer (or really, any other time you care if something is odd or even), 0 can be counted as even, so this wouldn't be an issue. — bharal, Jun 06 '13 at 19:44
@OliCharlesworth: when you do `x % 0` there will be an `ArithmeticException, Division by 0`. So everytime the `%` operator occurs, this check will be done. — jlordo, Jun 06 '13 at 19:50
@jlordo: In the general case, I agree. But in this case the compiler clearly knows it's a `% 2` (otherwise it wouldn't have replaced it with a `& 1`!). — Oliver Charlesworth, Jun 06 '13 at 19:53
@OliCharlesworth: I was assuming because of the `test` operations in the bytecode. Seems I can't find an explanation for them in the The Java Virtual Machine Specification :( — jlordo, Jun 06 '13 at 20:03
@jlordo: FWIW, this looks like x86 assembly, not JVM bytecode... — Oliver Charlesworth, Jun 06 '13 at 20:09
@OliCharlesworth: good :) This seems to be what I thought it is in the first place: the zero-check, even though the compiler knows it's not a division by zero. — jlordo, Jun 06 '13 at 20:12
@jlordo Yes it is the assembly generated by the JIT. I have added a micro benchmark in a separate answer. I get results in line with yours. — assylias, Jun 06 '13 at 21:20
@OliCharlesworth @jlordo I don't think it's checking for a divide by zero. `%` isn't really modulo; it's the remainder. So `(i % 2) != (i & 1)` if `i` is negative. The extra instructions in the `%` code sets the sign of the result to the sign of `i`. (And then just compares it to zero, so the effort is wasted.) — maybeWeCouldStealAVan, Jun 07 '13 at 05:16

score 6 · Answer 2 · answered Jun 06 '13 at 21:19

Another approach is to run a micro benchmark and analyse the time taken by each variants. Here are the results:

Benchmark    Mean    Units    Time vs. baseline
baseline     10.330  nsec/op     0.000
bitAnd       12.075  nsec/op     1.745
bitShift     12.309  nsec/op     1.979
modulo       12.309  nsec/op     4.529

(the baseline is a method that just returns i == 0)

Conclusion:

i & 1 -----> takes about 1.75ns
i << 31 --> takes about 2.00ns
i % 2 -----> takes about 4.50ns

In other words, i % 2 is 2x slower than i & 1.

Notes: benchmark done with jmh. The baseline is high because I generate random numbers to make sure the method are not optimised away. Tests run on an i7 @ 2.8GHz (i.e. one cycle = 0.35ns) with hotspot 7.

jlordo · Answer 3 · 2013-06-06T19:21:12.030

4

TL;DR The bitwise and version seems to be the fastest. Benchmark and sample results below.

This should be faster than modulo, since it's only two steps that can be handled directly in hardware:

if ((n & 1) == 0) {
  // even number here
}

Here's a microbenchmark that proves my and aasylias' point:

    // setup
    int runs = 10;
    int numbers = 200000000; // 200.000.000
    int[] randomNumbers = new int[numbers];
    Random random = new Random();
    for (int i = 0; i < randomNumbers.length; i++) {
        randomNumbers[i] = random.nextInt();
    }
    int even = 0;
    int odd = 0;

    // bitwiseAnd
    long andStart = System.currentTimeMillis();
    for (int i = 0; i < runs; i++) {
        for (int number : randomNumbers) {
            if ((number & 1) == 0)
                even++;
            else
                odd++;
        }
    }
    long andDone = System.currentTimeMillis();
    long andDuration = andDone - andStart;

    System.out.println("Even " + even + ", odd " + odd);

    // reset variables
    even = 0;
    odd = 0;

    // Modulo
    long moduloStart = System.currentTimeMillis();
    for (int i = 0; i < runs; i++) {
        for (int number : randomNumbers) {
            if (number % 2 == 0)
                even++;
            else
                odd++;
        }
    }
    long moduloDone = System.currentTimeMillis();
    long moduloDuration = moduloDone - moduloStart;
    // Done with modulo

    System.out.println("Even " + even + ", odd " + odd);

    // reset variables
    even = 0;
    odd = 0;

    // Shift
    long shiftStart = System.currentTimeMillis();
    for (int i = 0; i < runs; i++) {
        for (int number : randomNumbers) {
            if ((number << 31) == 0)
                even++;
            else
                odd++;
        }
    }
    long shiftDone = System.currentTimeMillis();
    long shiftDuration = shiftDone - shiftStart;
    // Done with shift

    System.out.println("Even " + even + ", odd " + odd);

    System.out.println("Modulo Time    " + moduloDuration);
    System.out.println("Bitwise & Time " + andDuration);
    System.out.println("Shift Time     " + shiftDuration);

bitwise is always a bit faster (even if you switch the block of code with the modulo block). Sample output:

Even 999999530, odd 1000000470
Even 999999530, odd 1000000470
Even 999999530, odd 1000000470
Modulo Time    17731
Bitwise & Time 9672
Shift Time     10638

edited Jun 06 '13 at 19:21

answered Jun 06 '13 at 18:16

jlordo

37,490
6
58
83

4

Have you determined that it **is** faster in practice? – Oliver Charlesworth Jun 06 '13 at 18:23
@OliCharlesworth: No, I said _should_ ;) I think JIT can optimize `% 2` pretty well, but there's not much room for optimization here, since it can be translated directly into machine code on every platform I know of. – jlordo Jun 06 '13 at 18:25
I am writing a microbenchmark right now and will post it when done in a few minutes. – jlordo Jun 06 '13 at 18:33
Do it one million times for different proposals. Then - compare the results. – Alex Kreutznaer Jun 06 '13 at 18:42
@OliCharlesworth: Yes, I have determined that it **is** faster in practice (on my Win7 x64, AMD Dualcore Machine). – jlordo Jun 06 '13 at 18:47
Guys, can you check left shift too? I am just curious. – Alex Kreutznaer Jun 06 '13 at 18:49
@AlexKreutznaer: running the test right now. – jlordo Jun 06 '13 at 18:50
@AlexKreutznaer: Shift is **almost** as fast as `AND`. I'll upload the complete benchmark and results in a second. – jlordo Jun 06 '13 at 18:51
1

@AlexKreutznaer: Also, one million is a small number for such a microbenchmark. I chose two billion. – jlordo Jun 06 '13 at 18:59
I just said a random number to show it should be big enough. – Alex Kreutznaer Jun 06 '13 at 19:03
Im confused, you didnt do any warmup cycles? – tilpner Jun 06 '13 at 19:29
Testing three variants in the same method like you did does not produce consistent results and the first method tested generally incurs some overhead. – assylias Jun 06 '13 at 19:30
2

http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java – Oliver Charlesworth Jun 06 '13 at 19:38

score 3 · Answer 4 · answered Jun 06 '13 at 18:20

3

if ((i & 1) == 0) {
  // Even
}

answered Jun 06 '13 at 18:20

K Boden

626
4
6

Another posted answer shows that you are correct, but you've tendered this answer and given no justification about why it's the most optimal method, which makes it a poor answer. I'll be glad to retract the down vote if you complete the answer. – slugster Jun 07 '13 at 11:07

What is the most efficient way to detect even numbers in Java?

4 Answers4

isEvenBit

isEvenMod

Linked