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

Question

For example:

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

Is it possible to do x = x/2*2; ? Is there a risk that the compiler optimizes this expression?

Answer 1

The compiler allows you to make any optimizations that he likes, until he introduces any side effects into the program. In your case, it cannot cancel "2", as then the expression will have a different value for odd numbers.

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

This is essentially an idiomatic rounding method.

Answer 2

Since you specified unsigned integers, you can do this with a simple mask:

 x & (~1u) 

Which sets the LSB to zero, thereby creating an immediate even number not exceeding x . That is, if x is of type that is not wider than unsigned int .

You can, of course, force 1 be of the same type as the wider x , for example:

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

But at this point you really should look at this approach as an exercise in obfuscation and accept the answer from Bathsheba.

---

Of course, I forgot about the standard library. If you include stdint.h (or cstdint , as 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 ++ usually use the “as if” rule in optimization. The result of the calculation should be as if the compiler had not optimized your code.

In this case, 9/2*2=8 . The compiler can use any method to achieve result 8. This includes bitmasks, bit shifts, or any processor-dependent hacker that produces the same results (x86 has quite a few tricks that rely on the fact that they do not distinguish between pointers and integers, unlike C and C ++).

Answer 4

You can write x / 2 * 2 , and the compiler will create very efficient code to clear the least significant bit if x is of unsigned type.

Conversely, you can write:

 x = x & ~1; 

Or perhaps less readable:

 x = x & -2; 

Or even

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

Or this too:

 x = x - (x & 1); 

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

 x = (x | 1) ^ 1; 

All the above sentences work correctly for all unsigned integer types on 2 additional architectures. Whether the compiler will create the optimal code is a matter of configuration and implementation quality.

Note that x & (~1u) does not work if the type of x greater than unsigned int . This is a counter-intuitive trap. If you insist on using the unsigned constant, you should write x & ~(uintmax_t)1 , since even x & ~1ULL will fail if x is of a larger type than unsigned long long . Even worse, many platforms now have integer types larger than uintmax_t , such as __uint128_t .

Here is a small guideline:

 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 Ruslan showed, testing Godbolt Compiler Explorer shows that for all of the above alternatives to gcc -O1 get the same exact code for unsigned int , but changing type T to unsigned long long shows a different code for test1u .

Answer 5

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

 x & -2; 

The wonders of unsigned arithmetic make -2 convert to type x and have a bit pattern that has everything, but for the least significant bit, which is 0 .

Unlike some other proposed solutions, this should work with any unsigned integer type that at least has a width than unsigned . (And you should not do arithmetic with narrower types.)

An added bonus, as noted by supercat, is only converting a signed type to an unsigned type. This is standardly defined modulo arithmetic. Thus, the result is always UTYPE_MAX-1 for a UTYPE unsigned type x . In particular, it does not depend on the symbolic representation of the platform for signed types.

Answer 6

One option that surprises me, until it is mentioned, is to use the modulo operator. I would say that it means your intention, at least as much as your original fragment, and perhaps even better.

 x = x - x % 2 

As others have argued, the compiler optimizer will deal with any reasonable expression equivalently, so be careful what is clearer and not what you consider the fastest. All the answers to the little things are interesting, but you should not use any of them instead of arithmetic operators (assuming that motivation is arithmetic, not bit tuning).

Answer 7

just use the following:

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

Do not be afraid that this is a function, the compiler should finally optimize this v and (~ 1) with the corresponding type 1.