How can I create a TBitSet32 record in Delphi for efficient 32-bit operations?

I am working on a project where I need to manipulate a set of 32 bits very efficiently. Memory efficiency is crucial, so using an array of boolean (which would occupy 32 bytes) is not an option (if I can have other choice, speed is the most important).

Here's the structure I am envisioning for my TBitSet32:

TBitSet32 = record 
    value: ?integer?; // I'm not sure about the datatype here. Should it be Integer or another type?

    // Gets the value associated with a particular bit index.
    function valueForBit(index: integer): boolean;

    // Returns the number of marked bits in the set.
    function count: integer;

    // Marks the specified bit.
    procedure markBit(value: boolean; index: integer);   
end;

For the value field, I presume I need a 32-bit integer type. Is Integer the correct choice here? How can I implement the valueForBit, count, and markBit methods?

I would appreciate any insights or sample implementations for this record.

Solution

If you need exactly 32 bits, then (U)Int32 would make more sense than Integer. The rest is just a matter of bit manipulation using the and, or, and shl/shr operators, eg:

type
  TBitSet32 = record 
    FSet: UInt32;

    // Gets the value associated with a particular bit index.
    function valueForBit(index: integer): boolean;

    // Returns the number of marked bits in the set.
    function count: integer;

    // Marks the specified bit.
    procedure markBit(value: boolean; index: integer);   
  end;

function TBitSet32.valueForBit(index: integer): boolean;
begin
  Result := (FSet and (1 shl index)) <> 0;
end;

function TBitSet32.count: integer;
var
  I: Integer;
  tmp: UInt32;
begin
  Result := 0;
  tmp := FSet;
  for I := 0 to 31 do begin
    Inc(Result, tmp and 1);
    tmp := tmp shr 1;
  end;
end;

procedure markBit(value: boolean; index: integer);
begin
  if value then
    FSet := FSet or (1 shl index)
  else
    FSet := FSet and not (1 shl index);
end;

That said, consider using a Set instead, and let the compiler handle the bit manipulation for you, as a Set is implemented using a bit set, eg:

type
  TBitSet32 = record 
    FSet: set of 0..31;

    // Gets the value associated with a particular bit index.
    function valueForBit(index: integer): boolean;

    // Returns the number of marked bits in the set.
    function count: integer;

    // Marks the specified bit.
    procedure markBit(value: boolean; index: integer);   
  end;

function TBitSet32.valueForBit(index: integer): boolean;
begin
  Result := index in FSet;
end;

function TBitSet32.count: integer;
var
  I: Integer;
begin
  Result := 0;
  for I := 0 to 31 do
    Inc(Result, Ord(I in FSet));
end;

procedure markBit(value: boolean; index: integer);
begin
  if value then
    Include(FSet, index)
  else
    Exclude(FSet, index);
end;