計算機(jī)的源頭

• 日常生活中评矩，我們廣泛采用十進(jìn)制計數(shù)法叶堆。

  
  
  
  

  10是十進(jìn)制計數(shù)法的基數(shù)，這也是十進(jìn)制中“十”的由來斥杜。

• 十進(jìn)制是使用10作為基數(shù)虱颗，那么二進(jìn)制就是使用2作為基數(shù)。110101作為二進(jìn)制：

  
  
  
  

  按照這個思路果录，我們還可以推導(dǎo)出八進(jìn)制上枕，十六進(jìn)制等等計數(shù)法。

• 計算機(jī)為什么使用二進(jìn)制
  計算機(jī)使用二進(jìn)制和現(xiàn)代計算機(jī)的硬件實現(xiàn)有關(guān)弱恒。組成計算機(jī)系統(tǒng)的邏輯電路通常只要有兩個狀態(tài)辨萍，開關(guān)的接通與斷開。
  斷開的狀態(tài)我們使用“0”來表示返弹，接通的狀態(tài)用“1”來表示锈玉。由于每位數(shù)據(jù)只有斷開和接通兩種狀態(tài)，所以即使系統(tǒng)收到了一定程度的干擾時义起，仍然能夠可靠地分辨出數(shù)字時“0”還是“1”拉背。因此，在具體的系統(tǒng)實現(xiàn)中默终，二進(jìn)制的數(shù)據(jù)表達(dá)具有抗干擾強(qiáng)椅棺，可靠性高的優(yōu)點(diǎn)犁罩。相比之下，如果用十進(jìn)制設(shè)計具有10種電路两疚，情況就會非常復(fù)雜床估，判斷狀態(tài)額時候出錯的幾率就會大大提高。另外诱渤，二進(jìn)制也非常適合邏輯運(yùn)算丐巫，邏輯運(yùn)算中“真”和“假”，正好與二進(jìn)制的“0”和“1”兩個數(shù)字相對應(yīng)勺美。邏輯運(yùn)算中的加法递胧、乘法都可以通過 “0”和“1”的加法、乘法和減法來實現(xiàn)赡茸。
• 二進(jìn)制的位操作
  • 向左移動
    二進(jìn)制110101當(dāng)左移動一位缎脾，就是在末尾添加一位0，因此110101就變成了1101010占卧，請注意赊锚，這里討論的是數(shù)字沒有溢出的情況。所謂數(shù)字溢出就是二進(jìn)制的位數(shù)超過了系統(tǒng)所指定的位數(shù)屉栓，目前主流的系統(tǒng)都支持至少32位的整型數(shù)字，而1101010遠(yuǎn)未超過32位耸袜，所以不會溢出友多。如果進(jìn)行左移動操作的二進(jìn)制已經(jīng)超過了32位，左移后數(shù)字就會溢出堤框，需要將溢出的位數(shù)去除域滥。
    
    
    在這個例子中，如果將1101010換算為十進(jìn)制蜈抓，就是106启绰，剛好是53的2倍。所以沟使，我們可以得出一個結(jié)論：二進(jìn)制向左移動一位委可，其實就是將數(shù)字翻倍
  • 向右移動
    二進(jìn)制向右移動一位就是去除末尾的那一位，因此110101就變成了11010.我們將11010換算為十進(jìn)制腊嗡，就是26着倾，正好是53除以2的整數(shù)商。所以燕少，二進(jìn)制右移一位卡者，就是將數(shù)字除以2并處以2求整數(shù)商的操作
    
    
    這段代碼的運(yùn)行結(jié)果是：數(shù)字 53 向左移 1 位是 106；數(shù)字 53 向右移 1 位是 26客们。數(shù)字 53 向左移 3位是 424崇决，數(shù)字 53 向右移 3 位是 6材诽。
    其中，移位一次相當(dāng)于乘以或者除以2恒傻，而移位3次就相當(dāng)于乘以或者除以8（2的3次方）脸侥。

• 位的“與”“或”“異或”運(yùn)算

  
  

取余操作和哈希函數(shù)的關(guān)系

• 提起余數(shù)我們都不陌生，我們生活中有太多和余數(shù)相關(guān)的例子
  比如說碌冶，今天星期三湿痢，你想知道50天后星期幾，可以拿50除以7扑庞， 余1譬重，最后在今天的基礎(chǔ)上加一天，這樣你就知道50天之后是星期四了罐氨。
  再比如我們做Web開發(fā)臀规，經(jīng)常要用到分頁的操作。假如要展示1123條數(shù)據(jù)栅隐，每頁展示10條塔嬉，那該怎么計算總共的頁數(shù)呢，1123除以10租悄，最后得到商是112谨究，余數(shù)是3，所以總頁數(shù)是112+1=113泣棋，最后的余數(shù)就是多出來胶哲，湊不夠一頁的數(shù)據(jù)。
  那任意一個整數(shù)除以7潭辈，余數(shù)肯定在0～6之間鸯屿。
  假如今天是星期一，從今天開始的100天里把敢，都有多少個星期呢寄摆？第1天，第8修赞、15天除以7余數(shù)都是1婶恼，都是星期一，同理柏副，第2熙尉、9、16天都是星期二搓扯。
  這些數(shù)的余數(shù)都是一樣的检痰，所以都被歸類到了一起，我們的前人很早就注意到了這一點(diǎn)锨推，所以他們把這一結(jié)論稱為同余定理铅歼。簡單來說就是兩個整數(shù)a和b公壤，如果他們除以正整數(shù)m得到的余數(shù)相等，我們就可以說a和b對于模m同余椎椰。
• 我們經(jīng)常提到的奇數(shù)和偶數(shù)其實也是同余定理的一個應(yīng)用厦幅，里面的模是2.
• 簡單來說，同余定理其實就是用來分類的
• 在每個編程語言中慨飘，都會有對應(yīng)的哈希函數(shù)确憨，哈希有的時候也會被翻譯成散列，簡單來說它就是將任意長度的輸入瓤的，通過哈希算法休弃，壓縮為某一固定長度的輸出求余的過程就是在做這事。
• 舉個例子圈膏，假如你想要快速讀寫100萬條數(shù)據(jù)塔猾，要達(dá)到快速的存取最理想的情況當(dāng)然是開辟一個連續(xù)的空間存放這些數(shù)據(jù)，這樣就可以減少尋址的時間稽坤，但是由于條件的限制丈甸，并不能開辟能夠容納100萬條數(shù)據(jù)記錄的連續(xù)地址空間。
  但是我們可以開辟若干個較小的連續(xù)空間尿褪，而每個空間又能存放一定的數(shù)據(jù)記錄睦擂，比如找到100個較小的連續(xù)空間，也就是說杖玲，這些空間彼此之間是被分割開來的祈匙，但是內(nèi)部是連續(xù)的，并足以容納1萬記錄連續(xù)存放天揖，那么我們就可以使用余數(shù)和同余定理來設(shè)計一個散列函數(shù)，并實現(xiàn)哈希表的結(jié)構(gòu)跪帝。
  
  
  在這個公式中今膊，x表示等待被轉(zhuǎn)換的數(shù)值，而size表示有限存儲空間的大小伞剑，mod表示取余操作斑唬，通過余數(shù)，能將任何數(shù)值黎泣，轉(zhuǎn)換為有限范圍內(nèi)的一個數(shù)值恕刘，然后根據(jù)這個新的數(shù)值，來確定將數(shù)值存放到何處抒倚。
  根據(jù)記錄標(biāo)號模100的余數(shù)褐着，制定某條數(shù)據(jù)存放在哪個空間。這個時候公式就變成了：
  
  
  假設(shè)有兩條記錄托呕，他們的記錄標(biāo)號分別是1和101.把這些模100之后余數(shù)都是1的含蓉，放到第一個可用空間里面频敛。以此類推，將余數(shù)為2的2馅扣、102斟赚、202等存放到第二個可用空間，將100差油、200拗军、300存放到第100個可用空間里。
  這樣就可以根據(jù)求余的快速數(shù)字變化蓄喇，對數(shù)組進(jìn)行分組发侵，并把它們存放到不同的地址空間里，求余操作本身非常簡單公罕，因此幾乎不會增加尋址時間器紧。
  
  除此之外位了增加數(shù)據(jù)散列的隨機(jī)程度，我們可以在公式中愛如一個較大的隨機(jī)數(shù)MAX楼眷，公式就變成了：
  
  image.png
  
  假設(shè)隨機(jī)數(shù)MAX是590199铲汪，那么針對標(biāo)號為1的記錄進(jìn)行重新計算，最后計算的結(jié)果就是0罐柳，針對標(biāo)號為101的記錄掌腰，如果隨機(jī)數(shù)MAX取627901，那么對應(yīng)結(jié)果應(yīng)該是2.這樣先前分配到空間1的兩條記錄在新的公式作用下就會被分配到兩個不同的空用空間里张吉。
  使用MAX這個隨機(jī)數(shù)后被分配到同一個空間中的記錄就更加“隨機(jī)”了齿梁，適合需要將數(shù)據(jù)重新洗牌的應(yīng)用場景，比如加密算法等肮蛹。
  例：
  加密規(guī)則：
  • 1.先對每個三位數(shù)的個勺择、十、百位數(shù)都加上一個較大的隨機(jī)數(shù)伦忠。
  • 2.將每位上的數(shù)除以7省核，用得到的余數(shù)代替原先有的個、十昆码、百位數(shù)气忠。

  • 3.最后將第一位和第三位交換给郊。
    這就是一個基本加密變換過程膀息。
    假如說，要加密數(shù)字625麻顶，根據(jù)剛才的規(guī)則脓匿，隨機(jī)數(shù)選擇590127淘钟，那百、十陪毡、個位分別加上這個隨機(jī)數(shù)就變成了590133日月、590129袱瓮、590132.然后三位分別處以7求余得到5，1爱咬，4.最終尺借，我們可以得到加密后的數(shù)字就是415.因為加密的人知道加密的規(guī)則，求余所用的除以7精拟，除法的商燎斩，以及所引用的隨機(jī)數(shù)590127，所以當(dāng)拿到415的時候蜂绎，機(jī)密者就可以計算出原始的數(shù)據(jù)是625.

    
    
    image.png

用二分法計算計算平方根

數(shù)學(xué)歸納法

遞歸上

image.png

遞歸下

分而治之 歸并排序

• 歸并排序通過分治的思想栅表，把長度為n的數(shù)列。每次簡化為n/2的數(shù)列师枣，這更有利于計算機(jī)的并行處理怪瓶，只需要log2n次歸并。

  
  

• 把歸并和分治的思想結(jié)合起來践美，這其實就是歸并排序算法洗贰。
  這種算法每次把數(shù)列進(jìn)行二等分，直到唯一的數(shù)字陨倡，也就是最基本的有序數(shù)列敛滋。然后從這些最基本的有序數(shù)列開始，兩兩合并有序的數(shù)列直到所有的數(shù)字都參與了歸并排序兴革。

  
  

• 歸并排序使用了分治的思想绎晃，而這個過程需要使用歸并來實現(xiàn)。
  歸并排序的算法用分治的思想把數(shù)列不斷的簡化杂曲，直到每個數(shù)列僅剩下一個單獨(dú)的數(shù)庶艾，然后再使用歸并逐步合并有序的數(shù)列，從而達(dá)到將整個薯類進(jìn)行排序的目的擎勘。而這個歸并排序正好可以使用歸并的方式來實現(xiàn)咱揍。

  
  

• 分治的過程可以通過歸并來表達(dá)，因此货抄，歸并排序最直觀的方式就是遞歸，所以從遞歸的步驟出發(fā)看下歸并排序如何實現(xiàn)朱转。
  假設(shè) n = k = 1的時候蟹地，已經(jīng)對較小的兩組數(shù)進(jìn)行了排序。只要在n= k的時候?qū)⑦@兩組數(shù)合并起來藤为，并且保證合并后的數(shù)組仍然是有序的就行了怪与。
  所以在遞歸的每次嵌套調(diào)用中，代碼都將一組數(shù)分解成更小的兩組缅疟，然后將這兩個小組的排序交給下一次的嵌套調(diào)用分别。而本次調(diào)用只需要關(guān)心如何將排序好的兩個小組進(jìn)行排序遍愿。
  在初始狀態(tài)，也即是 n = 1 的時候耘斩，對于排序的案例而言沼填，只包含了單個數(shù)字的分組，由于分組里只有一個數(shù)組括授，所以已經(jīng)是排好序了坞笙，之后就可以開始遞歸調(diào)用的返回階段。

  
  
  
  

1. 我們?yōu)槭裁葱枰创a和補(bǔ)碼荚虚？

1.什么是符號位薛夜？為什么要有符號位

符號位是有符號二進(jìn)制數(shù)中的最高位，需要用它來表示正負(fù)數(shù)版述。
把二進(jìn)制數(shù)分為符號位（signed）和無符號位（unsigned）梯澜。
如果是二進(jìn)制無符號數(shù)，最高位不是符號位渴析。二進(jìn)制符號數(shù)的最高位則表示正負(fù)晚伙。

2.什么是溢出

• 在數(shù)學(xué)的理論中，數(shù)字可以有無窮大檬某，也有無窮小撬腾。可是恢恼，現(xiàn)實中的計算機(jī)系統(tǒng)民傻，總有一個物理上的極限（比如說晶體管的大小和數(shù)量）因此不可能表示無窮大或者無窮小的數(shù)字。對計算機(jī)而言场斑，無論是何種數(shù)據(jù)類型漓踢，都有一個上限和下限。
  一旦某個數(shù)字超過了這些限定漏隐，就會發(fā)生溢出喧半。如果超出上限，就叫上溢出（overflow）青责。如果超出了下限挺据，就叫下溢出underflow）。

• 溢出之后會發(fā)生什么呢脖隶？n 位數(shù)字的最大的正值扁耐，其符號位為 0，剩下的 n-1 位都為 0产阱。而符號位是 1婉称，后面 n-1 位全是 0，這表示 -2^(n-1)。

  
  
  
  

  那么就是說王暗，上溢出之后悔据，又從下限開始，最大的數(shù)值加 1俗壹，就變成了最小的數(shù)值科汗，周而復(fù)始，這不就是余數(shù)和取模的概念嗎策肝？

  
  

二進(jìn)制的原碼肛捍、反碼及補(bǔ)碼

• 原碼
  原碼就是我們看到的二進(jìn)制的原始表示。對于有符號的二進(jìn)制來說之众，原碼的最高位是符號位拙毫，而其余的位用來表示該數(shù)字絕對值的二進(jìn)制。所以 +2 的原碼是 000…010棺禾，-2 的的原碼是 100.…010缀蹄。
• 那么我們是不是可以直接使用負(fù)數(shù)的原碼來進(jìn)行減法計算呢？答案是否定的膘婶。還是以 3+(-2) 為例缺前。
  2，它的十進(jìn)制是 000…010悬襟。最低的兩位是 10衅码，前面的高位都是 0。如果我們使用 -2 的原碼脊岳，也就是 100…010逝段，然后我們把 3 的二進(jìn)制原碼 000…011 和 -2 的二進(jìn)制原碼 100…010 相加，會得到 100…0101割捅。具體計算看這幅圖奶躯。
  
  
  二進(jìn)制編碼上的加減法和十進(jìn)制類似，只不過亿驾，在加法中嘹黔，十進(jìn)制是滿 10 才進(jìn)一位，二進(jìn)制加法中只要滿 2 就進(jìn)位莫瞬；同樣儡蔓，在減法中，二進(jìn)制借位后相當(dāng)于 2 而不是 10疼邀。
  相加后的結(jié)果是二進(jìn)制 100…0101喂江，它的最高位是 1，表示負(fù)數(shù)檩小，而最低的 3 位是 101开呐，表示 5烟勋，所以結(jié)果就是 -5 的原碼了规求，而 3+(-2) 應(yīng)該等于 1筐付，兩者不符。
  那該怎么辦呢阻肿？這個問題的解答還要依賴計算機(jī)的溢出機(jī)制瓦戚。
  對計算機(jī)里的減法進(jìn)行變換。假設(shè)有 i-j丛塌，其中 j 為正數(shù)较解。如果 i-j 加上取模的除數(shù)，那么會形成溢出赴邻，并正好能夠獲得我們想要的 i-j 的運(yùn)算結(jié)果印衔。如果還是不太好理解，參考下面這張圖姥敛。
  
  
  把這個過程用表達(dá)式寫出來就是 i-j=(i-j)+(2^n-1+1)=i+(2n-1-j+1)奸焙。
  其中 2^n-1 的二進(jìn)制碼在不考慮符號位的情況下是 n-1位的 1，那么 2^n-1-2 的結(jié)果就是下面這樣的：
  
  
  從結(jié)果可以觀察出來彤敛，所謂 2^n-1-j 相當(dāng)于對正數(shù) j的二進(jìn)制原碼与帆，除了符號位之外按位取反（0 變 1，1 變 0）墨榄。由于負(fù)數(shù) -j 和正數(shù) j 的原碼玄糟，除了符號位之外都是相同的，所以袄秩，2^n-1-j 也相當(dāng)于對負(fù)數(shù) -j 的二進(jìn)制源碼阵翎，除了符號位之外按位取反。我們把 2^n-1-j 所對應(yīng)的編碼稱為負(fù)數(shù) -j 的反碼播揪。所以贮喧，-2 的反碼就是 1111…1101。
  有了反碼的定義猪狈，那么就可以得出 i-j=i+(2^n-1-j+1)=i 的原碼 +(-j 的反碼)+1箱沦。
  如果我們把 -j 的反碼加上 1 定義為 -j 的補(bǔ)碼，就可以得到 i-j=i 的原碼 +(-j 的補(bǔ)碼)雇庙。
  由于正數(shù)的加法無需負(fù)數(shù)的加法這樣的變換谓形，因此正數(shù)的原碼、反碼和補(bǔ)碼三者都是一樣的疆前。最終寒跳，我們可以得到 i-j=i 的補(bǔ)碼+(-j 的補(bǔ)碼)。
  換句話說竹椒，計算機(jī)可以通過補(bǔ)碼童太，正確地運(yùn)算二進(jìn)制減法。我們再來用 3+(-2) 來驗證一下。正數(shù) 3 的補(bǔ)碼仍然是 0000…0011书释，-2 的補(bǔ)碼是 1111…1110翘贮，兩者相加，最后得到了正確的結(jié)果 1 的二進(jìn)制爆惧。
  
  
  可見狸页，溢出本來是計算機(jī)數(shù)據(jù)類型的一種局限性，但在負(fù)數(shù)的加法上扯再，它倒是可以幫我們大忙芍耘。

2.位操作應(yīng)用實例

1.1. 驗證奇偶數(shù)

• 奇偶數(shù)其實也是余數(shù)的應(yīng)用。編程中熄阻，也可以用位運(yùn)算來判斷及偶數(shù)斋竞。
• 仔細(xì)觀察，你會發(fā)現(xiàn)偶數(shù)的二進(jìn)制最后一位總是 0秃殉，而奇數(shù)的二進(jìn)制最后一位總是 1窃页，因此對于給定的某個數(shù)字，我們可以把它的二進(jìn)制和數(shù)字 1 的二進(jìn)制進(jìn)行按位“與”的操作复濒，取得這個數(shù)字的二進(jìn)制最后一位脖卖，然后再進(jìn)行判斷。
• 同樣次數(shù)的奇偶判斷巧颈，使用位運(yùn)算的方法耗時明顯更低畦木。

2.交換兩個數(shù)字

• 想在計算機(jī)中交換兩個變量的值，通常都需要一個中間變量砸泛，來臨時存放被交換的值十籍。不過，利用異或的特性唇礁，我們就可以避免這個中間變量勾栗。具體的代碼如下：

  x = (x ^ y);
  y = x ^ y;
  x = x ^ y;

-把第一步代入第二步中, 可以得到

y = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x

• 把第一步和第二步的結(jié)果代入第三步中，可以得到：

x = (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y

• 這里用到異或的兩個特性盏筐，第一個是兩個相等的數(shù)的異或為 0围俘，比如 x^x= 0；第二個是任何一個數(shù)和 0 異或之后琢融，還是這個數(shù)不變界牡，比如 0^y=y。

3. 集合操作

• 集合和邏輯的概念是緊密相連的漾抬，因此集合的操作也可以通過位的邏輯操作來實現(xiàn)宿亡。