If I want to round an unsigned integer to the closest smaller or equal even integer, can I divide by 2 then multiply by 2?

Question

For example :

f(8)=8
f(9)=8

Can I do x = x/2*2; ? Is there a risk that the compiler will optimize away such expression ?

Answer 1

The compiler is allowed to make any optimisiations it likes so long as it does not introduce any side effects into the program. In your case it can't cancel the '2's as then the expression will have a different value for odd numbers.

x / 2 * 2 is evaluated strictly as (x / 2) * 2, and x / 2 is performed in integer arithmetic if x is an integral type.

This, in fact, is an idiomatic rounding technique.

Answer 2

Since you specified the integers are unsigned, you can do it with a simple mask:

x & (~1u)

Which will set the LSB to zero, thus producing the immediate even number that is no larger than x. That is, if x has a type that is no wider than an unsigned int.

You can of course force the 1 to be of the same type as a wider x, like this:

x & ~((x & 1u) | 1u)

But at this point, you really ought to look at this approach as an exercise in obfuscation, and accept Bathsheba's answer.

---

I of course forgot about the standard library. If you include stdint.h (or cstdint, as you should in C++ code). You can let the implementation take care of the details:

uintmax_t const lsb = 1;
x & ~lsb;

or

x & ~UINTMAX_C(1)

Answer 3

C and C++ generally use the "as if" rule in optimization. The computation result must be as if the compiler didn't optimize your code.

In this case, 9/2*2=8. The compiler may use any method to achieve the result 8. This includes bitmasks, bit shifts, or any CPU-specific hack that produces the same results (x86 has quite a few tricks that rely on the fact that it doesn't differentiate between pointers and integers, unlike C and C++).

Answer 4

You can write x / 2 * 2 and the compiler will produce very efficient code to clear the least significant bit if x has an unsigned type.

Conversely, you could write:

x = x & ~1;

Or probably less readably:

x = x & -2;

Or even

x = (x >> 1) << 1;

Or this too:

x = x - (x & 1);

Or this last one, suggested by supercat, that works for positive values of all integer types and representations:

x = (x | 1) ^ 1;

All of the above proposals work correctly for all unsigned integer types on 2's complement architectures. Whether the compiler will produce optimal code is a question of configuration and quality of implementation.

Note however that x & (~1u) does not work if the type of x is larger than unsigned int. This is a counter-intuitive pitfall. If you insist on using an unsigned constant, you must write x & ~(uintmax_t)1 as even x & ~1ULL would fail if x has a larger type than unsigned long long. To make matters worse, many platforms now have integer types larger than uintmax_t, such as __uint128_t.

Here is a little benchmark:

typedef unsigned int T;

T test1(T x) {
    return x / 2 * 2;
}

T test2(T x) {
    return x & ~1;
}

T test3(T x) {
    return x & -2;
}

T test4(T x) {
    return (x >> 1) << 1;
}

T test5(T x) {
    return x - (x & 1);
}

T test6(T x) {  // suggested by supercat
    return (x | 1) ^ 1;
}

T test7(T x) {  // suggested by Mehrdad
    return ~(~x | 1);
}

T test1u(T x) {
    return x & ~1u;
}

As suggested by Ruslan, testing on Godbolt's Compiler Explorer shows that for all the above alternatives gcc -O1 produces the same exact code for unsigned int, but changing the type T to unsigned long long shows differing code for test1u.

Answer 5

If your values are of any unsigned type as you say, the easiest is

x & -2;

The wonders of unsigned arithmetic make it that -2 is converted to the type of x, and has a bit pattern that has all ones, but for the least significant bit which is 0.

In contrary to some of the other proposed solutions, this should work with any unsigned integer type that is at least as wide as unsigned. (And you shouldn't do arithmetic with narrower types, anyhow.)

Extra bonus, as remarked by supercat, this only uses conversion of a signed type to an unsigned type. This is well-defined by the standard as being modulo arithmetic. So the result is always UTYPE_MAX-1 for UTYPE the unsigned type of x. In particular, it is independent of the sign representation of the platform for signed types.

Answer 6

One option that I'm surprised hasn't been mentioned so far is to use the modulo operator. I would argue this represents your intent at least as well as your original snippet, and perhaps even better.

x = x - x % 2

As others have said, the compiler's optimiser will deal with any reasonable expression equivalently, so worry about what's clearer rather than what you think is fastest. All the bit-tweaking answers are interesting, but you should definitely not use any of them in place of arithmetic operators (assuming the motivation is arithmetic rather than bit tweaking).

Answer 7

just use following:

template<class T>
inline T f(T v)
{
    return v & (~static_cast<T>(1));
}

Do not afraid that this is function, compiler should finally optimize this into just v & (~1) with appropriate type of 1.