位运算作用，求个真的懂这个的来

Question

基本原理我懂，但是一运算就弄不清楚了，比如 return (x&y)+((x^y)>>1); 为什么就能求平均~~~
百度复制粘贴的就别来凑热闹了。。。。真心求帮助

Answer 1

int f(int x,int y)
{
return (x&y)+((x^y)>>1);
};
f(729,271)=500.
解答：
x&y是取相同的位与，这个结果是x和y相同位，x^y是取x和y的不同位的和，右移1位，相当于除以2.所以结果是求x和y的平均数。

如果二进制不易理解，那我们看看十进制的情况。
假如将&操作和^操作推广到是取十进制位中来，即如果&操作对应的两个位上的数相同，则结果为两个数中的一个，否则为0.如2&2=2，2&3=0；如果^操作则留下两个数不同的那些位，234^136=204+106;
(以下的&和^都是上面假设推广到十进制中的运算符，而非二进制中的运算符)
现在如果设x=234，y=136,x&y=30，x^y=204+106,(x&y)+((x^y)/2)=30+(204+106)/2=185.
( (234+136) / 2 = ( 204+30+106+30) / 2 = 30 + (204+106) / 2 ).

追问

还是理解不上去位运算的用法.....哭死了......有什么好的办法能理解位运算么？

还是理解不上去位运算的用法.....哭死了......有什么好的办法能理解位运算么？

追答

这个算是技巧，没理解也是可以的，看得懂就行

Answer 2

核心在于要时刻带着幂次的概念去理解。
可以这么理解：每一个数都可以写成2的幂次和的形式：
kn*2^n+kn-1*2+...+k2*2^2+k1*2+k0
以上kn,kn-1,...,k2,k1,k0只能为1或0.
实质也就是一个数的2进制表达形式：kn kn-1 ... k2 k1 k0 （ki只能在0、1中取值）
现在有2个数：a、b，我们都把它们的写成2的幂次和的形式：
a=∑ ki*2^i (i=0,1,2....n)
b=∑ kj*2^j (j=0,1,2....m)
以n、m中大的那个为基准，我们把a、b的同幂次项一一对应：
不妨设m>n，则有：
a=am*2^m+am-1*2^m-1+...+a2*2^2+a1*2+a0 (am,am-1,...,a2,a1,a0只能取0或1)
b=bm*2^m+bm-1*2^m-1+...+b2*2^2+b1*2+b0 (bm,bm-1,...,b2,b1,b0只能取0或1)
那么现在，如果我们要求a和b的平均，是不是就很清楚了：
(a+b)/2=(am+bm)/2 * 2^m + (am-1+bm-1)/2 *2^m-1 + ... + (a2+b2)/2 * 2^2 + (a1+b1)/2 * 2 + (a0+b0)/2
若 ai=bi (i=0,1,2,...,m)，则 (ai+bi)/2=ai=bi，所以相同的位不变
若 ai≠bi，则ai+bi必为1（ai、bi必然一个为0，一个为1），则 (ai+bi)/2=1/2，不够除了，怎么办？从后面的幂次里面借一个过来，所以此时的 i 对应的幂次项 2^ki 需要往后移一位。
基本就是这样了。