请选择 进入手机版 | 继续访问电脑版

12360技术网 - 专业IT技术发表平台

 立即注册  找回密码
查看: 621|回复: 4

【数学】位运算与代数结构

[复制链接]

11

主题

24

帖子

316

积分

中级会员

Rank: 3Rank: 3

积分
316
发表于 2020-1-26 22:55:00 | 显示全部楼层 |阅读模式
在java中,位运算主要有非∼\sim∼,与&\&&,或∣|∣,异或∧\wedge∧,左移,算数右移>>>>>>>>>,这么多种。我们只考虑三十二位整数,也就是java中的int类型。将其符合的运算律以及代数结构整理如下:
设ZZZ是三十二位整数全体。则∀x∈Z\forall x \in Z∀x∈Z,有:
1、x+∼x=−1x+\sim x=-1x+∼x=−1
证明可以由计算机中负数表示方法得到。因为−x=∼x+1-x=\sim x+1−x=∼x+1,所以上式成立。
2、设x∈{0,1}x\in\{0,1\}x∈{0,1},则x&0=0,x∣1=1,x&1=x,x∣0=xx\&0=0, x|1=1, x\&1=x, x|0=xx&0=0,x∣1=1,x&1=x,x∣0=x并且若x,y,z∈{0,1}x,y,z\in\{0,1\}x,y,z∈{0,1},则x&y=y&x,x∣y=y∣x,(x&y)&z=x&(y&z),(x∣y)∣z=x∣(y∣z)x\&y=y\& x, x|y=y|x, \\(x\&y)\&z=x\&(y\&z), (x|y)|z=x|(y|z)x&y=y&x,x∣y=y∣x,(x&y)&z=x&(y&z),(x∣y)∣z=x∣(y∣z)所以&\&&和∣|∣满足交换律和结合律。用群论的语言就是,({0,1},&)(\{0,1\},\&)({0,1},&)与({0,1},∣)(\{0,1\},|)({0,1},∣)是一个交换幺半群(commutative monoid)。即:
({0,1},&)(\{0,1\},\&)({0,1},&)是一个交换幺半群,单位元是111,000不可逆;
({0,1},∣)(\{0,1\},|)({0,1},∣)是一个交换幺半群,单位元是000,111不可逆。
3、若x,y,z∈{0,1}x,y,z\in\{0,1\}x,y,z∈{0,1},考虑分配律,我们有:x&(y∣z)=(x&y)∣(x&z)x∣(y&z)=(x∣y)&(x∣z)x\&(y|z)=(x\&y)|(x\&z)\\x|(y\&z)=(x|y)\&(x|z)x&(y∣z)=(x&y)∣(x&z)x∣(y&z)=(x∣y)&(x∣z)证明非常简单,只需要对xxx进行考虑,再结合前面的性质就可以了。所以由上面可知,它们还互相满足分配律。
4、德摩根律:∼(x&y)=(∼x)∣(∼y)∼(x∣y)=(∼x)&(∼y)\sim (x\& y)=(\sim x)| (\sim y)\\\sim (x| y)=(\sim x)\& (\sim y)∼(x&y)=(∼x)∣(∼y)∼(x∣y)=(∼x)&(∼y)
由于位运算是把两个int的每个数的每一位单独拿出来分别对应的做运算,所以上面的性质对任意int的xxx和yyy都是成立的,但是要按照计算机里的二进制表示稍微改动一下:∀x∈Z,x&0=0,x∣(−1)=−1,x&(−1)=x,x∣0=x\forall x\in Z, x\&0=0, x|(-1)=-1, x\&(-1)=x, x|0=x∀x∈Z,x&0=0,x∣(−1)=−1,x&(−1)=x,x∣0=x交换律结合律分配律仍然保持正确。
4、以上看出来,&\&&和∣|∣的性质还不够好,不过∧\wedge∧的性质就相当好了。我们有这样的结论:({0,1},∧)(\{0,1\},\wedge)({0,1},∧)是个阿贝尔群。
证明:封闭性显然,交换律显然,000是单位元,且两个元素的阶都是222,也就是逆元都是自己。结合律证明如下:由于x∧y=(x&∼y)∣(∼x&y)x\wedge y=(x\&\sim y)|(\sim x\&y)x∧y=(x&∼y)∣(∼x&y),所以:(x∧y)∧z=((x&∼y)∣(∼x&y))∧z=(((x&∼y)∣(∼x&y))&∼z)∣(∼((x&∼y)∣(∼x&y))&z)=(x&∼y&∼z)∣(∼x&y&∼z)∣(x&y&z)∣(∼x&∼y&z)=(x&((∼y&∼z)∣(y&z)))∣(∼x&((y&∼z)∣(∼y&z)))=(x&∼(y∧z))∣(∼x&(y∧z))=x∧(y∧z)(x\wedge y)\wedge z=((x\&\sim y)|(\sim x\&y))\wedge z\\=(((x\&\sim y)|(\sim x\&y))\&\sim z) |\\ (\sim((x\&\sim y)|(\sim x\&y))\& z)\\=(x\&\sim y\&\sim z)|(\sim x\& y\&\sim z)|\\(x\& y\& z)|(\sim x \&\sim y \& z)\\=(x\&((\sim y \& \sim z)|(y\& z)))|\\(\sim x\&((y \& \sim z)|(\sim y\& z)))\\=(x\&\sim (y\wedge z))|(\sim x\& (y\wedge z))\\=x\wedge (y\wedge z)(x∧y)∧z=((x&∼y)∣(∼x&y))∧z=(((x&∼y)∣(∼x&y))&∼z)∣(∼((x&∼y)∣(∼x&y))&z)=(x&∼y&∼z)∣(∼x&y&∼z)∣(x&y&z)∣(∼x&∼y&z)=(x&((∼y&∼z)∣(y&z)))∣(∼x&((y&∼z)∣(∼y&z)))=(x&∼(y∧z))∣(∼x&(y∧z))=x∧(y∧z)所以结合律成立。所以({0,1},∧)(\{0,1\},\wedge)({0,1},∧)是个阿贝尔群。
5、关于左移和右移,有两个很显然的结论:x>>1=x/2x>>1=x/2x>>1=x/2,以及xi)&1;
求xxx的从右向左数第111个111出现的位置代表的数是几:lowbit(x)=x&−xlowbit(x)=x\&-xlowbit(x)=x&−x。这个结论可以由−x=∼x+1-x=\sim x+1−x=∼x+1得到。
                                                                                                                                       
                                                    
  • 点赞                        
  • 收藏                        
  • 分享                                                                                                                        
  •                                                         
                                      
    • 文章举报                           
                                                
                                                                        
                                            
                                                        edWard的算法世界                                                                发布了106 篇原创文章 · 获赞 0 · 访问量 2792                                                                                            私信                                                            关注
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x




上一篇:计算机与操作系统与网络原理--3
下一篇:《计算机网络:自顶向下方法(原书第七版)》 参考答案(英文版+中文版)
回复

使用道具 举报

0

主题

19

帖子

409

积分

中级会员

Rank: 3Rank: 3

积分
409
发表于 2020-1-28 22:25:29 | 显示全部楼层
楼主,大恩不言谢了![www.12360.co]
回复

使用道具 举报

0

主题

18

帖子

388

积分

中级会员

Rank: 3Rank: 3

积分
388
发表于 2020-2-3 00:52:18 | 显示全部楼层
楼主太厉害了!楼主,I*老*虎*U![www.12360.co]
回复

使用道具 举报

0

主题

13

帖子

283

积分

中级会员

Rank: 3Rank: 3

积分
283
发表于 5 天前 | 显示全部楼层
既然你诚信诚意的推荐了,那我就勉为其难的看看吧![www.12360.co]
回复

使用道具 举报

0

主题

11

帖子

241

积分

中级会员

Rank: 3Rank: 3

积分
241
发表于 1 小时前 | 显示全部楼层
楼主发贴辛苦了,谢谢楼主分享![www.12360.co]
回复

使用道具 举报

懒得打字嘛,点击右侧快捷回复 【右侧内容,后台自定义】
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

12360技术网

GMT+8, 2020-2-29 15:24 , Processed in 0.083892 second(s), 26 queries .

本网站内容收集于互联网,Www.12360.Co不承担任何由于内容的合法性及健康性所引起的争议和法律责任。 欢迎大家对网站内容侵犯版权等不合法和不健康行为进行监督和举报。

© 2019-2020 Www.12360.Co

快速回复 返回顶部 返回列表