由位运算到操作符,再到逐步理解群论
Step by Step for Understanding from Bitwise to Operators, then Group Theory
是否曾经会有过很努力,还是看不懂别人代码的苦恼?
有时是算法思路堵塞,有时是作者“故意”用了一些奇形怪状的位运算来炫技!
比如交换两个变量,不借助第三者的异或运算^;判断奇偶数用&运算;置位用左移<>运算等等。
这些代码常见于嵌入式编程(考虑效率),或编程比丑大赛(Hacker)之中。
为什么一般看不懂呢?
因为通常我们脑中并没有很好理解它的意义,而习惯上加、减、乘、除("+-*/")的意义好像都已印入脑中!
但仔细一想,这些"&,|,^,<>,~,"与“加减乘除”其实都一样,没什么区别的,它们都是操作符(Operator)啊!
操作符绑定两个数,再安一些规则在其中,就形成了群!
听不懂?,那么倒要真的问一下自己,是否真的懂了加减乘除啦?(据说博士毕业之前最好都要搞懂)
下面将举一些具体的位操作运算例子,以辅助大家对各操作符意义的理解。
然后结合加减乘除上升到操作符的抽象!
最后再到群论的入门介绍
希望大家领略了群论的风景之后,再回来看自己曾经学过的各个计算机语言(C,C++,C#,Java,Python,Javascript...虽然很多我都不熟?),会有too simple, too young的感慨?~
位操作介绍
位操作主要有与、或、非和异或,下面将介绍各种位操作的基本用法。
与
0 & 1 = 0
1 & 0 = 0
0 & 0 = 0
1 & 1 = 1
或
0 | 1 = 1
1 | 0 = 1
0 | 0 = 0
1 | 1 = 1
非
!0 = 1
!1 = 0
异或
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
1 ^ 1 = 0
位操作符两边的数a和b只有两个数0和1,加减乘除两边的操作数a和b可以是所有实数(除法b不能为0),这是它们的最大区别,再无其它!
要把运算映射到人可以理解的意义,第一步要把二进制数映到实数(整数),再结合效果map到人习惯理解的意义!
1.判断一个数的奇偶性(不用%2操作)
#ifniseven,willbetrue,elsefalse deff(n): returnn&1==0 f(n)n=3
False
f(4)
True
2.判断一个数是否为2的整数幂
returnn&(n-1)==0 f(4)deff(n):
True
3.不用临时变量交换两个数
a^=b b^=a a^=b returna,b x,y=3,4 swap(x,y)defswap(a,b):
(4, 3)
4.找到数组中出现奇数次的元素:
一个非空数组,只有一个元素出现奇数次,其余出现偶数次,找出那个元素:
res=0 foriinarr: res^=i res #任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字, #那么最终的结果刚好是那个只出现奇数次的数字,因为那些出现偶数次的数字全部在异或中抵消掉了。arr=[1,2,1,2,4,3,3]
4
5.求两个整数的平均值(结果有小数点时抛弃小数点)
return(a+b)>>1 f(5,6)deff(a,b):
5
6.取两个数的最大值(某些机器上,效率比a>b ? a:b高)
returnb&((a-b)>>31)|a&(~(a-b)>>31) f(8,22)deff(a,b):
22
7.取两个数的最小值(某些机器上,效率比a>b ? b:a高)
returna&((a-b)>>31)|b&(~(a-b)>>31) f(3,4)deff(a,b):
3
8.判断两个数符号是否相同(0算正号)
return(x^y)>=0 f(3,4)deff(x,y):
True
9.计算2的n次方
return2<-1) f(3)deff(n):
8
10.从低位到高位,取某数的第m位
return(n>>(m-1))&1 f(8,4)deff(n,m):
1
11.从低位到高位,将某数的第m位置1
returnn|(1<-1)) f(8,2)deff(n,m):
10
12.取相反数 (注意~是单目运算符)
return~n+1 f(-5)deff(n):
5
13.判断两个数是否相等
return(x1^x2)==0 f(3,4)deff(x1,x2):
False
14.对n加1,++
return-~n f(3)deff(n):
4
15.对n减1,--
return~-n f(4)deff(n):
3
16.取绝对值
return(n^(n>>31))-(n>>31) f(-9)deff(n):
9
我们总结一下:
任何数和 0 进行 OR 都为自身:x | 0 = x。
任何数和 -1 进行 OR 都为 -1:x | -1 = -1。
任何数和 0 进行 XOR 都为自身:x ^ 0 = x。
任何数和 -1 进行 XOR 都为 ~x:x ^ -1 = ~x。
任何数和其自身进行XOR都为0:x ^ x = 0。
对任何数 x 进行 NOT 操作的结果为 -(x + 1),~x = -(x+1)。
<
在位数没溢出的情况下,左移一位,可视为乘2操作,左移n位相当于乘以2的n次方
>>(有符号右移)该操作数会将第一个操作数向右移动指定的位数。向右被移出的位被丢弃,左侧用0补充,最左侧符号位用原符号位填充。
在位数没溢出的情况下,右移一位,可视为除2操作,右移n位相当于除以2的n次方
所有符号都只是一个代表某种意义的操作符,而已!它和“加减乘除”是完全一样的!
进而我们是不是可以把这种操作符进一步抽象?把它和集合中的元素绑定在一起就形成了群论!
群(group)的基本定义:
群是一个集合G 加上一个操作符运算"#",它结合任何两个元素a和b而形成另一个元素,记为a#b。
要成为群,这个集合和操作运算(G,#)必须满足叫做群公理(group axioms)的四个要求:
(1)封闭性(closure):对于所有G中a,b,运算a#b的结果也在G中。(2)结合性(Associativity):对于所有G中的a,b和c,等式 (a#b)#c=a#(b#c)成立。(3)单位元(Identity element):G中存在一个元素e,对于所有G中的元素a,等式 e#a = a#e = a 成立。(4)逆元(Inverse element):对于每个G中的a,存在G中的一个元素b使得 a#b=b#a=e。
注意:
(1)"#"可以是带有任何有意义的操作符,有一些不一定满足交换律,即a#b!=b#a,比如矩阵运算。(2)单位元和逆元是唯一的。(3)然后群还有阿贝尔群,循环群,半群,幺半群,子群,群同态,群同构,陪集,商群等概念,数学家总结的一些定理精彩致极!(4)你可能会感受到到5次方程的根无解问题原来如此简单(5)你可能会看费马小定理变得如此显然,不就是1+1=2一样自然的吗?希望各位鉴赏完后,再来看前面的位运算操作炫技,是否是雕虫小技??......
数学之水,更多免费干货、敬请关注详查~~
如果觉得《java加减乘除运算代码_从“位运算”炫技到“操作符” 再到逐步理解“群论”...》对你有帮助,请点赞、收藏,并留下你的观点哦!