整数の中で立っているビットの数を数える

Population counting (hamming weight)

unit Unit2;

interface

function PopulationCount(Value: UInt8): Integer; overload;
function PopulationCount(Value: UInt16): Integer; overload;
function PopulationCount(Value: UInt32): Integer; overload;
function PopulationCount(Value: UInt64): Integer; overload;


implementation

function PopulationCount(Value: UInt8): Integer;
begin

  Value := (Value and $55) + ((Value shr 1) and $55);
  Value := (Value and $33) + ((Value shr 2) and $33);
  Value := (Value and $0F) + ((Value shr 4) and $0F);
  Result := Value;

end;

function PopulationCount(Value: UInt16): Integer;
begin

  Value := (Value and $5555) + ((Value shr 1) and $5555);
  Value := (Value and $3333) + ((Value shr 2) and $3333);
  Value := (Value and $0F0F) + ((Value shr 4) and $0F0F);
  Value := (Value and $00FF) + ((Value shr 8) and $00FF);
  Result := Value;

end;

function PopulationCount(Value: UInt32): Integer;
begin

  Value := (Value and $55555555) + ((Value shr  1) and $55555555);
  Value := (Value and $33333333) + ((Value shr  2) and $33333333);
  Value := (Value and $0F0F0F0F) + ((Value shr  4) and $0F0F0F0F);
  Value := (Value and $00FF00FF) + ((Value shr  8) and $00FF00FF);
  Value := (Value and $0000FFFF) + ((Value shr 16) and $0000FFFF);
  Result := Value;

end;

function PopulationCount(Value: UInt64): Integer; overload;
begin

  Value := (Value and $5555555555555555) + ((Value shr  1) and $5555555555555555);
  Value := (Value and $3333333333333333) + ((Value shr  2) and $3333333333333333);
  Value := (Value and $0F0F0F0F0F0F0F0F) + ((Value shr  4) and $0F0F0F0F0F0F0F0F);
  Value := (Value and $00FF00FF00FF00FF) + ((Value shr  8) and $00FF00FF00FF00FF);
  Value := (Value and $0000FFFF0000FFFF) + ((Value shr 16) and $0000FFFF0000FFFF);
  Value := (Value and $00000000FFFFFFFF) + ((Value shr 32) and $00000000FFFFFFFF);
  Result := Value;

end;

end.