1: In most C-like languages you need extra parentheses because the plus operator has higher precedence than the shift operator: (a & b) + ((a ^ b) >> 1)
(Mentioning this in case someone tried to copy/paste the expression to their favorite language and got confused why it didn't work, because they didn't realize Go has a unique operator precedence table.)
2: The blog post suggests the overflow problem is limited to signed integers, but actually unsigned integers are just as problematic. Consider (32768 + 32768) / 2 = 0 in 16-bit math. And the trick works equally well for those.
3: Note that integer division rounds towards 0 in most languages, including Java and Go, so the bitwise trick is not fully equivalent to (a + b) / 2 when the result is negative, even in the absence of overflow. For example, (-10 + 5) / 2 = -2, but the bit trick gives -3. However, sometimes rounding down is okay too, or even preferable.
A few comments on the integer averaging trick:
1: In most C-like languages you need extra parentheses because the plus operator has higher precedence than the shift operator: (a & b) + ((a ^ b) >> 1)
(Mentioning this in case someone tried to copy/paste the expression to their favorite language and got confused why it didn't work, because they didn't realize Go has a unique operator precedence table.)
2: The blog post suggests the overflow problem is limited to signed integers, but actually unsigned integers are just as problematic. Consider (32768 + 32768) / 2 = 0 in 16-bit math. And the trick works equally well for those.
3: Note that integer division rounds towards 0 in most languages, including Java and Go, so the bitwise trick is not fully equivalent to (a + b) / 2 when the result is negative, even in the absence of overflow. For example, (-10 + 5) / 2 = -2, but the bit trick gives -3. However, sometimes rounding down is okay too, or even preferable.