Python大整数原理：基于CPython源码解析无限精度整型实现

Ryan

发布时间：2026-10-13| 6人浏览过

原创

本文深入分析Python 3中整数不溢出的底层实现机制。基于CPython解释器源码，解析长整型（PyLongObject）如何利用动态数组存储任意大小整数。详细阐述以2的15次方为基数的存储策略、加法与乘法的竖式计算逻辑，以及Karatsuba算法的优化应用，揭示Python降低大数据运算门槛的技术基础。

本次分析基于 CPython 解释器，python3.x版本

在Python 2时代，整型分为int和long两种类型，其中long类型支持任意大小的整数存储，不存在溢出问题。Python 3统一了整型类型，全部采用类似长整型的机制。这一设计使得Python在大数据运算中无需处理溢出，也无需像其他语言那样区分短整型、整型和长整型，从而降低了跨行业的学习门槛。

那么，不溢出的整型在实现上是否可行呢？

不溢出的整型的可行性

尽管C语言中整型的表示范围有限，但Python代码是以文本文件形式保存的，并非直接转化为C语言的整型。因此，需要重新定义一种数据结构来表示和存储这种新的“整型”。

如何存储呢？既然要表示任意大小的数值，就需要使用动态可变长的结构，显然数组形式能够胜任：

[longintrepr.h] struct _longobject { PyObject_VAR_HEAD int *ob_digit; };

长整型的保存形式

Python内部使用一个int数组（ob_digit[n]）来保存长整型的值。待存储数值的低位信息存放在低索引位置，高位信息存放在高索引位置。例如，要保存较大的数字123456789，假设每个int只能保存3位：

ob_digit[0] = 789;
ob_digit[1] = 456;
ob_digit[2] = 123;

低索引保存低位，那么每个int元素保存多大的数合适？有观点认为数组中每个int应存放其上限（2^31 - 1），这样表示大数时数组长度更短，更省空间。虽然空间确实节省了，但操作代码会变得复杂，例如大数做乘积操作时，由于元素之间存在乘法溢出问题，还需额外考虑溢出情况。

如何改进呢？在长整型的ob_digit中，元素理论上可以保存32位int类型，但我们只保存15位，这样元素之间的乘积就可以只用int类型保存，结果做位移操作就能得到尾部和进位carry，定义位移长度为15：

#define PyLong_SHIFT 15
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 1))

PyLong_MASK即0b111111111111111，通过与它做位运算与操作就能得到低位数。

有了这种存放方式，在内存空间允许的情况下，我们就可以存放任意大小的数字了。

长整型的运算

加法与乘法运算都可以使用我们小学的竖式计算方法，例如对于加法运算：

		ob_digit[2]	ob_digit[1]	ob_digit[0]
加数a		23	934	543
加数b	+		454	632
结果z		24	389	175

为方便理解，表格展示的是数组中每个元素保存的是3位十进制数，计算结果保存在变量z中，那么z的数组最多只要size_a + 1的空间（两个加数中数组较大的元素个数+1），因此对于加法运算，可以这样来处理：

[longobject.c]
static PyLongObject * x_add(PyLongObject *a, PyLongObject *b) {
  int size_a = len(a), size_b = len(b);
  PyLongObject *z;
  int i;
  int carry = 0; // 进位
  
  // 确保a是两个加数中较大的一个
  if (size_a < size_b) {
    // 交换两个加数
    swap(a, b);
    swap(&size_a, &size_b);
  }
  
  z = _PyLong_New(size_a + 1); // 申请一个能容纳size_a+1个元素的长整型对象
  for (i = 0; i < size_b; ++i) {
    carry += a->ob_digit[i] + b->ob_digit[i];
    z->ob_digit[i] = carry & PyLong_MASK;  // 掩码
    carry >>= PyLong_SHIFT;         // 移除低15位, 得到进位
  }
  for (; i < size_a; ++i) {          // 单独处理a中高位数字
    carry += a->ob_digit[i];
    z->ob_digit[i] = carry & PyLong_MASK;
    carry >>= PyLong_SHIFT;
  }
  z->ob_digit[i] = carry;
  return long_normalize(z);          // 整理元素个数
  
}

这部分的过程就是，先将两个加数中长度较长的作为第一个加数，再为用于保存结果的z申请空间，两个加数从数组从低位向高位计算，处理结果的进位，将结果的低15位赋值给z相应的位置。最后的long_normalize(z)是一个整理函数，因为我们z申请了a_size + 1的空间，但不意味着z会全部用到，因此这个函数会做一些调整，去掉多余的空间，数组长度调整至正确的数量，若不方便理解，附录将给出更利于理解的python代码。

竖式计算不是按个位十位来计算的吗，为什么这边用整个元素？

竖式计算方法适用于任何进制的数字，我们可以这样来理解，这是一个32768（2的15次方）进制的，那么就可以把数组索引为0的元素当做是“个位”，索引1的元素当做是“十位”。

乘法运算

乘法运算一样可以用竖式的计算方式，两个乘数相乘，存放结果的z的元素个数为size_a + size_b即可：

	操作			ob_digit[2]	ob_digit[1]	ob_digit[0]
乘数a				23	934	543
乘数b	*				454	632
结果z			15	126	631	176
		10	866	282	522
结果z		10	881	409	153	176

这里需要注意的是，当乘数b用索引i的元素进行计算时，结果z也是从i索引开始保存。先创建z并初始化为0，在z上做累加操作，加法运算则可以利用前面的x_add函数：

// 为方便理解，会与cpython中源码部分稍有不同
static PyLongObject * x_mul(PyLongObject *a, PyLongObject *b)
{
  int size_a = len(a), size_b = len(b);
  PyLongObject *z = _PyLong_New(size_a + size_b);
  memset(z->ob_digit, 0, len(z) * sizeof(int)); // z 的数组清 0
  
  for (i = 0; i < size_b; ++i) {
    int carry = 0;     // 用一个int保存元素之间的乘法结果
    int f = b->ob_digit[i]; // 当前乘数b的元素
    
    // 创建一个临时变量，保存当前元素的计算结果，用于累加
    PyLongObject *temp = _PyLong_New(size_a + size_b);
    memset(temp->ob_digit, 0, len(temp) * sizeof(int)); // temp 的数组清 0
    
    int pz = i; // 存放到临时变量的低位
    
    for (j = 0; j < size_a; ++j) {
      carry = f * a[j] + carry;
      temp[pz] = carry & PyLong_MASK; // 取低15位
      carry = carry >> PyLong_SHIFT; // 保留进位
      pz ++;
    }
    if (carry){   // 处理进位
      carry += temp[pz];
      temp[pz] = carry & PyLong_MASK;
      carry = carry >> PyLong_SHIFT;
    }
    if (carry){
      temp[pz] += carry & PyLong_MASK;
    }
    temp = long_normalize(temp);
    z = x_add(z, temp);
  }
  
  return z
  
}

这大致就是乘法的处理过程，竖式乘法的复杂度是n^2，当数字非常大的时候（数组元素个数超过70个）时，python会选择性能更好，更高效的Karatsuba multiplication乘法运算方式，这种的算法复杂度是3nlog3≈3n1.585，当然这种计算方法已经不是今天讨论的内容了。有兴趣的小伙伴可以去了解下。

总结

要想支持任意大小的整数运算，首先要找到适合存放整数的方式，本篇介绍了用int数组来存放，当然也可以用字符串来存储。找到合适的数据结构后，要重新定义整型的所有运算操作，本篇虽然只介绍了加法和乘法的处理过程，但其实还需要做很多的工作诸如减法，除法，位运算，取模，取余等。

python代码以文本形式存放，因此最后，还需要一个将字符串形式的数字转换成这种整型结构：

[longobject.c]
PyObject * PyLong_FromString(const char *str, char **pend, int base)
{
}

这部分不是本篇的重点，有兴趣的同学可以看看这个转换的过程。

参考：https://github.com/python/cpython/blob/master/Objects/longobject.c

附录

# 例子中的表格中，数组元素最多存放3位整数，因此这边设置1000
# 对应的取低位与取高位也就变成对 1000 取模和取余操作
PyLong_SHIFT = 1000
PyLong_MASK = 999

# 以15位长度的二进制
# PyLong_SHIFT = 15
# PyLong_MASK = (1 << 15) - 1

def long_normalize(num):
  """
  去掉多余的空间，调整数组的到正确的长度
  eg: [176, 631, 0, 0] ==> [176, 631]
  :param num:
  :return:
  """
  end = len(num)
  while end >= 1:
    if num[end - 1] != 0:
      break
    end -= 1

  num = num[:end]
  return num

def x_add(a, b):
  size_a = len(a)
  size_b = len(b)
  carry = 0

  # 确保 a 是两个加数较大的，较大指的是元素的个数
  if size_a < size_b:
    size_a, size_b = size_b, size_a
    a, b = b, a

  z = [0] * (size_a + 1)
  i = 0
  while i < size_b:
    carry += a[i] + b[i]
    z[i] = carry % PyLong_SHIFT
    carry //= PyLong_SHIFT
    i += 1

  while i < size_a:
    carry += a[i]
    z[i] = carry % PyLong_SHIFT
    carry //= PyLong_SHIFT
    i += 1
  z[i] = carry

  # 去掉多余的空间，数组长度调整至正确的数量
  z = long_normalize(z)

  return z


def x_mul(a, b):
  size_a = len(a)
  size_b = len(b)
  z = [0] * (size_a + size_b)

  for i in range(size_b):
    carry = 0
    f = b[i]

    # 创建一个临时变量
    temp = [0] * (size_a + size_b)
    pz = i
    for j in range(size_a):
      carry += f * a[j]
      temp[pz] = carry % PyLong_SHIFT
      carry //= PyLong_SHIFT
      pz += 1

    if carry:  # 处理进位
      carry += temp[pz]
      temp[pz] = carry % PyLong_SHIFT
      carry //= PyLong_SHIFT
      pz += 1

    if carry:
      temp[pz] += carry % PyLong_SHIFT
    temp = long_normalize(temp)
    z = x_add(z, temp)  # 累加

  return z


a = [543, 934, 23]
b = [632, 454]
print(x_add(a, b))
print(x_mul(a, b))