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

それほど機会が多いわけではありませんが、整数の中で立っているビットの数を数えたいということがあります。C++であればstd::bitsetのcountを使えば一発ですが、残念ながらDelphiでは符号なし整数型のヘルパ(TByteHelper/TWordHelper/TCardinalHelper/TUInt64Helper)を含め、標準ではそのような機能がありません。でちょっと検索してみたところ、population countあるいはHamming weightというキーワードが浮かんできました。最近のCPUには専用の命令(x86だとSSE4.2以降のPOPCNT)がありますが、移植性などを考慮して、Delphiで実装してみました。とはいってもCで書かれたものをそのままDelphiに置き換えただけです。詳細や原理については○×つくろーどっとコムさんのその17 ビット演算あれこれや中村実さんのビットを数える・探すアルゴリズムなどを、またx86/x64のPOPCNT命令との比較についてはtakesakoさんのx86x64 SSE4.2 POPCNTあたりを参照してください。

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;
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;

→整数の中で立っているビットの数を数える(Gist)

2020/06/01追記: Delphi 10.4 Sydneyでは標準関数(かつ組み込みルーチン(en))としてCountLeadingZeros32(先頭の(MSBからの)連続している0の数/32bit整数)、CountLeadingZeros64(先頭の(MSBからの)連続している0の数/64bit整数)、CountTrailingZeros32(末尾のの(LSBからの)連続している0の数/32bit整数)、CountTrailingZeros64(末尾のの(LSBからの)連続している0の数/64bit整数)、CountPopulation32(1になっているビットの数/32bit整数)、CountPopulation64(1になっているビットの数/64bit整数)が追加されました。これらの関数はコンパイラによってインラインで展開されるため、System.pasなどに定義がありません。またこれらの関数は現時点ではヘルプ上に記述がありません。