* rcs@xmission.com <rcs@xmission.com> [Jun 03. 2016 08:44]:
[...] Probably we can do something with (a&b) + (a|b) = a+b, and a+b = (a^b) + 2(a&b). Maybe v(a+b) <= v(a^b) + v(a&b).
From a+b = (a^b) + 2(a&b) we get (a+b)/2 = (a^b)/2 + (a&b) so
static inline ulong average(ulong x, ulong y) // Return floor( (x+y)/2 ) // Result is correct even if (x+y) wouldn't fit into a ulong // Use: x+y == ((x&y)<<1) + (x^y) // that is: sum == carries + sum_without_carries { return (x & y) + ((x ^ y) >> 1); // return y + ((x-y)>>1); // works if x>=y } Similarly ulong ceil_average(ulong x, ulong y) // Return ceil( (x+y)/2 ) // Result is correct even if (x+y) wouldn't fit into a ulong // Use: x+y == ((x|y)<<1) - (x^y) // ceil_average(x,y) == average(x,y) + ((x^y)&1)) { return (x | y) - ((x ^ y) >> 1); } Best regards, jj
Rich
[...]