聲明：本文僅限于簡書發(fā)布，其他第三方網(wǎng)站均為盜版靶草，原文地址： Python 整數(shù)數(shù)據(jù)類型的實現(xiàn)
接著之前的 《Python 對象模型》繼續(xù)看看 Python 的源代碼岳遥，之前說了派继，Python 的一切數(shù)據(jù)都是對象，甚至于不是數(shù)據(jù)都是對象绅络，例如函數(shù)啊寻行，類啊這些這些對象简卧。其實构罗，在 Python 的實現(xiàn)中遂唧，套路都差不多，無非是關注這些對象是怎么創(chuàng)建的召边，然后內(nèi)部的數(shù)據(jù)結構是怎么編排的，有什么優(yōu)化策略這些片挂，所以，我就準備不多看滋将，就看看整數(shù)的實現(xiàn)症昏。
對于 Python 整數(shù)，我開始學的時候有個很感興趣的點就是 Python 的整數(shù)居然是沒有溢出的掘宪，例如這些代碼你就可以看出來了：
有意思吧攘烛，一個整數(shù)左移了 100 位都沒溢出，我想你肯定不會說內(nèi)部是用一個 128 位的數(shù)據(jù)類型來實現(xiàn)的鼠次，好像現(xiàn)在 C 語言中也還沒這個類型吧芋齿？
整數(shù)的內(nèi)部結構
之前一篇文章說過啦，整數(shù)的數(shù)據(jù)結構是 PyLongObject赦役，沒說也至少提到過栅炒，所以我就直接看這個數(shù)據(jù)結構好啦：
很簡單赢赊，可以看到數(shù)據(jù)是保存到了一個指針(這里定義的是一個元素為1的數(shù)組释移，似乎是 C 語言里面的慣用套路)里頭秀鞭，然后這個數(shù)據(jù)長度是放在 PyOBject_VAR_HEAD 里面的啦扛禽，后面會看到關于他的操作。
新建和刪除一個整數(shù)
新建和刪除一個整數(shù)在 Python 里面是有一點點優(yōu)化的豆巨，類似于 Java掐场，對于小整數(shù)贩猎，Python 會在啟動的時候先創(chuàng)建好萍膛，后面要用的時候就不用創(chuàng)建了蝗罗，直接增加引用計數(shù)即可，放在你也改變不了一個整數(shù)的值（不可變對象）串塑，至于小整數(shù)的定義，看代碼中的這個值：
這里也就是將 [-5, 257) 范圍內(nèi)的整數(shù)都定義為小整數(shù)打瘪。所以創(chuàng)建的時候闺骚，如果數(shù)字是這個返回就直接返回已經(jīng)創(chuàng)建好的對象了：
這是定義的一個檢查小整數(shù)的宏屋匕，在創(chuàng)建整數(shù)對象的時候都會先檢驗一遍，然后不是小整數(shù)才會做其他整數(shù)的操作：
這里 Line 44 就是檢查并且返回小整數(shù)的宏进泼，實現(xiàn)就很簡單了纤虽，再來看看其他整數(shù)是怎么操作的逼纸，我們前面看到了，整數(shù)都是被拆到一個個 digit 里面的杰刽，digit 的大小不確定，可能是 15 bit 或者 30 bit滓鸠。所以這里第一步是先確定需要多少個 digit第喳，Line49 就是在計算，然后 Line 52 就創(chuàng)建對應長度的對象悠抹，因為我們說了，digit 是一個數(shù)組啤挎，需要調(diào)節(jié)它的長度卵凑。然后 Line 58 就是拆分保存數(shù)據(jù)了。
這里還有一點沒高亮的是 Line 55氛谜，這里將這個整數(shù)的正負保存在 ob_size 這個字段值漫，而不是保存在 digit 里面，也就是說 digit 里面保存的是數(shù)字的絕對值杨何，這樣有什么好處危虱？操作方便啊，加減乘除都不需要擔心符號的問題埃跷，而且拆分也是大膽得拆，不需要考慮符號問題垃帅。
整數(shù)的加減乘除
整數(shù)這么創(chuàng)建的話剪勿，加減我們就比較簡單得可以猜到了，就是直接加和直接減少酱固，來點簡單的代碼吧：
可以看到运悲，就兩個循環(huán)髓窜，一個個 digit 得加，唯一需要注意的就是 長度 和 進位 的問題寄纵。加減是簡單，但是乘除就復雜了定踱，乘法的我還能看得明白一些恃鞋，除法的我直接就放棄了，很復雜畅哑，引用注釋的一段話：
/* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
edn.), section 4.3.1, Algorithm D], except that we don't explicitly
handle the special case when the initial estimate q for a quotient
digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
that won't overflow a digit. */
那就記錄點我看懂了的乘法吧水由，因為它將整數(shù)拆成一個個 digit，所以乘法也就是一個個 digit 來乘泥张，我們可以想象一下小學的時候學的乘法：
這是 10進制的嘛媚创，然后我們可以將一個 digit 當成一位彤恶，也是可以實現(xiàn)的，但是声离，就是更復雜了一些，為了減少一些乘法操作焕议，Python 進行了一點點的優(yōu)化：
/* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
* Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
* Then the original product is
* ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
* By picking X to be a power of 2, "*X" is just shifting, and it's
* been reduced to 3 multiplies on numbers half the size.
*/
這里的目的就是將大的整數(shù)的乘法轉化成小一半的整數(shù)的乘法盅安，從而減少真正乘法的規(guī)模和次數(shù)世囊，同時，這里的 X 因為是 2 的倍數(shù)株憾，所以直接移位就可以了，效率不能更高墙歪，所以真正的乘法就變少了。
