作为支持程度横跨从上世纪的Delphi 5到现阶段最新的RAD Studio 12的CnVCL组件包，尤其是加解密库，内部势必要实现扎实的各类运算支持，其中首当其冲就包括64位整数的运算。

Delphi的32位编译器天然支持32位有符号数及32位无符号数的运算，也就是说Integer和Cardinal型的变量，直接声明并加减乘除和比较，一点问题也没有，无需额外写代码。64位有符号整数用Int64也能同样操作，也不用我们操心，但当我们考虑64位无符号整数的时候，问题来了……

Delphi 5、6、7里，竟然没有UInt64类型！只有Delphi 2005及以上版本才有。

怎么办？在Delphi 5、6、7里，那只有自己动手、丰衣足食了。

首先，用什么表示64位无符号整数？

如果Delphi连Int64都不支持，那么就得被迫完全用32位来模拟，本文的复杂度就会立马上升一个数量级，就像用64位整数实现128位整数运算支持一样（别说，这个我们还真实现了，届时另起一篇文章说明）。

好在手头的Delphi版本再低也有Int64类型，从数字声明、存储方面，可以用Int64来代替UInt64，至少它们都是64位的。

我们新声明了一个类型叫TUInt64，它在Delphi 7或以下版本等于Int64，其余高版本则等于UInt64，声明如下：

  {$IFDEF SUPPORT_UINT64}
    TUInt64          = UInt64;
    {$IFNDEF SUPPORT_PUINT64}
    PUInt64          = ^UInt64;
    {$ENDIF}
  {$ELSE}
    TUInt64          = Int64;
    PUInt64          = ^TUInt64;
  {$ENDIF}

其次，64位整数的加减如何支持？

运算不外乎加、减、乘、除、求余、比较，以及和字符串等互相转换。其中，加和减是比较好办的。为什么？因为我们通用的计算机体系里，整数用“补码”表示，而补码的特性决定了，无论你是有符号数，还是无符号数，加减起来都……一样。

听起来是不是很神奇？

念过计算机基础课程的朋友们可能还记得，普通的0或正整数，表示成二进制很容易，甚至手工用除二记余法就能做出来，比如我们要将十进制的35转为二进制的话：

  35 ÷ 2 = 17 ... 余数 1

这里我们得到的第一个余数是1，这是二进制数的最低有效位（Least Significant Bit, LSB）。

  17 ÷ 2 = 8 ... 余数 1

第二个余数也是1。

  8 ÷ 2 = 4 ... 余数 0

第三个余数是0。

  4 ÷ 2 = 2 ... 余数 0

第四个余数是0。

  2 ÷ 2 = 1 ... 余数 0

第五个余数是0。

  1 ÷ 2 = 0 ... 余数 1

最后一个余数是1，这是二进制数的最高有效位（Most Significant Bit, MSB）。

现在我们将所有的余数从最后一个到第一个逆序排列：100011，所以，十进制数35转换为二进制数就是100011。

以上很好理解，可有没发觉缺了点什么？

对，没有负数的支持。

负数的负只是一个符号，并不属于数字本身，十进制数字也只能在前面加一横表示它是负的。但在计算机里都是二进制位，没地儿直接加这个横，所以人们研究出了好几种方法来表示这一横，这就是计算机基础课程里提到的“原码”、“反码”和“补码”规则，其中前两者其实是失败的，现阶段几乎完全没用，我们所涉及的负整数，几乎全是补码规则。

为了理解方便，可以先从原码讲起，这是最容易想到的规则：

假设我们是32位系统，一个普通的二进制整数占32位，如果它是无符号数，那么最大可以表示2的32次方减一，数字表示范围也就是从32个0到32个1。

现在我们要记录符号，就单独拎出最高位，规定它代表符号，不算数。剩下31个二进制位用来表示这个数的绝对值。

比如-35，用原码表示就是10000000000000000000000000100011，最高位1表示负的，后面的100011表示其绝对值是35，也很好理解。

但它为啥没用起来？理由很简单。

10000000000000000000000000000000和00000000000000000000000000000000，这两个数分别代表正0和负0，它们数学上都等于0，然而却出现了两个不同的表示方法。这在数学上可是个大漏洞！

虽然要强行弥补，在工程计算上也不是做不到，但明显增加了复杂度。

作为CPU的底层数学运算，多一些这方面的处理也会影响性能。

因此，原码就这样死在了计算机历史的长河中。

另外一种同样死掉了的方式是反码，高位仍用1表示负，和原码不同的是，当高位是1时，后面的内容不是绝对值本身，而是绝对值全取反。

比如-35的反码就是11111111111111111111111111011100。

反码的正0和负0同样有两种表示，全0和全1，照样不行。

而现阶段流行的“补码”，则是经过缜密设计而拼凑出来的负整数表示方式，简而言之，它将一个无符号数的范围，往负方向移动了一半，同时确保了负数最高位1，正数和0最高位0，并且最重要的是：正0和负0只有一种相同的表示方式，那就是全0。

举例来说（32位太长了，换8位的），一字节8位的无符号数范围是0到255，但如果以补码方式表示8位有符号数，范围就变成了-128到127，其中0到127对应00000000递增到01111111，但如果再增加1，变成10000000后，就代表-128了，后面的七个0逐步递增时，数字也从最小的-128逐步逼近0，等11111111时等于-1。

补码的口诀是“全1负1，全0是0，正负转换，求反加1。”

前两句好理解，后两句则是奇妙的计算规则。

比如1的二进制是00000001,那么-1的补码二进制就是求反加一，11111110，再加一，是11111111。

0的二进制是0，求反加一的动作是11111111，再加一进位，溢出的最高位1被丢弃，仍是00000000，确保了正0和负0拥有相同的唯一表达。

再比如128的无符号二进制是10000000，那么-128就是求反加一，就是01111111，再加一，进个位，还是10000000，是不是很奇妙？

而且，最奇妙的是，如果你拿到两个相同位数的二进制值，譬如都是8位或16位或32位，无论你将它们当成无符号整数，还是当成有符号整数，它们的加减规则与结果，刨去可能的溢出后，竟然是一模一样的！

这里仍然拿8位的单字节有符号和无符号数字来举例：

有符号数字的加法，随便找个53和-17：

  53  + (-17)  = 36
  53（十进制）= 0011 0101（二进制）
  -17（十进制）= 1110 1111（二进制）

00110101和11101111按二进制位加起来：

     0011 0101
   + 1110 1111
   --------------
    10010 0100

第9位产生了溢出，最高位的1舍弃，得到的00100110，其十进制是36，正好等于53-17的结果。

如果我们把这两个二进制值当作无符号数：

  53（十进制）仍然 = 0011 0101（二进制）
  1110 1111（二进制）则= 239（十进制）

而53+239=292，和上面的二进制运算一样产生了溢出，最高位的1舍弃，相当于减去256。

  292-256=36

同样也得到了36！

有符号整数和无符号整数的加减，在精妙的补码规则下，神奇地达到了统一！

正因为这个特性，CPU指令底层在做加减运算时，完全不需要区分被操作数是无符号数还是有符号数。x86指令集里也只有统一的、基于补码规则的ADD、SUB加减指令，并没有区分什么SigndAdd或UnsignedSub。

当然，两种运算造成的溢出、进位等标记是不同的，因而对正负、溢出的判断等机制，仍然要区分有符号数和无符号数。

用8位的例子说明了补码规则及其缜密得可以忽略符号的加减法规则，我们可以相同地外推到64位整数上。

研究结论与CnVCL中的CnNative.pas单元里的实践都证明了：我们用Int64这种1位符号位加63位数据位的格式来强行表示64位全是数据位的格式，做起加减来说，是完全通用的。

也就是说，我们可以声明var A, B, C: TUInt64; 并且直接写 C := A + B; C里就能得到64位无符号整数的和的正确结果。
但是这里还有个问题，在Delphi 7下，TUInt64可是Int64，如果我们想知道C的值，直接将C传给给IntToStr，那么，得到的字符串很可能是因为超出了Int64的范围而变成带负号的那种。

所以，我们不能直接用IntToStr打印它的值，而必须用Format('%u', []);的方式来打印它。

我们也写了一个UInt64ToStr封装这个行为。

无独有偶，如果我们有一个字符串形式的十进制数要转换成TUInt64，同样不能简单地调用StrToInt，那样对于超出Int64范围的正整数，会产生溢出错误。

我们同样写了个StrToUInt64函数来实现这个功能。

好了，加和减搞定了，那乘和除呢？

下面讲乘除法。

补码在加减法上抹平了有符号数和无符号数的区别，但遗憾的是它的威力延伸不到乘除法领域。同样两个32位或64位的整数，作为有符号数相乘除，和作为无符号数相乘除，结果即使用补码统一表示，也是完全不一样的。同样，x86指令集里的乘除法，也区分了MUL、IMUL和DIV、IDIV指令，足以说明这两个体系不同。

另外要说明，这里分析的64位无符号整数的乘法，并不是像加减法那样用两个TUInt64相乘，因为64位无符号整数相乘极易溢出64位无符号整数所能表示的最大范围，因而属于128位无符号整数乘法的研究范围。对于乘法来说，我们这里真正要处理的问题其实是：两个32位无符号数相乘，如何放入一个64位有符号中？

如果声明var A, B: Cardinal; 和 C: TUInt64; 在Delphi 7下直接写 C := A * B; 的话，如果A和B太大，导致各自超过32位有符号数的最大值，或乘积超出了Int64所能表示的最大值，它并不会像加减一样将真实的乘积搁在Int64内（哪怕它实际上以Int64解读时变成了负值），而是得到莫名其妙的错误结果，比如：

  var
    A, B: Cardinal;
    C: Int64;
  begin
    A := 2147483648;
    B := 1000000;
    C := A * B;

这段代码在Delphi 7下非但不会得到在Int64合法范围里的2147483648000000，而是得到个莫名其妙的0。查看其汇编，乘号在这里编译成了有符号乘法的IMUL指令：

  Unit1.pas.30: A := 2147483648;
  0044D111 B900000080       mov ecx,$80000000
  Unit1.pas.31: B := 1000000;
  0044D116 BE40420F00       mov esi,$000f4240
  Unit1.pas.32: C := A * B;
  0044D11B 8BC1             mov eax,ecx
  0044D11D F7EE             imul esi
  
因而并不是真正的32位无符号数乘法。

要完成32位无符号数的准确相乘，靠Delphi 7这种不支持UInt64的编译器是没指望了（须是Delphi 2005或以上支持UInt64的编译器，会编译出MUL无符号乘法指令），所幸在System.pas里我们发现有个System.@_llmul，我们分析了它的调用参数传播的规则，把它封装成了一个函数：

  function UInt64Mul(A, B: Cardinal): TUInt64;
  asm
        PUSH    0               // PUSH B 高位 0
        PUSH    EDX             // PUSH B 低位
                                // EAX A 低位，已经是了
        XOR     EDX, EDX        // EDX A 高位 0
        CALL    System.@_llmul; // 返回 EAX 低 32 位、EDX 高 32 位
  end;

它能够正确完成32位无符号数的准确相乘。

无独有偶，System.pas里还有System.@_llumod和System.@_lludiv，这两个汇编函数用效率还能接受的方式，手工实现了64位无符号整数的整除求商和求余，同样，它们也不能直接用div和mod两个运算符实现。

  function UInt64Mod(A, B: TUInt64): TUInt64;
  asm
        // PUSH ESP 让 ESP 减了 4，要补上
        MOV     EAX, [EBP + $10]              // A Lo
        MOV     EDX, [EBP + $14]              // A Hi
        PUSH    DWORD PTR[EBP + $C]           // B Hi
        PUSH    DWORD PTR[EBP + $8]           // B Lo
        CALL    System.@_llumod;
  end;
  
以及：

  function UInt64Div(A, B: TUInt64): TUInt64;
  asm
        // PUSH ESP 让 ESP 减了 4，要补上
        MOV     EAX, [EBP + $10]              // A Lo
        MOV     EDX, [EBP + $14]              // A Hi
        PUSH    DWORD PTR[EBP + $C]           // B Hi
        PUSH    DWORD PTR[EBP + $8]           // B Lo
        CALL    System.@_lludiv;
  end;

综上所述，在不内置支持UInt64的Delphi编译器下，64位无符号整数的加减乘除都实现完毕，可以以它们为基础，进一步实现更多的密码学基础算法了。

当然，随着编译器逐步升级，在内置支持UInt64类型的情况下，function UInt64Mul(A, B: Cardinal): TUInt64; 函数就能简化成一句，而无需再调用__llmul：

  function UInt64Mul(A, B: Cardinal): TUInt64;
  begin
    Result := TUInt64(A) * B;
  end;

而前面属于128位无符号整数乘法研究范围的两个64位无符号整数相乘，在支持64位的编译器下，也可以用64位汇编写出可用的、用无符号指令MUL直接相乘的高速版本：

  // 64 位下两个无符号 64 位整数相乘，结果放 ResLo 与 ResHi 中
  procedure UInt64MulUInt64(A, B: UInt64;
    var ResLo, ResHi: UInt64); assembler;
  asm
        PUSH RAX
        MOV RAX, RCX
        MUL RDX         // 得用无符号的MUL，不能用有符号的 IMUL
        MOV [R8], RAX
        MOV [R9], RDX
        POP RAX
  end;

这相同的功能如果在32位下实现，则需要手动将两个64位无符号整数用列竖式乘法的方式手工相乘、移位、相加、拼接，那代码复杂度和出错概率就比高版本编译器自行实现的要大多了。

最后再补充一个TUInt64的比较。

因为补码规则及有无符号数的区别，两个以64位有符号数表示的64位无符号数并不能直接用大于、等于、小于号比较，否则就蜕化成了有符号数比较，$8000000000000000就会小于$1000000000000000，因为前者被当成了负数。

我们也新写了一个函数function UInt64Compare(A, B: TUInt64): Integer; 用来实现两个以64位有符号数表示的64位无符号数的比较，原理也挺简单，将高低32位拆开成32位无符号数互相比较，类似于十进制里先进行百位数比较，不同就能得到结果，如果百位数相同则比较十位，十位相同再比较个位，以此类推。

    function UInt64Compare(A, B: TUInt64): Integer;
    var
      HiA, HiB, LoA, LoB: Cardinal;
    begin
      HiA := (A and $FFFFFFFF00000000) shr 32;
      HiB := (B and $FFFFFFFF00000000) shr 32;
      if HiA > HiB then
        Result := 1
      else if HiA < HiB then
        Result := -1
      else
      begin
        LoA := Cardinal(A and $00000000FFFFFFFF);
        LoB := Cardinal(B and $00000000FFFFFFFF);
        if LoA > LoB then
          Result := 1
        else if LoA < LoB then
          Result := -1
        else
          Result := 0;
      end;
    end;

以上代码先比高32位无符号数，相同再比低32位无符号数，总体逻辑比较清晰，大概是本文里最容易理解的一段代码吧。