For doing a right shift of unsigned values with rounding, the following functions work for me:
unsigned rshift_round_down(unsigned x, unsigned a) {
return x >> a;
}
unsigned rshift_round_up(unsigned x, unsigned a) {
return (x >> a) + ((x & ((1U << a) - 1)) != 0);
}
unsigned rshift_round_halfway(unsigned x, unsigned a) {
if (a == 0) return x;
return (x >> a) + ((x >> (a - 1)) & 1);
}
unsigned rshift_round_towards_even(unsigned x, unsigned a) {
if (a == 0) return x;
return (x >> a) + ((x >> (a - ((x & ((1U << a) - 1)) != 1 << (a - 1)))) & 1);
}
Is there a simpler but equivalent implementation of rshift_round_towards_even?
Please note that the allowed values for a are these: 0 <= a && a < sizeof(unsigned) * 8. Thus these functions don't have to work for very large values of a.
Example inputs and outputs:
This is slightly simpler in terms of number of operators (10 vs 12, counting the == in the if condition in the question):
unsigned rshift_round_towards_even(unsigned x, unsigned a) {
return (x && a) ? ((((x - !((x >> a) & 1)) >> (a - 1)) + 1) >> 1) : x;
}
Yes, one of the operators is the ternary operator, but then the question (now) has a full-blown if statement that this does not, and that I also haven't represented in the count.
The logic goes like this:
if either x or a is zero then the result is x. This is special-cased via a ternary operation to avoid underflows in the main expression.
the first alternative of the ternary is a modified version of this shift with round-half-up:
((x >> (a - 1)) + 1) >> 1
which itself involves an integer variation on floor(f + 0.5). To convert that into round-to-nearest, half-to-even, 1 is subtracted from the original x when the half-to-even part requires rounding down, which is when !((x >> a) & 1) evaluates to 1. That changes the result of the round-to nearest only when the original is at exactly the halfway point.
Addendum
As @IanAbbott alluded to in comments, the above has undefined behavior when a is greater than or equal to the number of value bits in type unsigned int, per explicit provision of the language specifications for the >> operator. The same applies to the alternative given in the question, so it may not be an issue, but if such inputs are contemplated, and if the target implementation(s) cannot be relied upon to produce the wanted behavior for such operands, then additional effort is required.
If a version safe for large a is required, then I might implement it as a separate wrapper, maybe something like:
// Assumes no padding bits in unsigned int:
#define UINT_BITS (sizeof(unsigned int) * CHAR_BIT)
unsigned rshift_round_towards_even_safe(unsigned x, unsigned a) {
if (a < UINT_BITS) return rshift_round_towards_even(x, a);
if (a > UINT_BITS) return 0;
return (x > ((UINT_MAX >> 1) + 1));
}
That could be restructured as a single expression via ternary operators, if desired, and the expression from rshift_round_towards_even could be inlined into it as well, if desired.