News for hackers. Stuff that matters.
Re:Finding the average of two unsigned integers without over... by justinpombrio on Monday February 07, 2022 @07:42PM (#30253588)
Alternatively, a direct explanation:

a & b is the bits they have in common. If they both have a bit x, you should keep it, because the average of x and x is x.

a ^ b is the bits that only one of them have. You should halve these bits, because the average of x and 0 is x/2.

Re:Finding the average of two unsigned integers without over... by ziml77 on Monday February 07, 2022 @09:34PM (#30254300)
This explanation makes a ton more sense!
Re:Finding the average of two unsigned integers without over... by wildmanx on Tuesday February 08, 2022 @03:35AM (#30256120)
But it has lots of assumptions/prerequisites about taking the mean baked-in. It happens to work for this particular case, but in general you don't get far with such hand-wavy reasoning since you just get confused with which assumptions hold and which don't.

The original explanation was the actual SIMD approach, which is really cool. You can extend it right away to other problems.

Re:Finding the average of two unsigned integers without over... by ggrrhh_ta on Tuesday February 08, 2022 @07:41AM (#30257720)
The explanation seems to work even in base 10.

Let's do the average of 85 and 95. The leftmost digit of both is equal, so we leave it: X5 The "xor"/2 is the sum of the non equal digits divided by 2 (respecting their powers): (8+9)10 = (17)10 = 85 Now, we add them: 5 + 85 = 90 (which is the average of 85 and 95).

Let's take now 87 and 89: The rightmost digits are equal: 8X We do the 'xor'/2 for the left most: (7+9)/2 = 8 8X + 8 = 88

Let me know if there are some examples for which it would fail (I only spent a minute to test if the explanation extends to other bases).

Re:Finding the average of two unsigned integers without over... by remram on Tuesday February 08, 2022 @11:33AM (#30260489)
The average of 15 and 30 is not 22. The average of 51 and 03 is not 22.