[学习笔记] Pascal集合类型内存结构

Question

个人学习笔记一篇，与大家交流探讨。顶者有分。指出错误或提出建议者，另有高分相赠。
//题目：Pascal集合类型内存结构
//作者：LihuaSoft
//日期：2007年2月3日
//链接：http://rabbitfox.blog.sohu.com/32519247.html(* 作人要厚道，转载请注明作者及出处 *)一、问题的起源：    2007年初，CSDN的Delphi版上有一个贴子(http://community.csdn.net/Expert/topic/5315/5315550.xml?temp=.4219171)，内容如下：
    “请问两个数组或TStringList怎么进行与或非运算？比如数组是1：1,2,3；2：1,3,4,5。怎么弄呢？最好是TStringList进行运算，然后生成一个新的List。”
    看到这个贴子时，我想：最常用的办法就是遍历了，也已经有人回贴：“遍历”。用TStringList甚至还不如遍历来得实在。脑中忽然闪现：“集合”运算(并集、交集等)是否可以借鉴？于是想立即实践一下。后来因为工作忙，这件事情耽搁了一段时间。今天终于可以静下心来研究了。二、Pascal集合类型对象的内存结构：    我写了下面这段代码，看了一下集合类型的内存结构：
var
  MySet : Set of Byte;
  P : ^Byte;
  I : integer;
begin
  MySet := [1,3,5,7];
  P := @MySet;
  for I := 0 to SizeOf(MySet)-1 do
    begin
    Memo1.Text := Memo1.Text + Format(' %.2x ',[P^]);
    Inc(P);
    end;
end;    结果是(16进制)： AA  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00     给集合MySet赋值为[0]，那么第一个字节的显示结果就是 01 ；赋值为[1]，结果就是 02 ；赋值为[](空集)，则这32个字节全部是 00 。    由此可知：Pascal集合类型是一个有序类型，占用32个字节(SizeOf)的内存空间(256位)，集合成员也必须是有序类型，取值范围为 NULL 或[0..255]。一个集合的0～256个成员，如果存在某成员，则该成员相应的位值为1，否则为0，如下所示：Bit: 0 0 0 0  0 0 0 0   0 0 0 0  0 0 0 0  ...  0   0   0   0    0   0   0   0 
     ^ ^ ^ ^  ^ ^ ^ ^   ^ ^ ^ ^  ^ ^ ^ ^       ^   ^   ^   ^    ^   ^   ^   ^ 
元素 7 6 5 4  3 2 1 0  15141312 1110 9 8  ... 255 254 253 252  251 250 249 248
字节 |<-- 1字节 ----|  |<-- 2字节 -----|  ... |<------ 32字节 ---------------|    集合类型，亦遵循“高位字节在后、低位字节在前”的内存原则。三、对前述CSDN贴子的解答：    基于对Pascal集合类型的认识，我写了下面这个程序，作为对前述贴子的解答。声明：该贴子问题的正解，仍是“遍历”，之所以提供下面这种解决方案，纯粹为了迎合“与或非运算”这种思路，以及自己“练练手”的欲望。另外，数组元素只能是有序类型，并且数组长度不能超256。type
  TArr = array of Byte;//Char数组亦可procedure CompArraysUseSet(const A1,A2 : TArr; var A : TArr; CompType : Char);
{ 编程：LihuaSoft；  做人要厚道，转载请注明作者及出处 }
var
  Set1,Set2,Set3 : Set of Byte;
  P : ^Byte;
  I, J, Sum : integer;
begin
  { 给Set1、Set2、Set3赋空值,即:空集 }
  Set1 := [];
  Set2 := [];
  Set3 := [];
  { A1 ---> Set1 }
  for I := Low(A1) to High(A1) do
      begin
      P := @Set1;
      Inc(P, A1[I] div 8);
      P^ := P^ or ( 1 shl (A1[I] mod 8) );
      end;
  { A2 ---> Set2 }
  for I := Low(A2) to High(A2) do
      begin
      P := @Set2;
      Inc(P, A2[I] div 8);
      P^ := P^ or ( 1 shl (A2[I] mod 8) );
      end;
  { Set1、Set2运算，结果为Set3 }
  case CompType of
      '+' : Set3 := Set1 + Set2;//并集
      '-' : Set3 := Set1 - Set2;//差集
      '*' : Set3 := Set1 * Set2;//交集
      else  Set3 := Set1 + Set2;
      end;
  { 设定返回数组的长度 }
  Sum := 0;
  for I := 0 to 255 do
      if I in Set3 then Inc(Sum);
  SetLength(A, Sum);
  { Set3 ---> 返回数组A }
  P := @Set3;
  Sum := Low(A);
  for I := 0 to 31 do
      begin
      for J := 0 to 7 do
        if (P^ and (1 shl J))>0 then
           begin
           A[Sum] := I*8 + J;
           Inc(Sum);
           end;
      Inc(P);
      end;
end;    //以下是测试：procedure TForm1.Button1Click(Sender: TObject);
var
  A1, A2, A : TArr;
  I : integer;
begin
  SetLength(A1,3);
  SetLength(A2,7);
  A1[0] := 1;  A1[1] := 3;  A1[2] := 5;
  A2[0] := 2;  A2[1] := 5;  A2[2] := 17;  A2[3] := 22;  A2[4] := 23;
  A2[5] := 128;  A2[6] := 255;
  CompArraysUseSet(A2,A1,A,'+');//此处用“并集”运算方式'+'
  for I := 0 to Length(A)-1 do
      Memo1.Text := Memo1.Text + IntToStr(A[I]) + ',';
end;    结果是：1,2,3,5,17,22,23,128,255,四、另类收获：    需要紧凑的内存格式存储一个“数”，而Int64(8字节)等类型的长度又不能满足需要时，可以参考使用“集合”类型或Byte数组。

Answer 1

procedure       _SetIntersect; // *
asm
{       PROCEDURE _SetIntersect( VAR dest: Set; CONST src: Set; size: Byte);}
{       EAX     =       destination operand             }
{       EDX     =       source operand                  }
{       CL      =       size of set (0 < size <= 32)    }@@loop:
        MOV     CH,[EDX]
        INC     EDX
        AND     [EAX],CH
        INC     EAX
        DEC     CL
        JNZ     @@loop
end;procedure       _SetSub; // -
asm
{       PROCEDURE _SetSub( VAR dest: Set; CONST src: Set; size: Byte);  }
{       EAX     =       destination operand             }
{       EDX     =       source operand                  }
{       CL      =       size of set (0 < size <= 32)    }@@loop:
        MOV     CH,[EDX]
        NOT     CH
        INC     EDX
        AND     [EAX],CH
        INC     EAX
        DEC     CL
        JNZ     @@loop
end;
procedure       _SetUnion; // +
asm
{       PROCEDURE _SetUnion( VAR dest: Set; CONST src: Set; size: Byte);        }
{       EAX     =       destination operand             }
{       EDX     =       source operand                  }
{       CL      =       size of set (0 < size <= 32)    }@@loop:
        MOV     CH,[EDX]
        INC     EDX
        OR      [EAX],CH
        INC     EAX
        DEC     CL
        JNZ     @@loop
end;

Answer 2

-.-# 只是拷贝的System.pas里的函数通过CPU察看器看看汇编代码里有"@SetUnion"调用贴出来而已，精彩属于编写Systemp.pas的那个程序员