问答题 如何实现位操作求两个数的平均值
【正确答案】
【答案解析】一般而言,求解平均数的方法就是将两者相加,然后除以2,以变量x与y为例,两者的平均数为(x+y)/2。
但是采用上述方法,会存在一个问题,当两个数比较大时,如两者的和大于了机器位数能够表示的最大值,可能会存在数据溢出的情况,而采用位运算方法则可以避免这一问题,(x&y)+((x^y)>>1)方式表达的意思都是求解变量x与y的平均数,而且位运算相比除法运算,效率更高。
对于表达式(x&y)+((x^y)>>1),x&y表示的是取出x与y二进制位数中都为‘1’的所有位,x^y表示的是x与y中有一个为‘1’的所有位,右移1位相当于执行除以2运算。整个表达式实际上可以分为两部分,第一部分是都为‘1’的部分,因为相同,所以直接相加即可;而第二部分是x为‘1’、y为‘0’的部分,以及y为‘1’、x为‘0’的部分,两部分加起来再除以2,然后跟前面的相加就可以表示两者的平均数了。
以下述示例为例。
#include<stdio.h>
int main()
{
int x=2147483647,Y=2147483647;
printf("%d/n",(x+y)/2);
printf("%d/n",(x&y)+((x^y)>>1));
return 0;
}
在32位机器下,程序输出结果如下:
-1
2147483647
程序的输出正好验证了这一算法的可行性。
引申:如何利用位运算计算数的绝对值?
以x为负数为例来分析。因为在计算机中,数字都是以补码的形式存放的,求负数的绝对值,应该是不管符号位,执行按位取反,末位加1操作即可。
对于一个负数,将其右移31位后会变成0xfffffff,而对于一个正数而言,右移31位则为0x00000000,而0ffffffff^x+x=-1,因为1011^1111=0100,任何数与1111异或,其实质都是把x的0和1进行颠倒计算。如果用变量Y表示x右移31位,(x^y)-y则表示的是x的绝对值。
程序示例如下:
#include<stdio.h>
int MyAbs(int x)
{
int y;
y=x>>31;
return (x^y)-y;∥此处还可以写为(x+y)^y
}
int main()
{
printf("%d/n",MyAbs(2));
printf("%d/n",MyAbs(-2));
return 0;
}
程序输出结果:
2
2
上例中,在函数MyAbs中,对局部变量y进行赋值时,由于是对X进行右移31位,如果x为正数,则y=0;如果x为负数,则y=-1。