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 < a
    if (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位
}

📝 9. 字符串转换实现

9.1 数值转字符串

9.2 字符串转数值

🏁 总结

Int128类的实现展示了以下核心技术：

1. 紧凑存储结构：16字节内存布局
2. 算术运算实现：
   • 加法：溢出检测与进位处理
   • 减法：补码转换技巧
   • 乘法：32位块分解与进位链
   • 除法：Knuth算法D与归一化技术
3. 位运算实现：
   • 移位：块处理与跨块位移
   • 逻辑运算：分高低位处理
4. 辅助算法：
   • 归一化提高数值稳定性
   • 有效长度计算优化性能
5. 类型转换：
   • 显式转换保证安全性
   • 低64位截断处理