それほど機会が多いわけではありませんが、整数の中で立っているビットの数を数えたいということがあります。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などに定義がありません。またこれらの関数は現時点ではヘルプ上に記述がありません。
