(x+y)>>1 == (x&y)+((x^y)>>1)
设x和y是两个32bit的无符号整数，unsigned int。
这个公式的左边是x和y的平均值。
右边是：符号&是按位求“与”(and)，^是xor。
17 个解决方案
#1
我们可以改为证明:
x+y = ((x&y)<<1) + (x^y)
有了这个,上面的结果自然就出来了.
我们考虑x,y在二进制表示时候,按位相加
其中第i位
xi+yi = ((xi&yi)<<1) + (xi^yi)
其中(xi&yi)<<1表示当xi和yi都是1是,需要进位1.
xi^yi表示不考虑进位,当前位的值.
把所有这些数据相加,也就是
x+y = Sum{xi*2^i}+Sum{yi*2^i} = Sum{(xi+yi)*2^i}
= Sum{ (((xi&yi)<<1)+(xi^yi))*2^i }
=Sum{ ((xi&yi)*2)*2^i + (xi^yi)*2^i}
=Sum{(xi&yi)*2^i}*2 + Sum{(xi^yi)*2^i}
=(x&y)*2+(x^y)
=((x&y)<<1)+(x^y)
x+y = ((x&y)<<1) + (x^y)
有了这个,上面的结果自然就出来了.
我们考虑x,y在二进制表示时候,按位相加
其中第i位
xi+yi = ((xi&yi)<<1) + (xi^yi)
其中(xi&yi)<<1表示当xi和yi都是1是,需要进位1.
xi^yi表示不考虑进位,当前位的值.
把所有这些数据相加,也就是
x+y = Sum{xi*2^i}+Sum{yi*2^i} = Sum{(xi+yi)*2^i}
= Sum{ (((xi&yi)<<1)+(xi^yi))*2^i }
=Sum{ ((xi&yi)*2)*2^i + (xi^yi)*2^i}
=Sum{(xi&yi)*2^i}*2 + Sum{(xi^yi)*2^i}
=(x&y)*2+(x^y)
=((x&y)<<1)+(x^y)
#2
楼上强人
#3
程序员的福音---去www.mylinux.com.cn看看吧,程序员的图书馆
最全面的程序开发资料网www.mylinux.com.cn
包罗java,linux,数据库,安全等等技术资料,更有众多软件外包项目
我们的qq群:15096318 学习程序的都可以来
华资软件作为一家专业的软件公司,现公开承接各种软件外包项目.
www.mylinux.com.cn国内最大的网上软件加工厂，提供最完善的软件外包服务，采用流水型操作流程。
中国软件业的发展不缺人才也不缺资金，缺的是人才的组织和管理，MyLinux平台的建设解决了软件人才的组织和管理问题，将每一项目最合适的软件开发人才以最有效率的形式组织在一起，从而取得1+1〉2的效果。
MyLinux（www. MyLinux.com.cn）由上海巨灵信息技术有限公司主办，是目前国内最大的网上软件加工厂，该网站将提供最完善的软件外包服务，采用流水型操作流程。
详情请登陆www. MyLinux.com.cn
您可把您的具体要求发布在http://www.mylinux.com.cn/guiderAction.do?type=7上,并留下联系方式,我们网站的技术部门和客服会在第一时间审核安排.
最全面的程序开发资料网www.mylinux.com.cn
包罗java,linux,数据库,安全等等技术资料,更有众多软件外包项目
我们的qq群:15096318 学习程序的都可以来
华资软件作为一家专业的软件公司,现公开承接各种软件外包项目.
www.mylinux.com.cn国内最大的网上软件加工厂，提供最完善的软件外包服务，采用流水型操作流程。
中国软件业的发展不缺人才也不缺资金，缺的是人才的组织和管理，MyLinux平台的建设解决了软件人才的组织和管理问题，将每一项目最合适的软件开发人才以最有效率的形式组织在一起，从而取得1+1〉2的效果。
MyLinux（www. MyLinux.com.cn）由上海巨灵信息技术有限公司主办，是目前国内最大的网上软件加工厂，该网站将提供最完善的软件外包服务，采用流水型操作流程。
详情请登陆www. MyLinux.com.cn
您可把您的具体要求发布在http://www.mylinux.com.cn/guiderAction.do?type=7上,并留下联系方式,我们网站的技术部门和客服会在第一时间审核安排.
#4
我也来发个呵呵:)
归纳法证明：
（证明中的数都是二进制，Fn为n位数且各位都为1；把x,y中位数少的前面补0使x',y'位数相同，
证明中的x,y都是指x',y'）
原理：如果p/2 = q+r/2,p'/2 = q'+r'/2，pqr都<=n位数，且(p'|Fn)=p'；(q'|Fn)=q'；(r'|Fn)=r'；
那么有(p+p')/2 = (q+q')+(r+r')/2成立。因为p'r'的任何非0位都比pr的最高位还高，不管是＋还是>>
p,p'；r,r'都互不影响.....................%EXP
一、用穷举法容易验证当x,y都是一位数时和两位数时原式成立。
二、如果当x,y是n位时成立，那么在x,y的最高位前分别补一位a,b，且(a|b)!=0。即：使x,y变成r,t，
且r,t为n+1位。
1、如果(x+y)是n位，那么(r+t) = ((a+b)<<n)+(x+y)，((a+b)<<n)和(x+y)满足%EXP，
rt成立只要ab,xy分别成立，ab是一位所以成立，xy已成立，所以rt对原式是成立的。
2、如果(x+y)是n+1位，那么(r+t) = ((a+b+1)<<n)+((x+y)&Fn)。这时ab和xy在第n位和n+1位
相关。令a',b'分别是r,t的高两位，x',y'分别为r,t的低(n-1)位，这样a'b'和x'y'满足%EXP，
所以rt对原式成立。
归纳法证明：
（证明中的数都是二进制，Fn为n位数且各位都为1；把x,y中位数少的前面补0使x',y'位数相同，
证明中的x,y都是指x',y'）
原理：如果p/2 = q+r/2,p'/2 = q'+r'/2，pqr都<=n位数，且(p'|Fn)=p'；(q'|Fn)=q'；(r'|Fn)=r'；
那么有(p+p')/2 = (q+q')+(r+r')/2成立。因为p'r'的任何非0位都比pr的最高位还高，不管是＋还是>>
p,p'；r,r'都互不影响.....................%EXP
一、用穷举法容易验证当x,y都是一位数时和两位数时原式成立。
二、如果当x,y是n位时成立，那么在x,y的最高位前分别补一位a,b，且(a|b)!=0。即：使x,y变成r,t，
且r,t为n+1位。
1、如果(x+y)是n位，那么(r+t) = ((a+b)<<n)+(x+y)，((a+b)<<n)和(x+y)满足%EXP，
rt成立只要ab,xy分别成立，ab是一位所以成立，xy已成立，所以rt对原式是成立的。
2、如果(x+y)是n+1位，那么(r+t) = ((a+b+1)<<n)+((x+y)&Fn)。这时ab和xy在第n位和n+1位
相关。令a',b'分别是r,t的高两位，x',y'分别为r,t的低(n-1)位，这样a'b'和x'y'满足%EXP，
所以rt对原式成立。
#5
对于 x+y 我们可以分为两部分来计算 第一部分分别对每一位不考虑进位相加 第二部分算出每一位的进位值 然后我算出来的进位值提高一位加到第一部分中去即为 x+y
根据此理 第一部分我们很容易可以得出为 x^y 第二部分为 x&y
所以 x+y = x^y + (x&y) << 1
根据此理 第一部分我们很容易可以得出为 x^y 第二部分为 x&y
所以 x+y = x^y + (x&y) << 1
#6
学习,接点分
#7
xor运算又叫模2加运算（相加不进位），不妨设X，Y的每一位相应为X[i],Y[i]（i从1开始）。当X[i]与Y[i]都为1时，X[i]+Y[i]是要进位的，但是在xor运算中没有进位。所以要加上： （2的i次方）*（X[i]&Y[i]），即当相同位为1时，要加上2的i次方。累加和为：2*（X&Y），此时2没有次方了。（想想为什么？），这点很重要。：公式 (x+y)>>1 == (x&y)+((x^y)>>1)，两边左移1位或两边乘以2，变成：（x+y)==2*（x&y）+（x^y）。得证。
#8
x = (x&y) + ((x^y)&x)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
----------------------------------
x + y = 2 * (x&y) + (x^y)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
----------------------------------
x + y = 2 * (x&y) + (x^y)
#9
强！这里的强人的确很多。
上面的贴子有几个已经看懂了，例如mathe的方法。有些还不懂，例如mLee79的方法。我不太理解
x = (x&y) + ((x^y)&x)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
这三个条件是怎么得出的。
我的基础知识比较差，请问各位高手，我想补一补这方面的课，有没有好的教科书可以推荐给我？
上面的贴子有几个已经看懂了，例如mathe的方法。有些还不懂，例如mLee79的方法。我不太理解
x = (x&y) + ((x^y)&x)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
这三个条件是怎么得出的。
我的基础知识比较差，请问各位高手，我想补一补这方面的课，有没有好的教科书可以推荐给我？
#10
俺也来一个：
x+y == x-(x&y) + y-(x&y) + 2*(x&y)
== (x中为1，y中为0) + (y中为1，x中为0) + 2*(x&y)
== x^y + 2*(x&y)
两边除以2
x+y == x-(x&y) + y-(x&y) + 2*(x&y)
== (x中为1，y中为0) + (y中为1，x中为0) + 2*(x&y)
== x^y + 2*(x&y)
两边除以2
#11
关键还是2楼说的，加法中的进位部分是(x&y)<<1
#12
mathe() ( ) 信誉：120 Blog
--------
强人
--------
强人
#13
mathe的解法有点不完全:
由x+y = ((x&y)<<1) + (x^y)
并不一定能推断出
(x+y)>>1 == (x&y)+((x^y)>>1)
举例(都是二进制数):
由 0010==0001+0001;
不能推断出
0010>>1==(0001>>1)+(0001>>1);
另,题目没指明x,y是否有符号数,由于x+y有可能溢出,等式本身就不一定成立;
#include <stdio.h>
int main(int argc,char * argv[])
{
unsigned int x=0xffffffff,y=0xfffffffe;
unsigned int c1=(x+y)>>1;
unsigned int d1=(x&y)+((x^y)>>1);
unsigned int c2=x+y;
unsigned int d2=((x&y)<<1)+(x^y);
printf("c1:%u d1:%u\nc2:%u d2:%u",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:2147483646 d1:4294967294
c2:4294967293 d2:4294967293
可以看出:
x+y == ((x&y)<<1) + (x^y)
但
(x+y)>>1 != (x&y)+((x^y)>>1)
既等式本身就不成立!
由x+y = ((x&y)<<1) + (x^y)
并不一定能推断出
(x+y)>>1 == (x&y)+((x^y)>>1)
举例(都是二进制数):
由 0010==0001+0001;
不能推断出
0010>>1==(0001>>1)+(0001>>1);
另,题目没指明x,y是否有符号数,由于x+y有可能溢出,等式本身就不一定成立;
#include <stdio.h>
int main(int argc,char * argv[])
{
unsigned int x=0xffffffff,y=0xfffffffe;
unsigned int c1=(x+y)>>1;
unsigned int d1=(x&y)+((x^y)>>1);
unsigned int c2=x+y;
unsigned int d2=((x&y)<<1)+(x^y);
printf("c1:%u d1:%u\nc2:%u d2:%u",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:2147483646 d1:4294967294
c2:4294967293 d2:4294967293
可以看出:
x+y == ((x&y)<<1) + (x^y)
但
(x+y)>>1 != (x&y)+((x^y)>>1)
既等式本身就不成立!
#14
再看看有符号数的情况:
#include <stdio.h>
#include <limits.h>
int main(int argc,char * argv[])
{
signed int x=INT_MAX,y=INT_MAX-1;
signed int c1=(x+y)>>1;
signed int d1=(x&y)+((x^y)>>1);
signed int c2=x+y;
signed int d2=((x&y)<<1)+(x^y);
printf("c1:%d d1:%d\nc2:%d d2:%d",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:-2 d1:2147483646
c2:-3 d2:-3
#include <stdio.h>
#include <limits.h>
int main(int argc,char * argv[])
{
signed int x=INT_MAX,y=INT_MAX-1;
signed int c1=(x+y)>>1;
signed int d1=(x&y)+((x^y)>>1);
signed int c2=x+y;
signed int d2=((x&y)<<1)+(x^y);
printf("c1:%d d1:%d\nc2:%d d2:%d",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:-2 d1:2147483646
c2:-3 d2:-3
#15
to tailzhou(尾巴):
我想就等式而言还是成立的！只不过是你的32位程序在运算中溢出了而已。
例如：
x=0xffffffff,y=0xfffffffe;
x+y是多少？其实你用计算器算一下就知道是0x1FFFFFFFD（8589934589），而不是你认为正确的
c2:4294967293 和 d2:4294967293, 即0xFFFFFFFD.
:)
我想就等式而言还是成立的！只不过是你的32位程序在运算中溢出了而已。
例如：
x=0xffffffff,y=0xfffffffe;
x+y是多少？其实你用计算器算一下就知道是0x1FFFFFFFD（8589934589），而不是你认为正确的
c2:4294967293 和 d2:4294967293, 即0xFFFFFFFD.
:)
#16
"设x和y是两个32bit的无符号整数，unsigned int。"
lz的原话.
纯从数学来看,等式当然是成立的.
由mathe的证明有x+y==((xi&yi)<<1) + (xi^yi);
又因为((xi&yi)<<1)的最后一位不可能是1,((xi&yi)<<1) 与 (xi^yi)的末位相加不会产生进位;
所以：(x+y)>>1 == (x&y)+((x^y)>>1)
lz的原话.
纯从数学来看,等式当然是成立的.
由mathe的证明有x+y==((xi&yi)<<1) + (xi^yi);
又因为((xi&yi)<<1)的最后一位不可能是1,((xi&yi)<<1) 与 (xi^yi)的末位相加不会产生进位;
所以：(x+y)>>1 == (x&y)+((x^y)>>1)
#17
x和y是两个32bit的无符号整数并不是表示x+y这样的临时变量也必须是32位的。否则你要我怎么描述？
#1
我们可以改为证明:
x+y = ((x&y)<<1) + (x^y)
有了这个,上面的结果自然就出来了.
我们考虑x,y在二进制表示时候,按位相加
其中第i位
xi+yi = ((xi&yi)<<1) + (xi^yi)
其中(xi&yi)<<1表示当xi和yi都是1是,需要进位1.
xi^yi表示不考虑进位,当前位的值.
把所有这些数据相加,也就是
x+y = Sum{xi*2^i}+Sum{yi*2^i} = Sum{(xi+yi)*2^i}
= Sum{ (((xi&yi)<<1)+(xi^yi))*2^i }
=Sum{ ((xi&yi)*2)*2^i + (xi^yi)*2^i}
=Sum{(xi&yi)*2^i}*2 + Sum{(xi^yi)*2^i}
=(x&y)*2+(x^y)
=((x&y)<<1)+(x^y)
x+y = ((x&y)<<1) + (x^y)
有了这个,上面的结果自然就出来了.
我们考虑x,y在二进制表示时候,按位相加
其中第i位
xi+yi = ((xi&yi)<<1) + (xi^yi)
其中(xi&yi)<<1表示当xi和yi都是1是,需要进位1.
xi^yi表示不考虑进位,当前位的值.
把所有这些数据相加,也就是
x+y = Sum{xi*2^i}+Sum{yi*2^i} = Sum{(xi+yi)*2^i}
= Sum{ (((xi&yi)<<1)+(xi^yi))*2^i }
=Sum{ ((xi&yi)*2)*2^i + (xi^yi)*2^i}
=Sum{(xi&yi)*2^i}*2 + Sum{(xi^yi)*2^i}
=(x&y)*2+(x^y)
=((x&y)<<1)+(x^y)
#2
楼上强人
#3
程序员的福音---去www.mylinux.com.cn看看吧,程序员的图书馆
最全面的程序开发资料网www.mylinux.com.cn
包罗java,linux,数据库,安全等等技术资料,更有众多软件外包项目
我们的qq群:15096318 学习程序的都可以来
华资软件作为一家专业的软件公司,现公开承接各种软件外包项目.
www.mylinux.com.cn国内最大的网上软件加工厂，提供最完善的软件外包服务，采用流水型操作流程。
中国软件业的发展不缺人才也不缺资金，缺的是人才的组织和管理，MyLinux平台的建设解决了软件人才的组织和管理问题，将每一项目最合适的软件开发人才以最有效率的形式组织在一起，从而取得1+1〉2的效果。
MyLinux（www. MyLinux.com.cn）由上海巨灵信息技术有限公司主办，是目前国内最大的网上软件加工厂，该网站将提供最完善的软件外包服务，采用流水型操作流程。
详情请登陆www. MyLinux.com.cn
您可把您的具体要求发布在http://www.mylinux.com.cn/guiderAction.do?type=7上,并留下联系方式,我们网站的技术部门和客服会在第一时间审核安排.
最全面的程序开发资料网www.mylinux.com.cn
包罗java,linux,数据库,安全等等技术资料,更有众多软件外包项目
我们的qq群:15096318 学习程序的都可以来
华资软件作为一家专业的软件公司,现公开承接各种软件外包项目.
www.mylinux.com.cn国内最大的网上软件加工厂，提供最完善的软件外包服务，采用流水型操作流程。
中国软件业的发展不缺人才也不缺资金，缺的是人才的组织和管理，MyLinux平台的建设解决了软件人才的组织和管理问题，将每一项目最合适的软件开发人才以最有效率的形式组织在一起，从而取得1+1〉2的效果。
MyLinux（www. MyLinux.com.cn）由上海巨灵信息技术有限公司主办，是目前国内最大的网上软件加工厂，该网站将提供最完善的软件外包服务，采用流水型操作流程。
详情请登陆www. MyLinux.com.cn
您可把您的具体要求发布在http://www.mylinux.com.cn/guiderAction.do?type=7上,并留下联系方式,我们网站的技术部门和客服会在第一时间审核安排.
#4
我也来发个呵呵:)
归纳法证明：
（证明中的数都是二进制，Fn为n位数且各位都为1；把x,y中位数少的前面补0使x',y'位数相同，
证明中的x,y都是指x',y'）
原理：如果p/2 = q+r/2,p'/2 = q'+r'/2，pqr都<=n位数，且(p'|Fn)=p'；(q'|Fn)=q'；(r'|Fn)=r'；
那么有(p+p')/2 = (q+q')+(r+r')/2成立。因为p'r'的任何非0位都比pr的最高位还高，不管是＋还是>>
p,p'；r,r'都互不影响.....................%EXP
一、用穷举法容易验证当x,y都是一位数时和两位数时原式成立。
二、如果当x,y是n位时成立，那么在x,y的最高位前分别补一位a,b，且(a|b)!=0。即：使x,y变成r,t，
且r,t为n+1位。
1、如果(x+y)是n位，那么(r+t) = ((a+b)<<n)+(x+y)，((a+b)<<n)和(x+y)满足%EXP，
rt成立只要ab,xy分别成立，ab是一位所以成立，xy已成立，所以rt对原式是成立的。
2、如果(x+y)是n+1位，那么(r+t) = ((a+b+1)<<n)+((x+y)&Fn)。这时ab和xy在第n位和n+1位
相关。令a',b'分别是r,t的高两位，x',y'分别为r,t的低(n-1)位，这样a'b'和x'y'满足%EXP，
所以rt对原式成立。
归纳法证明：
（证明中的数都是二进制，Fn为n位数且各位都为1；把x,y中位数少的前面补0使x',y'位数相同，
证明中的x,y都是指x',y'）
原理：如果p/2 = q+r/2,p'/2 = q'+r'/2，pqr都<=n位数，且(p'|Fn)=p'；(q'|Fn)=q'；(r'|Fn)=r'；
那么有(p+p')/2 = (q+q')+(r+r')/2成立。因为p'r'的任何非0位都比pr的最高位还高，不管是＋还是>>
p,p'；r,r'都互不影响.....................%EXP
一、用穷举法容易验证当x,y都是一位数时和两位数时原式成立。
二、如果当x,y是n位时成立，那么在x,y的最高位前分别补一位a,b，且(a|b)!=0。即：使x,y变成r,t，
且r,t为n+1位。
1、如果(x+y)是n位，那么(r+t) = ((a+b)<<n)+(x+y)，((a+b)<<n)和(x+y)满足%EXP，
rt成立只要ab,xy分别成立，ab是一位所以成立，xy已成立，所以rt对原式是成立的。
2、如果(x+y)是n+1位，那么(r+t) = ((a+b+1)<<n)+((x+y)&Fn)。这时ab和xy在第n位和n+1位
相关。令a',b'分别是r,t的高两位，x',y'分别为r,t的低(n-1)位，这样a'b'和x'y'满足%EXP，
所以rt对原式成立。
#5
对于 x+y 我们可以分为两部分来计算 第一部分分别对每一位不考虑进位相加 第二部分算出每一位的进位值 然后我算出来的进位值提高一位加到第一部分中去即为 x+y
根据此理 第一部分我们很容易可以得出为 x^y 第二部分为 x&y
所以 x+y = x^y + (x&y) << 1
根据此理 第一部分我们很容易可以得出为 x^y 第二部分为 x&y
所以 x+y = x^y + (x&y) << 1
#6
学习,接点分
#7
xor运算又叫模2加运算（相加不进位），不妨设X，Y的每一位相应为X[i],Y[i]（i从1开始）。当X[i]与Y[i]都为1时，X[i]+Y[i]是要进位的，但是在xor运算中没有进位。所以要加上： （2的i次方）*（X[i]&Y[i]），即当相同位为1时，要加上2的i次方。累加和为：2*（X&Y），此时2没有次方了。（想想为什么？），这点很重要。：公式 (x+y)>>1 == (x&y)+((x^y)>>1)，两边左移1位或两边乘以2，变成：（x+y)==2*（x&y）+（x^y）。得证。
#8
x = (x&y) + ((x^y)&x)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
----------------------------------
x + y = 2 * (x&y) + (x^y)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
----------------------------------
x + y = 2 * (x&y) + (x^y)
#9
强！这里的强人的确很多。
上面的贴子有几个已经看懂了，例如mathe的方法。有些还不懂，例如mLee79的方法。我不太理解
x = (x&y) + ((x^y)&x)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
这三个条件是怎么得出的。
我的基础知识比较差，请问各位高手，我想补一补这方面的课，有没有好的教科书可以推荐给我？
上面的贴子有几个已经看懂了，例如mathe的方法。有些还不懂，例如mLee79的方法。我不太理解
x = (x&y) + ((x^y)&x)
y = (x&y) + ((x^y)&y)
((x^y)&x) + ((x^y)&y) = x^y
这三个条件是怎么得出的。
我的基础知识比较差，请问各位高手，我想补一补这方面的课，有没有好的教科书可以推荐给我？
#10
俺也来一个：
x+y == x-(x&y) + y-(x&y) + 2*(x&y)
== (x中为1，y中为0) + (y中为1，x中为0) + 2*(x&y)
== x^y + 2*(x&y)
两边除以2
x+y == x-(x&y) + y-(x&y) + 2*(x&y)
== (x中为1，y中为0) + (y中为1，x中为0) + 2*(x&y)
== x^y + 2*(x&y)
两边除以2
#11
关键还是2楼说的，加法中的进位部分是(x&y)<<1
#12
mathe() ( ) 信誉：120 Blog
--------
强人
--------
强人
#13
mathe的解法有点不完全:
由x+y = ((x&y)<<1) + (x^y)
并不一定能推断出
(x+y)>>1 == (x&y)+((x^y)>>1)
举例(都是二进制数):
由 0010==0001+0001;
不能推断出
0010>>1==(0001>>1)+(0001>>1);
另,题目没指明x,y是否有符号数,由于x+y有可能溢出,等式本身就不一定成立;
#include <stdio.h>
int main(int argc,char * argv[])
{
unsigned int x=0xffffffff,y=0xfffffffe;
unsigned int c1=(x+y)>>1;
unsigned int d1=(x&y)+((x^y)>>1);
unsigned int c2=x+y;
unsigned int d2=((x&y)<<1)+(x^y);
printf("c1:%u d1:%u\nc2:%u d2:%u",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:2147483646 d1:4294967294
c2:4294967293 d2:4294967293
可以看出:
x+y == ((x&y)<<1) + (x^y)
但
(x+y)>>1 != (x&y)+((x^y)>>1)
既等式本身就不成立!
由x+y = ((x&y)<<1) + (x^y)
并不一定能推断出
(x+y)>>1 == (x&y)+((x^y)>>1)
举例(都是二进制数):
由 0010==0001+0001;
不能推断出
0010>>1==(0001>>1)+(0001>>1);
另,题目没指明x,y是否有符号数,由于x+y有可能溢出,等式本身就不一定成立;
#include <stdio.h>
int main(int argc,char * argv[])
{
unsigned int x=0xffffffff,y=0xfffffffe;
unsigned int c1=(x+y)>>1;
unsigned int d1=(x&y)+((x^y)>>1);
unsigned int c2=x+y;
unsigned int d2=((x&y)<<1)+(x^y);
printf("c1:%u d1:%u\nc2:%u d2:%u",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:2147483646 d1:4294967294
c2:4294967293 d2:4294967293
可以看出:
x+y == ((x&y)<<1) + (x^y)
但
(x+y)>>1 != (x&y)+((x^y)>>1)
既等式本身就不成立!
#14
再看看有符号数的情况:
#include <stdio.h>
#include <limits.h>
int main(int argc,char * argv[])
{
signed int x=INT_MAX,y=INT_MAX-1;
signed int c1=(x+y)>>1;
signed int d1=(x&y)+((x^y)>>1);
signed int c2=x+y;
signed int d2=((x&y)<<1)+(x^y);
printf("c1:%d d1:%d\nc2:%d d2:%d",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:-2 d1:2147483646
c2:-3 d2:-3
#include <stdio.h>
#include <limits.h>
int main(int argc,char * argv[])
{
signed int x=INT_MAX,y=INT_MAX-1;
signed int c1=(x+y)>>1;
signed int d1=(x&y)+((x^y)>>1);
signed int c2=x+y;
signed int d2=((x&y)<<1)+(x^y);
printf("c1:%d d1:%d\nc2:%d d2:%d",c1,d1,c2,d2);
return 0;
}
输出:
G:\projects>test
c1:-2 d1:2147483646
c2:-3 d2:-3
#15
to tailzhou(尾巴):
我想就等式而言还是成立的！只不过是你的32位程序在运算中溢出了而已。
例如：
x=0xffffffff,y=0xfffffffe;
x+y是多少？其实你用计算器算一下就知道是0x1FFFFFFFD（8589934589），而不是你认为正确的
c2:4294967293 和 d2:4294967293, 即0xFFFFFFFD.
:)
我想就等式而言还是成立的！只不过是你的32位程序在运算中溢出了而已。
例如：
x=0xffffffff,y=0xfffffffe;
x+y是多少？其实你用计算器算一下就知道是0x1FFFFFFFD（8589934589），而不是你认为正确的
c2:4294967293 和 d2:4294967293, 即0xFFFFFFFD.
:)
#16
"设x和y是两个32bit的无符号整数，unsigned int。"
lz的原话.
纯从数学来看,等式当然是成立的.
由mathe的证明有x+y==((xi&yi)<<1) + (xi^yi);
又因为((xi&yi)<<1)的最后一位不可能是1,((xi&yi)<<1) 与 (xi^yi)的末位相加不会产生进位;
所以：(x+y)>>1 == (x&y)+((x^y)>>1)
lz的原话.
纯从数学来看,等式当然是成立的.
由mathe的证明有x+y==((xi&yi)<<1) + (xi^yi);
又因为((xi&yi)<<1)的最后一位不可能是1,((xi&yi)<<1) 与 (xi^yi)的末位相加不会产生进位;
所以：(x+y)>>1 == (x&y)+((x^y)>>1)
#17
x和y是两个32bit的无符号整数并不是表示x+y这样的临时变量也必须是32位的。否则你要我怎么描述？