1.整數(shù)的表示
重要結(jié)論：任何整數(shù)都可以表示為2的不同冪次的和
2,8,16進(jìn)制與10進(jìn)制的相互轉(zhuǎn)換
2.整數(shù)的計算機運算
對整數(shù)的
進(jìn)制展開（
）可以用如下偽代碼描述：
余數(shù)部分
商部分
}
整數(shù)的加法：
image.png
image.png
image.png
但其實在硬件實現(xiàn)上由于高位的運算必須等待低位的運算完成充边，延遲時間長，故采用超前進(jìn)位加法器進(jìn)行并行運算，其原理如下：
image.png
圖中乘法表示與岖研，加法表示或
image.png
其實相當(dāng)于通過復(fù)雜的硬件搜贤，將未知量轉(zhuǎn)為已知量掖举，每一位的運算同時進(jìn)行讥邻，互不干擾拦英，運算時間固定蜒什，效率提升。
乘法運算
image.png
image.png
image.png
更高效的算法：
image.png
image.png
偽代碼展示：
image.png
image.png
以上乘法算法并非最優(yōu)的方法疤估，更多內(nèi)容參考https://zhuanlan.zhihu.com/p/63291883
同時在高級語言層面大多數(shù)情況不需要考慮位運算的復(fù)雜度灾常，同時現(xiàn)代計算機普遍配備著效率極高的乘法器，在機器指令層面可以高效執(zhí)行铃拇，這里僅僅作為一個算法的展示钞瀑，在程序設(shè)計層面，并沒有實際意義
除法和取余運算
image.png
image.png
模指數(shù)運算
image.png
image.png
原文這里寫的比較簡略慷荔，我寫一些自己的理解：
由同余的性質(zhì)雕什，，
轉(zhuǎn)化為二進(jìn)制數(shù)對應(yīng)的也就是對
通過得知的結(jié)果計算出显晶，對應(yīng)偽代碼
power=(power*power)mod m ;
而對于贷岸，其二進(jìn)制表示不一定都為1，所以對于是0的項磷雇，要跳過偿警，這也是if語句僅僅在時才執(zhí)行的意義。
image.png
image.png
對復(fù)雜度的分析如上唯笙，感覺mod部分省略了應(yīng)該是因為兩個乘數(shù)都小于m螟蒸，其乘積不會超出m很多，這部分的復(fù)雜度就可以忽略了崩掘。
3. 運算的復(fù)雜度
大O表示法：是一個指定的正整數(shù)集合七嫌，如果
為取正值的函數(shù)，且對所有的
有定義苞慢，則如果存在正常數(shù)
對所有充分大的
均有
诵原，那么
在
上是
以下是衍生的幾個性質(zhì)：
- 如果
是
的，
是正常數(shù)，則
是
- 如果
的皮假，
的鞋拟，則
回顧整數(shù)乘法，對a,b有：
image.png
image.png
image.png
image.png
本節(jié)的算法java實現(xiàn)部分參見：位操作實現(xiàn)四則運算
