深入分析python中整型不會溢出問題

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

#define PyLong_SHIFT 15
#define PyLong_BASE ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK ((digit)(PyLong_BASE - 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; // 進(jìn)位
  
  // 確保a是兩個加數(shù)中較大的一個
  if (size_a < size_b) {
    // 交換兩個加數(shù)
    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位, 得到進(jìn)位
  }
  for (; i < size_a; ++i) {          // 單獨(dú)處理a中高位數(shù)字
    carry += a->ob_digit[i];
    z->ob_digit[i] = carry & PyLong_MASK;
    carry >>= PyLong_SHIFT;
  }
  z->ob_digit[i] = carry;
  return long_normalize(z);          // 整理元素個數(shù)
  
}

// 為方便理解，會與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 的數(shù)組清 0
  
  for (i = 0; i < size_b; ++i) {
    int carry = 0;     // 用一個int保存元素之間的乘法結(jié)果
    int f = b->ob_digit[i]; // 當(dāng)前乘數(shù)b的元素
    
    // 創(chuàng)建一個臨時變量，保存當(dāng)前元素的計算結(jié)果，用于累加
    PyLongObject *temp = _PyLong_New(size_a + size_b);
    memset(temp->ob_digit, 0, len(temp) * sizeof(int)); // temp 的數(shù)組清 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; // 保留進(jìn)位
      pz ++;
    }
    if (carry){   // 處理進(jìn)位
      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
  
}

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

# 例子中的表格中，數(shù)組元素最多存放3位整數(shù)，因此這邊設(shè)置1000
# 對應(yīng)的取低位與取高位也就變成對 1000 取模和取余操作
PyLong_SHIFT = 1000
PyLong_MASK = 999

# 以15位長度的二進(jìn)制
# PyLong_SHIFT = 15
# PyLong_MASK = (1 << 15) - 1

def long_normalize(num):
  """
  去掉多余的空間，調(diào)整數(shù)組的到正確的長度
  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 是兩個加數(shù)較大的，較大指的是元素的個數(shù)
  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

  # 去掉多余的空間，數(shù)組長度調(diào)整至正確的數(shù)量
  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]

    # 創(chuàng)建一個臨時變量
    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:  # 處理進(jìn)位
      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))