第5章：Int128 高精度整数运算

5.1 概述

在多边形裁剪算法中，计算两条边的交点需要进行乘法运算。当使用 64 位整数坐标时，两个 64 位整数相乘可能产生 128 位的中间结果。为了避免溢出并保持精度，Clipper1 实现了一个自定义的 128 位整数结构 Int128。

5.2 为什么需要 Int128

5.2.1 溢出问题示例

考虑计算两条边是否共线的判断：

// 判断三点是否共线
// 使用叉积：(pt1-pt2) × (pt2-pt3) = 0
// 展开：(pt1.Y - pt2.Y) * (pt2.X - pt3.X) == (pt1.X - pt2.X) * (pt2.Y - pt3.Y)

// 假设坐标范围接近 Int64.MaxValue
long a = 4611686018427387903L;  // 接近 loRange
long b = 4611686018427387902L;
long c = a * b;  // 溢出！

5.2.2 坐标范围与溢出

坐标范围	乘积范围	是否溢出
≤ 46,340 (Int32 安全范围)	≤ 2.1×10⁹	否（Int64 可容纳）
≤ 10⁹ (loRange)	≤ 10¹⁸	否（Int64 可容纳）
≤ 10¹⁸ (hiRange)	≤ 10³⁶	是（需要 Int128）

5.3 Int128 结构定义

internal struct Int128
{
    private Int64 hi;   // 高 64 位（有符号）
    private UInt64 lo;  // 低 64 位（无符号）

    public Int128(Int64 _lo)
    {
        lo = (UInt64)_lo;
        if (_lo < 0) hi = -1;  // 符号扩展
        else hi = 0;
    }

    public Int128(Int64 _hi, UInt64 _lo)
    {
        lo = _lo;
        hi = _hi;
    }

    public Int128(Int128 val)
    {
        hi = val.hi;
        lo = val.lo;
    }
}

5.3.1 内存布局

Int128 结构（16 字节）：
┌────────────────────────────────────────────────────────────────┐
│                           hi (Int64)                           │
│  符号位 │              高63位数值                              │
├────────────────────────────────────────────────────────────────┤
│                           lo (UInt64)                          │
│                         低64位数值                             │
└────────────────────────────────────────────────────────────────┘
总范围：-2¹²⁷ 到 2¹²⁷-1

5.3.2 符号扩展

从 Int64 构造 Int128 时，需要正确处理负数：

public Int128(Int64 _lo)
{
    lo = (UInt64)_lo;
    if (_lo < 0) 
        hi = -1;  // 全1（0xFFFFFFFFFFFFFFFF），表示负数扩展
    else 
        hi = 0;   // 全0，表示正数
}

示例：

Int64 值: -1 = 0xFFFFFFFFFFFFFFFF
Int128 表示: hi = 0xFFFFFFFFFFFFFFFF, lo = 0xFFFFFFFFFFFFFFFF
             = -1 (128位)

Int64 值: 100
Int128 表示: hi = 0x0000000000000000, lo = 0x0000000000000064
             = 100 (128位)

5.4 符号判断

public bool IsNegative()
{
    return hi < 0;
}

原理：128 位有符号整数的最高位（hi 的符号位）决定整体符号。

5.5 相等性比较

public static bool operator ==(Int128 val1, Int128 val2)
{
    if ((object)val1 == (object)val2) return true;
    else if ((object)val1 == null || (object)val2 == null) return false;
    return (val1.hi == val2.hi && val1.lo == val2.lo);
}

public static bool operator !=(Int128 val1, Int128 val2)
{
    return !(val1 == val2);
}

public override bool Equals(System.Object obj)
{
    if (obj == null || !(obj is Int128))
        return false;
    Int128 i128 = (Int128)obj;
    return (i128.hi == hi && i128.lo == lo);
}

public override int GetHashCode()
{
    return hi.GetHashCode() ^ lo.GetHashCode();
}

5.6 大小比较

public static bool operator >(Int128 val1, Int128 val2)
{
    if (val1.hi != val2.hi)
        return val1.hi > val2.hi;  // 先比较高位
    else
        return val1.lo > val2.lo;  // 高位相同则比较低位
}

public static bool operator <(Int128 val1, Int128 val2)
{
    if (val1.hi != val2.hi)
        return val1.hi < val2.hi;
    else
        return val1.lo < val2.lo;
}

比较逻辑：

首先比较 hi（有符号比较）
- 如果 hi 不同，直接得出结果
- 负数的 hi < 0，正数的 hi >= 0
如果 hi 相同，比较 lo（无符号比较）
- 此时两个数符号相同，直接比较 lo

示例：

A = (hi=0, lo=100)   // = 100
B = (hi=0, lo=200)   // = 200
A < B 因为 hi 相同，100 < 200

C = (hi=-1, lo=max)  // = -1
D = (hi=0, lo=1)     // = 1
C < D 因为 -1 < 0

5.7 加法运算

public static Int128 operator +(Int128 lhs, Int128 rhs)
{
    lhs.hi += rhs.hi;
    lhs.lo += rhs.lo;
    if (lhs.lo < rhs.lo) lhs.hi++;  // 处理低位进位
    return lhs;
}

5.7.1 进位处理

    lhs.lo = 0xFFFFFFFFFFFFFFFF (最大无符号64位)
  + rhs.lo = 0x0000000000000001
  ─────────────────────────────
  结果.lo = 0x0000000000000000 (溢出，产生进位)
  
  检测方法：如果 lhs.lo < rhs.lo，说明发生了溢出
           需要将 hi 加 1 来处理进位

5.7.2 加法示例

// 大数加法
Int128 a = new Int128(0, 0xFFFFFFFFFFFFFFFF);  // 2^64 - 1
Int128 b = new Int128(0, 1);                    // 1
Int128 c = a + b;  // c.hi = 1, c.lo = 0       // = 2^64

5.8 取负运算

public static Int128 operator -(Int128 val)
{
    if (val.lo == 0)
        return new Int128(-val.hi, 0);
    else
        return new Int128(~val.hi, ~val.lo + 1);
}

5.8.1 补码取反原理

对于补码表示的整数，取负操作等价于”按位取反后加1”：

原值:  val = (hi, lo)
取反:  ~val = (~hi, ~lo)
加1:   -val = (~hi, ~lo + 1)

特殊情况：当 lo = 0 时
  - ~lo + 1 会产生溢出，变回 0
  - 需要向 hi 进位
  - 简化为 (-hi, 0)

5.8.2 取负示例

// 正数取负
Int128 pos = new Int128(0, 100);   // = 100
Int128 neg = -pos;                  // = -100
// neg.hi = ~0 = -1, neg.lo = ~100 + 1 = -100（作为无符号数）

// lo = 0 的特殊情况
Int128 a = new Int128(5, 0);       // = 5 * 2^64
Int128 b = -a;                      // = -5 * 2^64
// b.hi = -5, b.lo = 0

5.9 减法运算

public static Int128 operator -(Int128 lhs, Int128 rhs)
{
    return lhs + -rhs;
}

减法通过取负后加法实现，简化了代码。

5.10 转换为 double

public static explicit operator double(Int128 val)
{
    const double shift64 = 18446744073709551616.0; // 2^64
    if (val.hi < 0)
    {
        if (val.lo == 0)
            return (double)val.hi * shift64;
        else
            return -(double)(~val.lo + ~val.hi * shift64);
    }
    else
        return (double)(val.lo + val.hi * shift64);
}

5.10.1 转换原理

128 位整数可以表示为：value = hi * 2^64 + lo

// 正数转换
double result = (double)lo + (double)hi * (2^64);

// 负数转换
// 需要先计算绝对值，再取负
// |val| = ~val + 1 = ~lo + 1 + ~hi * 2^64
// 简化：|val| ≈ ~lo + ~hi * 2^64（忽略+1的精度影响）
double result = -((double)(~lo) + (double)(~hi) * (2^64));

5.10.2 精度说明

double 只有 53 位有效数字，无法精确表示所有 128 位整数值。这个转换主要用于：

调试输出
近似计算
最终结果转换

5.11 核心乘法：Int128Mul

这是 Int128 最重要的方法，用于计算两个 64 位整数的 128 位乘积：

public static Int128 Int128Mul(Int64 lhs, Int64 rhs)
{
    // 处理符号
    bool negate = (lhs < 0) != (rhs < 0);
    if (lhs < 0) lhs = -lhs;
    if (rhs < 0) rhs = -rhs;
    
    // 将 64 位分解为两个 32 位部分
    UInt64 int1Hi = (UInt64)lhs >> 32;
    UInt64 int1Lo = (UInt64)lhs & 0xFFFFFFFF;
    UInt64 int2Hi = (UInt64)rhs >> 32;
    UInt64 int2Lo = (UInt64)rhs & 0xFFFFFFFF;

    // 计算四个部分乘积
    UInt64 a = int1Hi * int2Hi;
    UInt64 b = int1Lo * int2Lo;
    UInt64 c = int1Hi * int2Lo + int1Lo * int2Hi;

    // 组合结果
    UInt64 lo;
    Int64 hi;
    hi = (Int64)(a + (c >> 32));

    unchecked { lo = (c << 32) + b; }
    if (lo < b) hi++;
    
    Int128 result = new Int128(hi, lo);
    return negate ? -result : result;
}

5.11.1 算法图解

将 64 位整数分解为高低 32 位后，乘法可以表示为：

         int1Hi    int1Lo
       ×  int2Hi    int2Lo
       ─────────────────────
                   b = int1Lo × int2Lo    (0-64位)
         c1 = int1Hi × int2Lo             (32-96位)
         c2 = int1Lo × int2Hi             (32-96位)
       a = int1Hi × int2Hi                (64-128位)
       ─────────────────────
                   最终 128 位结果

位置分布：
|----a----|----c----|----b----|
    96-128   32-96     0-64
            (c需要分拆到高位和低位)

5.11.2 关键步骤解析

步骤1：符号处理

bool negate = (lhs < 0) != (rhs < 0);  // 异或判断结果符号
if (lhs < 0) lhs = -lhs;  // 转为正数计算
if (rhs < 0) rhs = -rhs;

步骤2：分解为 32 位

UInt64 int1Hi = (UInt64)lhs >> 32;    // 高32位
UInt64 int1Lo = (UInt64)lhs & 0xFFFFFFFF;  // 低32位

步骤3：计算部分乘积

UInt64 a = int1Hi * int2Hi;  // 高×高，结果在位置 64-128
UInt64 b = int1Lo * int2Lo;  // 低×低，结果在位置 0-64
UInt64 c = int1Hi * int2Lo + int1Lo * int2Hi;  // 交叉项，位置 32-96

步骤4：组合结果

// hi 包含：a（完整）+ c的高32位
hi = (Int64)(a + (c >> 32));

// lo 包含：b（完整）+ c的低32位（左移32位后）
unchecked { lo = (c << 32) + b; }

// 处理低位加法的进位
if (lo < b) hi++;

5.11.3 为什么不直接使用乘法运算符

源代码注释解释了这一点：

//nb: Constructing two new Int128 objects every time we want to multiply longs  
//is slow. So, although calling the Int128Mul method doesn't look as clean, the 
//code runs significantly faster than if we'd used the * operator.

即：每次乘法都创建两个 Int128 对象会很慢，直接使用静态方法更高效。

5.12 在 Clipper 中的使用

5.12.1 斜率比较

internal static bool SlopesEqual(TEdge e1, TEdge e2, bool UseFullRange)
{
    if (UseFullRange)
        return Int128.Int128Mul(e1.Delta.Y, e2.Delta.X) ==
               Int128.Int128Mul(e1.Delta.X, e2.Delta.Y);
    else 
        return (cInt)(e1.Delta.Y) * (e2.Delta.X) ==
               (cInt)(e1.Delta.X) * (e2.Delta.Y);
}

5.12.2 点在线段上的判断

internal bool PointOnLineSegment(IntPoint pt, 
    IntPoint linePt1, IntPoint linePt2, bool UseFullRange)
{
    if (UseFullRange)
        // 使用 Int128 进行精确计算
        return /* ... */ &&
          ((Int128.Int128Mul((pt.X - linePt1.X), (linePt2.Y - linePt1.Y)) ==
          Int128.Int128Mul((linePt2.X - linePt1.X), (pt.Y - linePt1.Y))));
    else
        // 使用普通 64 位计算
        return /* ... */ &&
          ((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) ==
            (linePt2.X - linePt1.X) * (pt.Y - linePt1.Y));
}

5.12.3 UseFullRange 标志

void RangeTest(IntPoint Pt, ref bool useFullRange)
{
    if (useFullRange)
    {
        if (Pt.X > hiRange || Pt.Y > hiRange || 
            -Pt.X > hiRange || -Pt.Y > hiRange) 
            throw new ClipperException("Coordinate outside allowed range");
    }
    else if (Pt.X > loRange || Pt.Y > loRange || 
             -Pt.X > loRange || -Pt.Y > loRange) 
    {
        useFullRange = true;  // 自动升级到高精度模式
        RangeTest(Pt, ref useFullRange);
    }
}

5.13 性能考虑

5.13.1 何时使用 Int128

条件	使用类型	性能
坐标 ≤ loRange	Int64	快
坐标 > loRange 且 ≤ hiRange	Int128	较慢（约2-3倍）
坐标 > hiRange	异常	N/A

5.13.2 优化建议

尽量使用小坐标：如果应用场景允许，将坐标缩放到 loRange 范围内
避免不必要的精度：对于不需要极高精度的应用，使用较小的比例因子
预处理坐标：在添加到 Clipper 之前检查并调整坐标范围

// 检查是否需要高精度
bool NeedsHighPrecision(Paths paths)
{
    foreach (var path in paths)
        foreach (var pt in path)
            if (Math.Abs(pt.X) > ClipperBase.loRange || 
                Math.Abs(pt.Y) > ClipperBase.loRange)
                return true;
    return false;
}

// 坐标缩放以避免高精度
double scale = 1.0;
if (NeedsHighPrecision(paths))
{
    // 找到最大坐标
    long maxCoord = 0;
    foreach (var path in paths)
        foreach (var pt in path)
        {
            maxCoord = Math.Max(maxCoord, Math.Abs(pt.X));
            maxCoord = Math.Max(maxCoord, Math.Abs(pt.Y));
        }
    
    // 计算缩放因子
    scale = (double)ClipperBase.loRange / maxCoord;
    
    // 应用缩放
    ScalePaths(paths, scale);
}

5.14 本章小结

本章详细分析了 Clipper1 的 Int128 高精度整数实现：

设计目的：避免 64 位乘法的溢出问题
结构设计：
- 使用 hi（有符号）+ lo（无符号）表示 128 位
- 正确处理符号扩展
核心运算：
- 加法：处理低位进位
- 取负：补码取反加1
- 乘法：将 64 位分解为 32 位部分相乘
关键方法：Int128Mul 实现两个 64 位整数的精确乘法
自动切换：当坐标超过 loRange 时自动启用高精度模式

理解 Int128 的实现有助于理解 Clipper 如何在保持高精度的同时处理大范围坐标。

上一章：枚举类型与常量

返回目录

下一章：ClipperBase基类详解