4 ms·
int mid(int x, int y) { return (x/2 + y/2) + (1 & x & y); } would be a more readable solution edit: Actually, this fails on mid(INT_MIN, INT_MAX) and po
by pksadiq 4y ago
int mid(int x, int y) {
return (x/2 + y/2) + (1 & x & y);
}
would be a more readable solution
edit: Actually, this fails on mid(INT_MIN, INT_MAX) and possibly other mixed sign values (returns: -1, expected: 0 (or -1 is okay?), where the precise answer is -0.5)
more edit: The C standard says: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (This is often called ‘‘truncation toward zero’’).
So -1/2 should be 0.
- tiffanyh 4y agoUsing the midpoint function is the most readable. https://en.cppreference.com/w/cpp/numeric/midpoint https://en.cppreference.com/w/cpp/numeric/midpoint Though it's odd this allows overflow.
- abainbridge 4y agostd::midpoint also seems to yield less efficient code with g++12 targeting x86-64: https://godbolt.org/z/j695ce98Y https://godbolt.org/z/j695ce98Y
- Lockal 4y agostd::midpoint does different thing in terms of rounding, therefore comparison is not fair.
- abainbridge 4y agoPossibly true, but it yields less efficient code in GCC 12 for x86-64. https://godbolt.org/z/oafPrb4K8 https://godbolt.org/z/oafPrb4K8
- bonzini 4y agoBecause it's also wrong! / rounds towards zero, while summing a&b&1 requires the division to round towards negative infinity.
- nwellnhof 4y agoFor signed ints, try (x >> 1) + (y >> 1) + (x & y & 1) This rounds toward negative infinity. Also (x >> 1) + (y >> 1) + ((x | y) & 1) // Rounds toward +Inf (x >> 1) + (y >> 1) + (x & 1) // Rounds up if x is odd (x >> 1) + (y >> 1) + (y & 1) // Rounds up if y is odd I'd be curious if there's a bit-twiddling trick for rounding toward x or y.