整数求均值的几种方法

问题描述：

求均值最常用的方法是将两数相加再除以2，但是当两个数都大于其最大值的一半时，

相加的结果会发生内存移除。比如：

unsigned average(unsigned a, unsigned b)
{
	return (a + b) / 2;
}
average(0x8000'0000 + 0x8000'0000) = 0; // 内存溢出

解决方法：

1. 使用减法代替加法

   unsigned average(unsigned a, unsigned b)
   {
   	// assume a > b
   	return b + (a - b) / 2;
   }

2. 分别求两个数的均值再相加，最后修正地位，以确保两个数都是奇数时结果仍然正确：

   unsigned average(unsigned a, unsigned b)
   {
   	return (a / 2) + (b / 2) + (a & b & 1);
   }

3. SWAR (SMID with a register)

   unsigned average(unsigned a, unsigned b) 
   {
     // 交集 + 合集 / 2
     // &运算不会发生进位
   	return (a & b) + (a ^ b) / 2;
   }