make an integer even

Question

Sometimes I need to be sure that some integer is even. As such I could use the following code:

int number = /* magic initialization here */;

// make sure the number is even
if ( number % 2 != 0 ) {
    number--;
}

but that does not seem to be very efficient the most efficient way to do it, so I could do the following:

int number = /* magic initialization here */;

// make sure the number is even
number &= ~1;

but (besides not being readable) I am not sure that solution is completely portable.

• Which solution do you think is best?
• Is the second solution completely portable?
• Is the second solution considerably faster that the first?
• What other solutions do you know for this problem?
• What if I do this inside an inline method? It should (theoretically) be as fast as these solutions and readability should no longer be an issue, does that make the second solution more viable?

note: This code is supposed to only work with positive integers but having a solution that also works with negative numbers would be a plus.

Answer 1

Personally, I'd go with an inline helper function.

inline int make_even(int n)
{
    return n - n % 2;
}

// ....

int m = make_even(n);

Answer 2

Before accepting an answer I will make my own that tries to summarize and complete some of the information found here:

Four possible methods where described (and some small variations of these).

1. if (number % 2 != 0) { number--; }
2. number&= ~1
3. number = number - (number % 2);
4. number = (number / 2) * 2;

Before proceeding any further let me clarify something: The expected gain for using any of these methods is minimal, even if we could prove that one method is 200% faster than the others the worst one is so fast that the only way to have visible gain in speed would be if this method was called many times in a CPU bound application. As such this is more of an exercise for fun than a real optimization.

Analysis

Readability

As far as readability goes I would rank method 1 as the most readable, method 4 as the second best and method 2 as the worse. People are free to disagree but I ranked them like this because:

1. In method 1 it is as explicit as possible that if the number is odd you want to subtract from it making it even.
2. Method 4 is also very much explicit but I ranked it second because at first glance you might think it is doing nothing, and only a fraction of a second latter you're like "Oh... Integer division.".
3. Method 2 and 3 are almost equivalent in terms of readability, but many people are not used to bitwise operations and as such I ranked method 2 as the worse.

With that in mind I would add that it is generally accepted that the best way to implement this is using an inline function, and none of the options is that unreadable, readability is not really an issue (direct uses in the code are explicit and clear and reading the method will never be that hard).

If you don't want to use an inline method I would recommend that you only use method 1 or method 4.

Compatibility issues

Underflow

It has been mentioned that method 1 may underflow, depending on the way the processor represents integers. Just to be sure you can add the following STATIC_ASSERT when using method 1.

STATIC_ASSERT(INT_MIN % 2 == 0, make_even_may_underflow);

As for method 3, even when INT_MIN is not even it may not underflow depending on whether the result has the same sign of the divisor or the dividend. Having the same sign of the divisor never underflows because INT_MIN - (-1) is closer to 0. Add the following STATIC_ASSERT just to be sure:

STATIC_ASSERT(INT_MIN % 2 == 0 || -1 % 2 < 0, make_even_may_underflow);

Of course you can still use these methods when the STATIC_ASSERT fails since it would only be a problem when you pass INT_MIN to your make_even method, but I would STRONGLY advice against it.

(Un)supported bit representations

When using method 2 you should make sure your compiler bit representation behaves as expected:

STATIC_ASSERT( (1 & ~1) == 0, unsupported_bit_representation);

// two's complement OR sign-and-magnitude.
STATIC_ASSERT( (-3 & ~1) == -4 || (-3 & ~1) == -2 , unsupported_bit_representation); 

Speed

I also did some naive speed tests using the Unix time utility. I ran every different method (and its variations) 4 times and recorded the results, since the results didn't vary much I didn't find necessary to run more tests.

The obtained results show method 4 and method 2 as the fastest of them all.

Conclusion

According to the provided information, I would recommend using method 4. Its readable, I am not aware of any compatibility issues and performs great.

I hope you enjoy this answer and use the information contained here to make your own informed choice. :)

---

The source code is available if you want to check my results. Please note that the tests where compiled using g++ and run in Mac OS X. Different platforms and compilers may give different results.

Answer 3

I would use the second solution. In any binary representation, regardless of the number of bits, big-endian vs. little-endian, or other architecture differences, that operation will have the effect of setting the lowest bit to zero. It's fast and completely portable. The intent of the code can be explained via comments, if you meet any poor C programmers who can't figure out what it means.

Answer 4

int even_number = (number / 2) * 2;

This should work regardless architecture as long as optimizer is not going in the way (it shouldn't but who knows).

Answer 5

The &= solution looks best to me. If you want to make it more portable and more readable:

const int MakeEven = -2;

int number = /* magic initialization here */
// Make sure number is even
number &= MakeEven;

The second solution should be considerably faster than the first. Is it completely portable? Most likely, although there's probably some computer somewhere that does math differently.

This should work for positive and negative integers.

Answer 6

Use your second solution as inline function and put static assert into implementation of it to document and test that it works on platform that it is compiled on.

 BOOST_STATIC_ASSERT( (1 & ~1) == 0 );

 BOOST_STATIC_ASSERT( (-1 & ~1) == -2 );

Answer 7

Your second solution only works if your sign representation is "two's complement" or "sign and magnitude". To do it in place I'd go with suszterpatt's variant, which should (almost) always work

number -= (number % 2);

You don't know for sure in which direction this will "round" for negative values, so in extreme cases you might have an underflow.

Answer 8

even_integer = (any_integer >> 1) << 1;

This solution achieves the goal in the most performant way compared to the other suggested solutions. In general, bitwise shift is the cheapest possible operation. Some compilers generate the same assembly for "number = (number / 2) * 2" as well but that is not guaranteed on all target platforms and programming languages.

Answer 9

The following approach is simple and requires no multiplication or division.

number = number & ~1;

or

number = (number + 1) & ~1;