位运算四则运算

一、位运算简介   我们先来熟悉下位运算的操作,大致要用到的位运算如下: 与(&)操作,该操作先将数值转换为二进制(如:a=3 => a=11),然后再进行操作。会对两个数相同的位置上进行操作,如果两个操作数长度不一致,会对值较短的数进行高位补0。(如:a =3 , b = 4, a+b = 011+100);相同位置为全1才为1,有0必为0,则上述结果:a&b = 000。 或(|)操作,跟与(&)操作不一样的地方在于,相同位置有1则1。a|b = 000。 异或(^)操作,相同则为0,不同则为1。a^b = 111。 我们将从加法开始依次分析。 二进制加法   可以很轻松的利用异或(^)操作与与(&)操作来实现加法的运算。与(&)操作可以用来获取两者相加进位,因为相同的位置同时出现1结果才为1,那么此时对结果集进行左移(<<)操作得到即为进位的值,采用异或(^)操作得到的是我们不带进位的相加结果,再利用不带进位与进位相加,依次迭代,即可以求出我们需要的值。 例如:a=010010,b=100111,计算步骤如下: 二进制减法   二进制的减法跟简单,其实就是在加法的基础上进行改进,众所周知,在计算机中一切都是在做加法,减法的由来就是一个数加上另外一个数的负数。计算机中的负数可以采用补码+1的形式得到 tip: 取反(~)得到补码: a的补码为~a。 二进制乘法   乘法有个特性就是,当你乘一个数的时候,你会左移它所出现的位置步,比如:10110010那么就会左移动1位,10111000左移3位,利用好这个特性我们就可以对一个数进行拆分了,保留每一位上面的1,其余的都变成0。 在这里需要用到几个辅助的位操作:1. -n = ~(n-1) = ~n+12. n&~(n-1),获取n中二进制中的最后一个13. n&(n-1),去掉n中二进制中的最后一个1 二进制除法   二进制的除法可以利用移位跟加减法进行计算。思路如下:先对除数进行移位操作,移位到一个临界值,即比被除数小的最大值,再用除数进行迭代相减,有点类似辗转相除法。   下面贴张图,应该就很好理解了。满足为1,不满足上0 POW的实现 在这里不使用的循环的原因是,那样太需要计算很多次,这里的temp用于保存上次的记录的结果,直接拿出来用,避免的了重复的计算,我们一次分为奇偶来讨论,如 x^4 可以拆分为x^2*x^2 => x^(y/2),而奇数的话,我们可以用上次保存的偶数乘以x得到。代码如下: 总结 位运算应用口诀 清零取反要用与,某位置一可用或 若要取反和交换,轻 轻松松用异或 移位运算 […]

lWoHvYe 无悔,专一