加载中…
正文 字体大小:

128位大整数扩展和操作符重载(附delphi源代码)

(2013-01-13 04:11:20)
标签:

delphixe3

128位整数

操作符重载

分类: IT技术-Delphi
一个应用需要用到准确大整数,而不是浮点数。通观各常用语言,VC++,C#,delphi,java似乎都没有提供直接支持,一些科学算法语言倒是有现成第三方插件,但不是我想要.不得已只能自己实现.牵涉到数据结构的东西,我还是习惯于先用最佳教学语言pascal(delphi)先实现,因为它在逻辑上更接近自然语言,结构上更清晰,当然这也许只是个人习惯而已.之后可以很容易的移植到其它语言.说干就干.
  1. 128位整数定义:先实现无符号的
    type Uint128=array[0..15] of byte;//16个byte
  2. 定义一个方便访问16byte的结构
      Int128Rec = packed record
        case integer of
          0: (Lo, Hi: UInt64);
          1: (Uint64s: array [0 .. 1] of UInt64);
          2: (Cardinals: array [0 .. 3] of Cardinal);
          3: (Words: array [0 .. 7] of word);
          4: (Bytes: array [0 .. 15] of byte);
      end;
    这样就可以方便的按照需求访问128整数的各个部分了
  3. 128位加法
    function UInt128Add(a, b: UInt128): UInt128;
    begin
      Int128Rec(result).Hi := Int128Rec(a).Hi + Int128Rec(b).Hi;//看成两Uint64加,高位先加,进位舍去
      Int128Rec(result).Lo := Int128Rec(a).Lo + Int128Rec(b).Lo;//低位相加
      if ((Int128Rec(result).Lo <= Int128Rec(a).Lo) or (Int128Rec(result).Lo <= Int128Rec(b).Lo)) and
        ((Int128Rec(a).Lo > 0) and (Int128Rec(b).Lo > 0)) then Int128Rec(result).Hi := Int128Rec(result).Hi + 1;//进位加到高位
  4. 128位减法(暂时只求球绝对值)
    function UInt128.Subtract(a, b: UInt128): UInt128;
    begin
      case CompareValue(a, b) of
        EqualsValue:
          begin
            result := 0;//相同则为0
            exit;
          end;
        LessThanValue: Exchange(a, b); // 若b>a 则交换
      end; //case

      Int128Rec(result).Hi := Int128Rec(a).Hi - Int128Rec(b).Hi;//高位想减
      if CompareValue(Int128Rec(a).Lo, Int128Rec(b).Lo) = LessThanValue then
      begin  //低位不够则借位相减
        Int128Rec(result).Lo := not(Int128Rec(b).Lo - Int128Rec(a).Lo) + 1;
        Int128Rec(result).Hi := Int128Rec(result).Hi - 1;
      end
      else Int128Rec(result).Lo := Int128Rec(a).Lo - Int128Rec(b).Lo;//否者直接相减
    end;
  5. 128为大小比较函数:(上面用到了)
    function CompareValue(const a, b: UInt128): TValueRelationship; overload;
    begin
      result := CompareValue(Int128Rec(a).Hi, Int128Rec(b).Hi);
      if result = EqualsValue then result := CompareValue(Int128Rec(a).Lo, Int128Rec(b).Lo);
    end;
  6. 128位 shl
    function UInt128LeftShift(a: UInt128; count: byte): UInt128;
    var
      u64: UInt64;
    begin
      if count = 0 then exit(a);
      if count >= 128 then exit(0);
      if count >= 64 then
      begin
        Int128Rec(result).Hi := Int128Rec(a).Lo shl (count - 64);
        Int128Rec(result).Lo := 0;
        exit;
      end;
      Int128Rec(result).Hi := Int128Rec(a).Hi shl count;
      u64 := Int128Rec(a).Lo;
      u64 := u64 shr (64 - count);
      Int128Rec(result).Hi := Int128Rec(result).Hi or u64;
      Int128Rec(result).Lo := Int128Rec(a).Lo shl count;
    end;
  7. 128位 shr
    function UInt128RightShift(a: UInt128; count: byte): UInt128;
    var
      u64: UInt64;
    begin
      if count = 0 then exit(a);
      if count >= 128 then exit(0);
      if count >= 64 then
      begin
        Int128Rec(result).Lo := Int128Rec(a).Lo shr (count - 64);
        Int128Rec(result).Hi := 0;
        exit;
      end;
      Int128Rec(result).Lo := Int128Rec(a).Lo shr count;
      u64 := Int128Rec(a).Hi;
      u64 := u64 shl (64 - count);
      Int128Rec(result).Lo := Int128Rec(result).Lo or u64;
      Int128Rec(result).Hi := Int128Rec(a).Hi shr count;
    end;

  8. 128位乘法
    function UInt128Multiply(a, b: UInt128): UInt128;
      function mul64To128(aa, bb: UInt64): UInt128;//先实现一个U1nt64*Uint64=Uint128的
      var
        AHi, ALo, BHi, BLo: UInt64;
        T128: UInt128;
      begin
        T128 := 0;
        AHi := int64Rec(aa).Hi;
        ALo := int64Rec(aa).Lo;
        BHi := int64Rec(bb).Hi;
        BLo := int64Rec(bb).Lo;
        Int128Rec(T128).Lo := AHi * BHi;
        result := T128 shl 64;
        Int128Rec(T128).Lo := AHi * BLo; //A.hi*B.Lo
        result := result + (T128 shl 32);
        Int128Rec(T128).Lo := ALo * BHi; //A.Lo*B.Hi
        result := result + (T128 shl 32);
        Int128Rec(T128).Lo := ALo * BLo; //Lo*Lo
        result := result + T128;
      end;

    var
      AHi, ALo, BHi, BLo: UInt64;
      T128: UInt128;
    begin
      AHi := Int128Rec(a).Hi;
      ALo := Int128Rec(a).Lo;
      BHi := Int128Rec(b).Hi;
      BLo := Int128Rec(b).Lo;

      T128 := mul64To128(AHi, BLo);
      result := T128 shl 64;

      T128 := mul64To128(ALo, BHi);
      result := result + T128 shl 64;

      T128 := mul64To128(ALo, BLo);
      result := result + T128;
    end;
  9. 128位 计算所使用bit数
    function UintsHighBit(U: UInt128): byte; Overload;
    begin
      if Int128Rec(U).Hi > 0 then result := 64 + UintsHighBit(Int128Rec(U).Hi)
      else result := UintsHighBit(Int128Rec(U).Lo);
    end;
  10. 128位除法
    function UInt128IntDivide(a, D: UInt128): UInt128;
      function IntDivU128(aa, dd: UInt128): UInt128;
      var
        c: integer;
        U, t: UInt128;
      begin
        U := 0;
        t := 0;
        result := 0;
        case CompareValue(aa, dd) of
          EqualsValue:
            begin
              result := 1;
              exit;
            end;
          LessThanValue: exit;
        else
          begin
            result := 1;
            c := UintsHighBit(aa) - UintsHighBit(dd);
            result := result shl c;
            U := dd shl c;
            if CompareValue(aa, U) = LessThanValue then
            begin
              U := U shr 1;
              result := result shr 1;
            end;
            t := aa - U;
            result := result + IntDivU128(t, dd);
          end;
        end;
      end;

    begin
      result := IntDivU128(a, D);
    end;
  11. 128位 mod
    function UInt128Modulus(a, M: UInt128): UInt128;
      function ModU128(aa, mm: UInt128): UInt128;
      var
        c: integer;
        U, t: UInt128;
      begin
        U := 0;
        t := 0;
        result := 0;
        case CompareValue(aa, mm) of
          EqualsValue: exit;
          LessThanValue: result := aa;
        else
          begin
            c := UintsHighBit(aa) - UintsHighBit(mm);
            //        c := UintsHighCardinal(aa) - UintsHighCardinal(mm);
            U := mm shl c;
            if CompareValue(aa, U) = LessThanValue then U := U shr 1;
            t := aa - U;
            result := ModU128(t, mm);
          end;
        end; //case
      end;

    begin
      result := ModU128(a, M);
    end;

上面的代码能编译吗?显然是不能,编译器是不会同意自定义的数据类型的符号操作的, Uint128+ Uint28、Uint128- Uint28、Uint128* Uint28、Uint128 shl N这类操作时通不过的 。那怎么办呢?
简单的把这些操作符都换成定义的函数调用就可以了。换了再试试,果然行了。但这太不方便了吧,如果能让编译器直接帮我们替换就好了。嘿嘿!这就要用到操作符重载了。在C++里操作符重载很早就实现了,但它实现的原理等同于模版替换(这真是个万能语法糖功能),在delphi里知道delphi8才实现.net下的重载,到delphi2006实现win32的重载,当然到现在xe3,已经实现了几乎所有(说几乎所有,是因为我还没找到直接对大整数正常赋大值的方法,当然不正常实现了)重载了.
  1. delphi下操作符重载帮助
    128位大整数扩展和操作符重载(附delphi源代码)

    128位大整数扩展和操作符重载(附delphi源代码)

    128位大整数扩展和操作符重载(附delphi源代码)

  2. 按帮助重新整理添加上面函数
    type
      {128位长度整数支持}

      // ------------128位整数定义---------------
    {$IFDEF NoInt28}    //估计未来版本会支持128位整数,所以条件编译,到时简单去掉就行了

      Int128Rec = packed record
        case integer of
          0: (Lo, Hi: UInt64);
          1: (Uint64s: array [0 .. 1] of UInt64);
          2: (Cardinals: array [0 .. 3] of Cardinal);
          3: (Words: array [0 .. 7] of word);
          4: (Bytes: array [0 .. 15] of byte);
      end;

      {重载Uint28操作符, }
      PUInt128 = ^UInt128;

      UInt128 = record
      private
        FData: array [0 .. 15] of byte;
      public
        class operator Implicit(a: UInt64): UInt128;
        class operator Implicit(a: UInt128): UInt64;
        class operator Implicit(a: string): UInt128;//可以直接用字符串对其赋值了
        class operator Implicit(a: UInt128): string;//可以直接当字符串使用了
        class operator LeftShift(a: UInt128; count: byte): UInt128; //shl
        class operator RightShift(a: UInt128; count: byte): UInt128; //shr
        class operator Add(a: UInt128; b: UInt128): UInt128; //+
        {int128 暂时没定义,减法得到的是绝对值}
        class operator Subtract(a: UInt128; b: UInt128): UInt128; //-
        class operator Multiply(a: UInt128; b: UInt128): UInt128; //*
        class operator IntDivide(a: UInt128; D: UInt128): UInt128; // div
        class operator Modulus(a: UInt128; M: UInt128): UInt128; // mod
        class operator Equal(a: UInt128; b: UInt128): Boolean; //=
        class operator NotEqual(a: UInt128; b: UInt128): Boolean; //<>
        class operator GreaterThan(a: UInt128; b: UInt128): Boolean; //>
        class operator GreaterThanOrEqual(a: UInt128; b: UInt128): Boolean; //>=
        class operator LessThan(a: UInt128; b: UInt128): Boolean; //<
        class operator LessThanOrEqual(a: UInt128; b: UInt128): Boolean; //<=
        class operator BitwiseAnd(a: UInt128; b: UInt128): UInt128; //AND
        class operator BitwiseOr(a: UInt128; b: UInt128): UInt128; //OR
        class operator BitwiseXor(a: UInt128; b: UInt128): UInt128; //XOR

        function ToString: string;//可以像对象一样使用:Uint128.tostring
      end;
    {$ENDIF}
  3. 到这里我们几乎实现全部128整数的操作符重载了.这时我们的delphi 看起来就是原生支持128为整数的了.
    同是我们多实现几个功能.
    • class operator Implicit(a: string): UInt128;//可以直接用字符串对其赋值了
      可以这样使用: Uint128:='1323131237084038234832400324';
      Uint128:=edit1.text;
      这就解决了对128位整数直接赋大值的问题.

    •  class operator Implicit(a: UInt128): string;//可以直接当字符串使用了
      memo1.line.add(Uint128);//Uint128会自动转换成字符串了.是不是有了点javascript的感觉.
    • 内置的function ToString: string; 让你可以这样使用:s:=Uint128.tostring;像java和C#是吧!
  4. 操作符重载虽然只是语法糖,但的确能极大的方便编程,特别是在便于思考记忆和阅读.比如用于矩阵运算.用于2维、3维甚至多维运算时。
  5. 最后,可能会有人思考,这里定义Uint128 可以用类似对象操作 的Uint128.Tostring,那么以前系统自带数据类型也可以就好了.呵呵!那当然是可以的.不过现在我想睡觉.明天再说吧.

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有