日本亚洲人妻不卡,干日韩女人区,国产一二啪啪啪啪

1.整數(shù)的表示

重要結(jié)論：任何整數(shù)都可以表示為2的不同冪次的和
2,8,16進(jìn)制與10進(jìn)制的相互轉(zhuǎn)換

2.整數(shù)的計(jì)算機(jī)運(yùn)算

對(duì)整數(shù) $n$ 的 $b$ 進(jìn)制展開（ $a_{k-1}...a_{1}a_{0}$ ）可以用如下偽代碼描述：

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

整數(shù)的加法：

image.png

但其實(shí)在硬件實(shí)現(xiàn)上由于高位的運(yùn)算必須等待低位的運(yùn)算完成，延遲時(shí)間長，故采用超前進(jìn)位加法器進(jìn)行并行運(yùn)算，其原理如下：

image.png

$C_{i}表示第i位的進(jìn)位，A_{i}與B_{i}表示兩個(gè)數(shù)第i位的值$

圖中乘法表示與，加法表示或

image.png

其實(shí)相當(dāng)于通過復(fù)雜的硬件，將未知量轉(zhuǎn)為已知量，每一位的運(yùn)算同時(shí)進(jìn)行，互不干擾，運(yùn)算時(shí)間固定，效率提升。

乘法運(yùn)算

image.png

更高效的算法：

image.png

偽代碼展示：

image.png

以上乘法算法并非最優(yōu)的方法，更多內(nèi)容參考https://zhuanlan.zhihu.com/p/63291883
同時(shí)在高級(jí)語言層面大多數(shù)情況不需要考慮位運(yùn)算的復(fù)雜度，同時(shí)現(xiàn)代計(jì)算機(jī)普遍配備著效率極高的乘法器，在機(jī)器指令層面可以高效執(zhí)行，這里僅僅作為一個(gè)算法的展示，在程序設(shè)計(jì)層面，并沒有實(shí)際意義

除法和取余運(yùn)算

image.png

模指數(shù)運(yùn)算

image.png

原文這里寫的比較簡略，我寫一些自己的理解：
由同余的性質(zhì)，，
轉(zhuǎn)化為二進(jìn)制數(shù)對(duì)應(yīng)的也就是對(duì)
通過得知的結(jié)果計(jì)算出，對(duì)應(yīng)偽代碼
power=(power*power)mod m ;
而對(duì)于，其二進(jìn)制表示不一定都為1，所以對(duì)于是0的項(xiàng)，要跳過，這也是if語句僅僅在時(shí)才執(zhí)行的意義。

image.png

對(duì)復(fù)雜度的分析如上，感覺mod部分省略了應(yīng)該是因?yàn)閮蓚€(gè)乘數(shù)都小于m，其乘積不會(huì)超出m很多，這部分的復(fù)雜度就可以忽略了。

3. 運(yùn)算的復(fù)雜度

大O表示法： $S$ 是一個(gè)指定的正整數(shù)集合，如果 $f,g$ 為取正值的函數(shù)，且對(duì)所有的 $x\in S$ 有定義，則如果存在正常數(shù) $K$ 對(duì)所有充分大的 $x\in S$ 均有 $f(x)<Kg(x)$ ，那么 $f$ 在 $S$ 上是 $O(g)$