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?

c++ c

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.

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;

x & ~UINTMAX_C(1)

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++).

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.

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?

Related

Recent Posts