There's this well-known identity [1] a + b = (a ^ b) + ((a & b) << 1). This is essentially how a parallel ripple carry adder works. So (a + b) / 2 = (a + b) >>

There's this well-known identity [1] a + b = (a ^ b) + ((a & b) << 1). This is essentially how a parallel ripple carry adder works. So (a + b) / 2 = (a + b) >> 1 = ((a ^ b) >> 1) + (a & b). [1] http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23 http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23