（2）整数运算

2019-07-12  本文已影响0人  古剑诛仙

1.整数的表示

重要结论：任何整数都可以表示为2的不同幂次的和
2,8,16进制与10进制的相互转换

2.整数的计算机运算

对整数n的b进制展开（a_{k-1}...a_{1}a_{0}）可以用如下伪代码描述：

q=n;
k=0;
while(q≠0)\{
\ \ \ \ \ a_{k}=q\ mod\ b; 余数部分
\ \ \ \ \ q=q\ div\ b; 商部分
\ \ \ \ \ k=k+1;
}
return(a_{k-1}...a_{1}a_{0});

整数的加法：

image.png
image.png
image.png

但其实在硬件实现上由于高位的运算必须等待低位的运算完成，延迟时间长，故采用超前进位加法器进行并行运算，其原理如下：


image.png

C_{i}表示第i位的进位，A_{i}与B_{i}表示两个数第i位的值

图中乘法表示与，加法表示或


image.png

其实相当于通过复杂的硬件，将未知量转为已知量，每一位的运算同时进行，互不干扰，运算时间固定，效率提升。

乘法运算

image.png
image.png
image.png

更高效的算法：

image.png
image.png
伪代码展示：
image.png
image.png
以上乘法算法并非最优的方法，更多内容参考https://zhuanlan.zhihu.com/p/63291883
同时在高级语言层面大多数情况不需要考虑位运算的复杂度，同时现代计算机普遍配备着效率极高的乘法器，在机器指令层面可以高效执行，这里仅仅作为一个算法的展示，在程序设计层面，并没有实际意义

除法和取余运算

image.png
image.png

模指数运算

image.png
image.png
原文这里写的比较简略，我写一些自己的理解：
由同余的性质，，
转化为二进制数对应的也就是对
通过得知的结果计算出，对应伪代码
power=(power*power)mod m ;
而对于，其二进制表示不一定都为1，所以对于是0的项，要跳过，这也是if语句仅仅在时才执行的意义。
image.png
image.png
对复杂度的分析如上，感觉mod部分省略了应该是因为两个乘数都小于m，其乘积不会超出m很多，这部分的复杂度就可以忽略了。

3. 运算的复杂度

大O表示法：S是一个指定的正整数集合，如果f,g为取正值的函数，且对所有的x\in S有定义，则如果存在正常数K对所有充分大的x\in S均有f(x)<Kg(x)，那么f在S上是O(g)

以下是衍生的几个性质：

  1. 如果f是O(g)的，c是正常数，则cf是O(g)的
  2. 如果f_{1}是O(g_{1})的，f_{2}是O(g_{2})的，则f_{1}+f_{2}是O(g_{1}+g_{2})

回顾整数乘法，对a,b有：


image.png
image.png
image.png
image.png

本节的算法java实现部分参见：位操作实现四则运算

上一篇 下一篇

猜你喜欢

热点阅读