明計(jì)算機(jī)的人真是個(gè)天才。計(jì)算機(jī)執(zhí)行的所有計(jì)算都可以分解成一系列簡單的數(shù)學(xué)運(yùn)算。計(jì)算機(jī)不斷地進(jìn)行數(shù)字相加、相乘、比較大小、移動(dòng)數(shù)字等操作，以便高效地解決問題。為了使這些操作變得實(shí)用，計(jì)算機(jī)需要能夠快速執(zhí)行這些操作。
以其中一種操作為例，計(jì)算機(jī)如何進(jìn)行數(shù)字相加？又如何能夠快速地解決復(fù)雜的問題？其基本策略與人計(jì)算數(shù)字并沒有太大的區(qū)別。
·如果要將兩組數(shù)字相加，可能會(huì)一次處理一對(duì)數(shù)字，先加第一對(duì)數(shù)字，然后是下一對(duì)，依此類推。有時(shí)可能會(huì)加一對(duì)數(shù)字，并留下一個(gè)進(jìn)位，然后影響下一對(duì)數(shù)字的加法。計(jì)算機(jī)也是這樣做的，只不過是用二進(jìn)制位代替十進(jìn)制數(shù)字。
一個(gè)稱為全加器的電路可以將兩個(gè)位相加，還可能有一個(gè)進(jìn)位位，然后它產(chǎn)生一個(gè)和及可能的進(jìn)位。例如，如果用輸入進(jìn)位位為0來相加1和0，則和將是1而沒有輸出進(jìn)位。但是如果用輸入進(jìn)位位為1來相加1和0，那么情況就變了。現(xiàn)在輸出一個(gè)進(jìn)位為1，而和位為0。
這些全加器在位上執(zhí)行非常簡單的操作，但可以將它們組合起來，以相加更大的數(shù)字。要將兩個(gè)四位數(shù)相加，可以將四個(gè)全加器串聯(lián)成一個(gè)脈動(dòng)進(jìn)位加法器。第一個(gè)全加器將右側(cè)位相加并產(chǎn)生一個(gè)和，它還將一個(gè)進(jìn)位位傳遞給下一個(gè)全加器，后者計(jì)算出一個(gè)和，并將可能的進(jìn)位位傳遞給下一個(gè)加法器。
通過連接足夠多的這些單位加法器，可以設(shè)計(jì)出添加數(shù)字尺寸任意大的電路。但隨著相加的數(shù)字變得更大，會(huì)注意到加法所需的時(shí)間越來越長，大多數(shù)加法器大部分時(shí)間都在等待傳遞進(jìn)位位，以便開始計(jì)算，但這并不是很有效的時(shí)間利用。
理想情況下，所有這些加法器都希望立即開始計(jì)算它們的和，但它們不能，因?yàn)樗鼈兊暮腿Q于上一個(gè)加法器是否有進(jìn)位輸出。進(jìn)位前瞻邏輯在這里就可以發(fā)揮重要作用。在進(jìn)位前瞻加法器中，基本思想是添加邏輯，來快速且同時(shí)地計(jì)算所有進(jìn)位，并將它們傳遞給需要的加法器。這使得單個(gè)位加法器無需等待所有先前的加法器即可完成工作。
但這是如何實(shí)現(xiàn)的？這個(gè)進(jìn)位前瞻加法器如何知道所有進(jìn)位是什么而不必進(jìn)行完整的加法？為了回答這個(gè)問題，讓我們看看其中一個(gè)單位加法器并考慮它是否會(huì)產(chǎn)生進(jìn)位。
根據(jù)輸入值，我們可能能夠?qū)@個(gè)加法作出一些斷言。對(duì)于某些輸入值，我們可能會(huì)說這個(gè)加法"產(chǎn)生"進(jìn)位。產(chǎn)生進(jìn)位意味著無論是否有輸入進(jìn)位，加法都會(huì)產(chǎn)生一個(gè)進(jìn)位。如果要添加的兩個(gè)位都是1，則會(huì)出現(xiàn)這種情況。當(dāng)兩個(gè)1相加時(shí)，無論是否有輸入進(jìn)位都會(huì)產(chǎn)生一個(gè)進(jìn)位輸出，因此我們說這個(gè)加法會(huì)產(chǎn)生一個(gè)進(jìn)位。
更正式地說，如果我們要相加的兩個(gè)位是A和B，則我們可以說該加法會(huì)在A和B都是1時(shí)產(chǎn)生一個(gè)進(jìn)位。對(duì)于其他輸入值，我們可能會(huì)說這個(gè)加法"傳播"進(jìn)位。傳播進(jìn)位意味著如果有輸入進(jìn)位，則會(huì)有一個(gè)輸出進(jìn)位。
例如，如果輸入位是1和0，則這個(gè)加法會(huì)傳播進(jìn)位；如果有輸入進(jìn)位，則輸出也會(huì)有進(jìn)位。但如果輸入位都是兩個(gè)0，則該加法不會(huì)傳播進(jìn)位。即使有輸入進(jìn)位，也不會(huì)有輸出進(jìn)位。換句話說，如果我們要相加的兩個(gè)位是A和B，則當(dāng)A或B是1時(shí)，該加法會(huì)傳播進(jìn)位。
從產(chǎn)生和傳播進(jìn)位的角度考慮，這些單位加法的思路有兩個(gè)用處。
·首先，對(duì)于每一對(duì)位，我們可以立即計(jì)算出該加法是否產(chǎn)生或傳播進(jìn)位，而不需要等待任何其他計(jì)算的結(jié)果。這意味著當(dāng)加法開始時(shí)，我們可以同時(shí)計(jì)算所有位對(duì)的這些產(chǎn)生和傳播值。
·其次，我們可以使用這些產(chǎn)生和傳播值來計(jì)算所有的進(jìn)位。對(duì)于任何給定的位相加，我們可以按照以下方式計(jì)算出進(jìn)位輸出。如果加法產(chǎn)生進(jìn)位，或者如果有輸入進(jìn)位且加法傳播進(jìn)位，則加法會(huì)產(chǎn)生一個(gè)進(jìn)位為1。
我們可以利用這個(gè)思想得到這個(gè)四位加法器中每個(gè)進(jìn)位的公式。假設(shè)我們正在相加的只是這四位數(shù)，沒有進(jìn)位輸入到它們，那么第一次加法的進(jìn)位輸出就等于該加法是否產(chǎn)生進(jìn)位。第二次加法的進(jìn)位輸出為1，如果第二次加法產(chǎn)生進(jìn)位。或者如果第一次加法產(chǎn)生進(jìn)位，且第二次加法傳播了該進(jìn)位，第三次加法的進(jìn)位輸出為1。如果第三次加法產(chǎn)生進(jìn)位，或者如果第二次加法產(chǎn)生了進(jìn)位，且第三次加法傳播了該進(jìn)位，或者如果第一次加法產(chǎn)生了進(jìn)位，且第二次和第三次加法都傳播了該進(jìn)位。
也許你可以看到這里形成了一個(gè)模式，我們可以為第四次加法的進(jìn)位輸出構(gòu)建類似的公式。注意，所有這些公式都是根據(jù)我們可以快速計(jì)算和同時(shí)計(jì)算的產(chǎn)生和傳播值計(jì)算出來的。這些公式本身也可以快速計(jì)算，將公式中的這些單獨(dú)項(xiàng)進(jìn)行與運(yùn)算只需一個(gè)邏輯步驟，然后再進(jìn)行或運(yùn)算將這些項(xiàng)組合在一起以得到進(jìn)位值。
這是第二步，結(jié)果是當(dāng)相加的兩個(gè)四位數(shù)的第一對(duì)位被相加時(shí)，我們可以計(jì)算出傳播和產(chǎn)生值，并開始將它們組合起來，這樣就得到了所有的進(jìn)位值，然后可以將它們傳遞給所有其他單個(gè)位加法器，以便它們可以同時(shí)進(jìn)行工作。
理論上，隨著我們相加的數(shù)字越來越大，通過這種進(jìn)位前瞻邏輯節(jié)省的時(shí)間也越來越多。在傳統(tǒng)的脈動(dòng)進(jìn)位加法器中，添加更大的數(shù)字意味著等待時(shí)間更長。因?yàn)檫M(jìn)位從一個(gè)加法器傳遞到下一個(gè)加法器，但在進(jìn)位前瞻加法器中，我們可以一次計(jì)算出所有進(jìn)位。
然而在實(shí)踐中，計(jì)算后面的進(jìn)位的公式，隨著項(xiàng)數(shù)增多而變得更大。用兩個(gè)步驟計(jì)算出這些公式的電路也不再那么實(shí)用。相反，我們經(jīng)常會(huì)將四位進(jìn)位前瞻加法器的邏輯封裝在一起，然后將它們串聯(lián)起來以構(gòu)建一個(gè)更大的加法器。每個(gè)四位加法器可以依次運(yùn)行，并將進(jìn)位傳遞給下一個(gè)。
但是現(xiàn)在我們知道了一個(gè)更有效的方法來做到這一點(diǎn)，我們可以再次使用進(jìn)位前瞻邏輯，只是在更大的范圍內(nèi)，每個(gè)四位組現(xiàn)在可以為其組計(jì)算生成和傳播值，而較大的進(jìn)位前瞻單元可以使用該信息來計(jì)算出每個(gè)四位加法器的進(jìn)位，以便它們可以在不等待彼此的情況下并行地工作。
在添加大數(shù)時(shí)應(yīng)用進(jìn)位前瞻邏輯可以節(jié)省大量時(shí)間。當(dāng)我們談?wù)撾娐窌r(shí)，這段時(shí)間以納秒為單位衡量，但當(dāng)計(jì)算機(jī)執(zhí)行數(shù)十億次操作時(shí)，這些納秒就會(huì)累加起來。
通過利用計(jì)算機(jī)電路可以同時(shí)執(zhí)行多個(gè)任務(wù)的事實(shí)，我們的邏輯現(xiàn)在更快了。因此，通過給予它們多個(gè)任務(wù)，它們可以在不需要等待其他邏輯完成的情況下執(zhí)行任務(wù)，從而使我們的計(jì)算更加高效。
看代碼：
// 計(jì)算x/y。退出時(shí)x=商, r=余數(shù)
void div(uint8_t x, uint8_t y) {
uint8_t r=0;
char count=8;
while (count--) {
r <<=1;
if (x & 0x80) r |=1;
x <<=1;
if (r >=y) {
r -=y; x |=1;
}
}
printf("%d %d\n", x, r);
}8051是個(gè)8位的cpu。apt install sdcc后在/usr/share/sdcc/lib/src/_divulong.c里有32位除法的匯編和C源碼。上述程序是從它改來的。為了便于學(xué)習(xí)和測(cè)試改成了8位。
無論是255/1還是9/4，循環(huán)都是固定8次。r和x在循環(huán)里<<=1，我們回顧下類似的"移位"方式：
int atoi(char* s) {
int n=0;
while (*s++)
n=n * 10 + s[-1] - '0';
return n;
}再回顧下十進(jìn)制135/4。看到1我們干啥？去找3了。寫個(gè)空格或0也可以，最終的商是033，再把連續(xù)的前導(dǎo)0去掉。
十進(jìn)制每位有0-9十個(gè)數(shù)字，二進(jìn)制每位只有0-1兩個(gè)數(shù)字，非0即1。
最后一些代碼：
算機(jī)使用二進(jìn)制系統(tǒng)進(jìn)行計(jì)數(shù)。在計(jì)算機(jī)中，二進(jìn)制是一種只包含0和1兩個(gè)數(shù)字的數(shù)字系統(tǒng)。計(jì)算機(jī)通過在電路中使用開關(guān)來表示0和1，從而實(shí)現(xiàn)數(shù)字的存儲(chǔ)和計(jì)算。
計(jì)算機(jī)中的計(jì)數(shù)是通過使用觸發(fā)器（flip-flop）來實(shí)現(xiàn)的。觸發(fā)器是一種電路元件，可以存儲(chǔ)一個(gè)二進(jìn)制位（0或1）。計(jì)算機(jī)中的觸發(fā)器通常是由邏輯門（如與門、或門、非門）組成的。
計(jì)算機(jī)通過將多個(gè)觸發(fā)器連接在一起，形成一個(gè)寄存器（register），來存儲(chǔ)多位的二進(jìn)制數(shù)。寄存器可以存儲(chǔ)整數(shù)、浮點(diǎn)數(shù)、字符等不同類型的數(shù)據(jù)。
計(jì)算機(jī)中的計(jì)數(shù)是通過對(duì)寄存器中的二進(jìn)制數(shù)進(jìn)行遞增或遞減來實(shí)現(xiàn)的。遞增或遞減的操作可以通過邏輯門和觸發(fā)器的組合來實(shí)現(xiàn)。例如，使用加法器電路可以實(shí)現(xiàn)二進(jìn)制數(shù)的遞增操作。
在計(jì)算機(jī)中，計(jì)數(shù)的范圍是有限的，由寄存器的位數(shù)決定。例如，一個(gè)8位寄存器可以表示0到255的整數(shù)。當(dāng)計(jì)數(shù)超過寄存器的最大值時(shí)，會(huì)發(fā)生溢出（overflow）。
除了基本的計(jì)數(shù)操作，計(jì)算機(jī)還可以執(zhí)行其他數(shù)學(xué)運(yùn)算，如加法、減法、乘法和除法。這些運(yùn)算是通過在邏輯電路中使用不同的算術(shù)電路和算法來實(shí)現(xiàn)的。
總結(jié)起來，計(jì)算機(jī)使用二進(jìn)制系統(tǒng)進(jìn)行計(jì)數(shù)，通過觸發(fā)器和寄存器來存儲(chǔ)和操作二進(jìn)制數(shù)。計(jì)算機(jī)可以執(zhí)行基本的計(jì)數(shù)操作以及其他數(shù)學(xué)運(yùn)算，通過邏輯電路和算術(shù)電路來實(shí)現(xiàn)。