C++ Int128 —— 128位有符号整数类实现剖析

🧠 C++ Int128 —— 128位有符号整数类实现剖析

引用：openppp2/ppp/Int128.h

🏗️ 1. 存储结构设计

内存布局解析

0        64       128 (位)
┌────────┬────────┐
│   lo   │   hi   │
└────────┴────────┘

设计特点：

#pragma pack(push, 1) 确保16字节紧凑存储
低64位(lo)使用无符号类型处理纯数据
高64位(hi)使用有符号类型处理数值符号
构造函数覆盖所有基础整数类型

➕ 2. 加法运算实现

算法流程图

代码实现详解

inline Int128 operator+(const Int128& left, const Int128& right)
{Int128 value; // 创建临时结果对象value.lo = left.lo + right.lo; // 计算低64位和// 检测低64位是否溢出// 无符号数溢出时：a + b < aif (value.lo < left.lo) {value.hi = left.hi + right.hi + 1; // 进位处理} else {value.hi = left.hi + right.hi; // 无进位}return value;
}

关键技术点：

无符号整数溢出检测：a + b < a
进位处理：高64位额外加1
时间复杂度：O(1)，性能接近原生加法

➖ 3. 减法运算实现

算法流程图

取负操作实现

inline Int128 Int128::operator-() const
{Int128 x = *this; // 创建副本x.Negate(); // 执行取反操作return x;
}void Int128::Negate()
{hi = ~hi; // 高64位按位取反lo = ~lo; // 低64位按位取反(*this) += 1; // 加1完成补码转换
}

减法运算符实现

inline Int128 operator-(const Int128& left, const Int128& right)
{return left + (-right); // 利用补码原理：a - b = a + (-b)
}

关键技术点：

基于补码原理实现减法
取负操作：按位取反后加1
边界情况处理：最小负数取负后仍为自身

✖️ 4. 乘法运算实现

算法流程图

代码实现详解

inline Int128 Int128::Multiply(Int128 left, Int128 right)
{// 处理符号int leftSign = left.Sign(); // 获取左操作数符号left = leftSign < 0 ? -left : left; // 转换为正数int rightSign = right.Sign(); // 获取右操作数符号right = rightSign < 0 ? -right : right; // 转换为正数// 分解为32位数组unsigned int xInts[4]; // 左操作数32位数组unsigned int yInts[4]; // 右操作数32位数组memcpy(xInts, &left.lo, 16); // 复制内存memcpy(yInts, &right.lo, 16); // 复制内存unsigned int mulInts[8] = {0}; // 乘积结果数组// 双层循环乘法for (int i = 0; i < 4; i++) {unsigned long long carry = 0; // 进位值for (int j = 0; j < 4; j++) {// 计算32位块乘积unsigned long long product = (unsigned long long)xInts[i] * yInts[j];// 累加乘积和进位unsigned long long sum = product + mulInts[i+j] + carry;// 存储低32位mulInts[i+j] = (unsigned int)sum;// 计算新进位carry = sum >> 32;}// 处理剩余进位int k = i + 4;while (carry) {unsigned long long sum = (unsigned long long)mulInts[k] + carry;mulInts[k] = (unsigned int)sum;carry = sum >> 32;k++;}}// 应用符号并返回结果return Int128(leftSign * rightSign, mulInts, 8);
}

关键技术点：

32位块分解避免64位乘法溢出
小学乘法算法实现
双重循环处理所有位组合
进位链式处理

➗ 5. 除法与取模运算实现

算法流程图

核心代码实现

inline Int128 Int128::DivRem(Int128 dividend, Int128 divisor, Int128& remainder)
{// 处理除数为零if (divisor == 0) return 0;// 处理符号int dividendSign = dividend.Sign();dividend = dividendSign < 0 ? -dividend : dividend;int divisorSign = divisor.Sign();divisor = divisorSign < 0 ? -divisor : divisor;// 分解为32位数组unsigned int u[4]; // 被除数数组unsigned int v[4]; // 除数数组memcpy(u, &dividend.lo, 16);memcpy(v, &divisor.lo, 16);unsigned int quotient[4] = {0}; // 商数组unsigned int rem[4] = {0}; // 余数数组// 执行无符号除法DivModUnsigned(u, v, quotient, rem);// 构造结果remainder = Int128(1, rem, 4); // 余数return Int128(dividendSign * divisorSign, quotient, 4); // 商
}

Knuth算法D关键步骤

void Int128::DivModUnsigned(unsigned int* u, unsigned int* v, unsigned int*& q, unsigned int*& r)
{int m = GetLength(u, 4); // 被除数有效长度int n = GetLength(v, 4); // 除数有效长度if (n <= 1) {// 单字除数特殊处理unsigned long long rem = 0;unsigned int v0 = v[0];for (int j = m - 1; j >= 0; j--) {rem = (rem << 32) + u[j]; // 组合当前值q[j] = (unsigned int)(rem / v0); // 计算商rem %= v0; // 更新余数}r[0] = (unsigned int)rem;}else if (m >= n) {// 归一化int shift = GetNormalizeShift(v[n-1]);unsigned int un[4] = {0};unsigned int vn[4] = {0};Normalize(u, m, un, shift);Normalize(v, n, vn, shift);// Knuth算法D主循环for (int j = m - n; j >= 0; j--) {// 试商计算unsigned long long rr = (unsigned long long)un[j+n] * Base32 + un[j+n-1];unsigned int qhat = (unsigned int)(rr / vn[n-1]);unsigned long long rhat = rr % vn[n-1];// 试商调整while (qhat >= Base32 || (qhat * vn[n-2] > (rhat * Base32 + un[j+n-2]))) {qhat--;rhat += vn[n-1];if (rhat >= Base32) break;}// 乘减操作signed long long borrow = 0;for (int i = 0; i < n; i++) {unsigned long long p = (unsigned long long)qhat * vn[i];signed long long t = un[i+j] - borrow - (p & 0xFFFFFFFF);un[i+j] = (unsigned int)t;borrow = (p >> 32) - (t >> 32);}borrow = un[j+n] - borrow;un[j+n] = (unsigned int)borrow;// 结果调整if (borrow < 0) {qhat--;unsigned long long carry = 0;for (int i = 0; i < n; i++) {carry = (unsigned long long)vn[i] + un[i+j] + carry;un[i+j] = (unsigned int)carry;carry >>= 32;}un[j+n] += (unsigned int)carry;}// 存储商q[j] = qhat;}// 反归一化Unnormalize(un, r, shift);}else {// 被除数小于除数memset(q, 0, 16); // 商为零memcpy(r, u, 16); // 余数为被除数}
}

关键技术点：

归一化提高数值稳定性
试商算法减少迭代次数
乘减操作实现精确计算
反归一化恢复正确余数

🧮 6. 位运算实现

6.1 按位取反 (~)

inline Int128 operator~(const Int128& value)
{return Int128(~value.hi, ~value.lo); // 高低位分别取反
}

6.2 左移 (<<)

inline Int128 operator<<(const Int128& value, int shift)
{// 处理零位移if (shift == 0) return value;// 计算实际位移shift %= 128; // 规范化位移// 分解为64位块unsigned long long* values = (unsigned long long*)&value.lo;// 计算块移位和位内移位int shiftOffset = shift / 64; // 整块移位int bshift = shift % 64; // 块内移位unsigned long long shifted[2] = {0}; // 结果数组// 处理低64位if (shiftOffset == 0) {shifted[0] = values[0] << bshift;if (bshift > 0) {shifted[1] = values[0] >> (64 - bshift);}}// 处理高64位if (shiftOffset <= 1) {int idx = shiftOffset;shifted[idx] |= values[1] << bshift;if (bshift > 0 && idx < 1) {shifted[idx+1] = values[1] >> (64 - bshift);}}return Int128((signed long long)shifted[1], shifted[0]);
}

6.3 右移 (>>)

inline Int128 operator>>(const Int128& value, int shift)
{// 处理零位移if (shift == 0) return value;// 计算实际位移shift %= 128; // 规范化位移// 处理整块移位unsigned long long* values = (unsigned long long*)&value.lo;if (shift >= 64) {int blockShift = shift / 64;shift %= 64;// 移动整块values[0] = values[1];// 符号扩展values[1] = (unsigned long long)((signed long long)values[1] >> 63);}// 块内移位处理int bshift = 64 - shift; // 补位位数unsigned long long shifted[2] = {0};// 高64位处理（带符号扩展）shifted[1] = (unsigned long long)((signed long long)values[1] >> shift);// 低64位处理shifted[0] = values[0] >> shift;if (shift > 0) {shifted[0] |= values[1] << bshift;}return Int128((signed long long)shifted[1], shifted[0]);
}

6.4 按位与 (&)、或 (|)、异或 (^)

// 按位与
inline Int128 operator&(const Int128& left, const Int128& right)
{return Int128(left.hi & right.hi, left.lo & right.lo);
}// 按位或
inline Int128 operator|(const Int128& left, const Int128& right)
{return Int128(left.hi | right.hi, left.lo | right.lo);
}// 按位异或
inline Int128 operator^(const Int128& left, const Int128& right)
{return Int128(left.hi ^ right.hi, left.lo ^ right.lo);
}

🛠️ 7. 关键辅助算法实现

7.1 归一化技术

inline void Int128::Normalize(unsigned int* u, int l, unsigned int* un, int shift)
{unsigned int carry = 0; // 进位值if (shift > 0) {int rshift = 32 - shift; // 右移位数for (int i = 0; i < l; i++) {unsigned int ui = u[i]; // 当前值un[i] = (ui << shift) | carry; // 左移并合并进位carry = ui >> rshift; // 计算新进位}// 处理剩余进位if (carry != 0) {un[l] = carry;}} else {// 无移位直接复制for (int i = 0; i < l; i++) {un[i] = u[i];}}
}

7.2 长度计算

inline int Int128::GetLength(unsigned int* uints, int uintslen)
{int index = uintslen - 1; // 从最高位开始// 跳过前导零while (index >= 0 && uints[index] == 0) {index--;}return index + 1; // 返回有效长度
}

🔄 8. 类型转换实现

在这里插入图片描述

// 布尔转换
inline Int128::operator bool() const
{return lo != 0 || hi != 0; // 任意位非零即为真
}// 64位整数转换
inline Int128::operator unsigned long long() const
{return lo; // 仅使用低64位
}// 32位整数转换
inline Int128::operator unsigned int() const
{return (unsigned int)lo; // 截断到32位
}