最初のセットを見つける

コンピュータソフトウェアとハ​​ードウェアにおいて、最初のセットの検索( ffs ) または最初の 1 の検索は、符号なしマシンワードが与えられると、^{[nb 1]}最下位ビットの位置から数えてワード内で 1 に設定されている最下位ビットのインデックスまたは位置を指定するビット操作です。ほぼ同等の操作は、末尾のゼロの数のカウント( ctz ) または末尾のゼロの数( ntz ) で、最下位の 1 ビットに続くゼロビットの数を数えます。最上位に設定されているビットのインデックスまたは位置を検索する補完操作は、2 進対数⌊log ₂ (x)⌋を計算するため、このように呼ばれるlog base 2です。^[1]これは、最上位の 1 ビットの前のゼロビットの数を数える先頭のゼロの数のカウント( clz ) または先頭のゼロの数( nlz )と密接に関連しています。 ^{[nb 2]} find first setには2つの一般的なバリエーションがあり、ビットのインデックスを1から開始するPOSIX定義^[2]（ここではffsと表記）と、ビットのインデックスを0から開始するバリエーション（ctzと同等なのでその名前で呼ぶ）があります。

最近の CPU命令セット アーキテクチャのほとんどは、これらの 1 つ以上をハードウェア オペレータとして提供します。利用できないものについては、通常、コンパイラ組み込み関数またはシステム ライブラリのいずれかでソフトウェア エミュレーションが提供されます。

次の 32 ビット ワードがあるとします。

0000 0000 0000 0000 1000 0000 0000 1000

末尾のゼロをカウントする操作は 3 を返しますが、先頭のゼロをカウントする操作は 16 を返します。先頭のゼロをカウントする操作はワード サイズによって異なります。この 32 ビット ワードが 16 ビット ワードに切り捨てられた場合、先頭のゼロをカウントする操作は 0 を返します。最初のセットを検索する操作は 4 を返します。これは右から 4 番目の位置を示します。切り捨てられた 2 を底とする対数は 15 です。

同様に、次の 32 ビット ワードの場合、上記のワードのビット否定は次のようになります。

1111 1111 1111 1111 0111 1111 1111 0111

末尾の 1 を数える演算は 3 を返し、先頭の 1 を数える演算は 16 を返し、最初のゼロを見つける演算 ffz は 4 を返します。

ワードがゼロ (ビットが設定されていない) の場合、count leading zeros と count trailing zeros は両方ともワード内のビット数を返しますが、ffs はゼロを返します。find first set の log base 2 とゼロベースの実装は両方とも、通常、ゼロ ワードに対して未定義の結果を返します。

多くのアーキテクチャには、最初にセットを検索する操作や、以下に示す関連操作を迅速に実行するための命令が含まれています。最も一般的な操作は、先行ゼロのカウント (clz) です。これは、他のすべての操作をこれに基づいて効率的に実装できるためと考えられます (「プロパティと関係」を参照)。

一部の Alpha プラットフォームでは、CTLZ と CTTZ はソフトウェアでエミュレートされます。

多くのコンパイラおよびライブラリ ベンダーは、最初のセットの検索や関連する操作を実行するためのコンパイラ組み込み関数またはライブラリ関数を提供しており、これらは多くの場合、上記のハードウェア命令に基づいて実装されます。

ビットが 1 から始まるラベル付けされている場合 (この記事で使用されている規則)、末尾のゼロを数える操作と最初のセットを見つける操作は、ctz( x ) = ffs( x ) − 1で関連付けられます (入力がゼロの場合を除く)。ビットが0から始まるラベル付けされている場合、末尾のゼロを数える操作と最初のセットを見つける操作はまったく同じです。ワードあたりwビットを考えると、log _{2 は}clzから簡単に計算でき、その逆も同様にlog ₂ ( x ) = w − 1 − clz( x )で計算できます。

上記の例で示されているように、最初のゼロの検索、先頭の 1 のカウント、および末尾の 1 のカウントの操作は、入力を否定し、最初のセットの検索、先頭のゼロのカウント、および末尾のゼロのカウントを使用することで実装できます。逆の場合も同様です。

M68000 などの効率的な log ₂演算を備えたプラットフォームでは、 ctz は次のように計算できます。

ctz( x ) = log ₂ ( x & −x )

ここで、& はビットごとの AND を表し、−x はxの2 の補数を表します。式x & −x は最下位の1ビットを除くすべてのビットをクリアし、最上位の1ビットと最下位の1ビットが同じになるようにします。

ARM や PowerPC などの効率的な先頭のゼロのカウント操作を備えたプラットフォームでは、ffs は次のように計算できます。

ffs( x ) = w − clz( x & −x )です。

逆に、 log ₂またはclz演算子のないマシンでは、非効率的ではありますが、 ctz を使用してclz を計算できます。

clz = w − ctz(2 ^{⌈log ₂ ( x )⌉} ) （これはゼロ入力に対してctzがwを返すことに依存）

SPARCの^{[35] [36]}やBlackfinの^{[37]のような効率的な}ハミング重み（人口カウント）演算を備えたプラットフォームでは、次のようになります。 POPCONES

ctz( x ) = popcount(( x & −x ) − 1) , ^{[38] [39]}またはctz ( x ) = popcount(~( x | −x )) ,

ffs( x ) = popcount( x ^~ −x ) ^[35]

clz = 32 − ポップカウント(2 ^{⌈log ₂ ( x )⌉} − 1)

ここで、^ はビットごとの排他的論理和、| はビットごとの論理和、~ はビットごとの否定を表します。

逆問題（iが与えられたとき、ctz( x ) = iとなるようなx を生成する）は、左シフト（ 1 << i ）で計算できます。

最初のセットの検索および関連する操作は、一方の端から開始して、すべてゼロではない単語 ( ffs、ctz、clzの場合) またはすべて 1 ではない単語 ( ffz、clo、ctoの場合) に遭遇するまで続行することで、任意の大きさのビット配列に簡単に拡張できます。ビットマップを再帰的に使用してどの単語がゼロではないかを追跡するツリー データ構造により、これを高速化できます。

1980 年代後半以降の CPU のほとんどには、ffs またはそれと同等のビット演算子がありますが、ARM-Mx シリーズの一部など、最近の CPU にはそれがありません。ffs、clz、ctz のハードウェア演算子の代わりに、ソフトウェアはシフト、整数演算、ビット演算子を使用してそれらをエミュレートできます。CPU のアーキテクチャ、およびそれほど重要ではないもののプログラミング言語のセマンティクスとコンパイラ コード生成の品質に応じて、いくつかのアプローチがあります。これらのアプローチは、線形検索、バイナリ検索、検索 + テーブル検索、de Bruijn 乗算、浮動小数点変換/指数抽出、およびビット演算子 (ブランチレス) 方式として大まかに説明できます。実行時間とストレージ領域、および移植性と効率性の間にはトレードオフがあります。

ソフトウェア エミュレーションは通常、決定論的です。すべての入力値に対して定義された結果を返します。特に、すべてゼロ ビットの入力の結果は、ffs の場合は通常 0 になり、他の操作の場合はオペランドのビット長になります。

ハードウェア clz または同等のものがあれば、ctz はビット演算で効率的に計算できますが、その逆は当てはまりません。つまり、ハードウェア演算子がない場合、clz の計算は効率的ではありません。

^{シフトとビットOR [40]}を使用した関数2⌈log2 ^(x)⌉（最も近い2の累乗に切り上げる）は^{、この32ビットの例のように計算するのは効率_的}ではなく、64ビットまたは128ビットのオペランドがある場合はさらに非効率的です。

関数pow2(x):
     x = 0の場合、invalidを返します  // invalid は実装定義です ([0,63] の範囲外)
    x ← x - 1
    {1, 2, 4, 8, 16}内の各yについて: x ← x | (x >> y)
     x + 1
を返す

ffs = ctz + 1 (POSIX) または ffs = ctz (その他の実装) であるため、ctz に適用可能なアルゴリズムを使用できます。最終ステップでは、結果に 1 を追加し、すべてのゼロ ビットの入力に対してオペランドの長さの代わりに 0 を返すことができます。

標準的なアルゴリズムは、LSB から始めて 1 ビットに遭遇するまでゼロをカウントするループです。

関数ctz1 (x)
     x = 0の場合wを返す
    t ← 1
    r ← 0
    (x & t) = 0の場合
        t ← t << 1
        r ← r + 1
    rを
返す

このアルゴリズムはO ( n ) の時間と演算を実行し、条件分岐の数が多いため実際には実用的ではありません。

ルックアップ テーブルを使用すると、ほとんどの分岐を排除できます。

table[0..2 n -1] = ctz(i) iが0..2 n -1
の場合function ctz2 (x)
     x = 0の場合wを返す
    r ← 0
    
        (x & (2 n -1)) ≠ 0
            の場合にループし、 r + table[x & (2 n -1)]を返す
        x ← x >> n
        r ← r + n

パラメータnは固定（通常は 8）で、時間と空間のトレードオフを表します。ループは完全に展開することもできます。ただし、線形ルックアップであるため、このアプローチではオペランドのビット数は依然として O(n) です。

バイナリ検索の実装では、次の32ビットバージョンのように、対数の数の操作と分岐が必要になります。^{[41] [42]} このアルゴリズムはテーブルによっても補助でき、下部の3つの「if」ステートメントを、最初に検出されたゼロ以外のバイトをインデックスとして使用する256エントリのルックアップテーブルに置き換えます。

関数ctz3(x)
     x = 0の場合32を返す
    0 ← 0
    if (x & 0x0000FFFF) = 0: n ← n + 16, x ← x >> 16
     if (x & 0x000000FF) = 0: n ← n + 8, x ← x >> 8
     if (x & 0x0000000F) = 0: n ← n + 4, x ← x >> 4
     if (x & 0x00000003) = 0: n ← n + 2, x ← x >> 2
     if (x & 0x00000001) = 0: n ← n + 1
     return n

ハードウェアに clz 演算子がある場合、ctz を計算する最も効率的な方法は次のとおりです。

関数ctz4 (x)
    x &= -x
    w - (clz(x) + 1)
を返す

32ビットCTZアルゴリズムは、デ・ブリュインシーケンスを使用して、すべての分岐を排除する最小限の完全ハッシュ関数を構築します。 ^{[43] [44]} このアルゴリズムでは、乗算の結果が32ビットに切り捨てられることを前提としています。

iが0から31の場合: table[ ( 0x077CB531 * ( 1 << i ) ) >> 27 ] ← i // テーブル [0..31] を初期化します。
関数ctz5 (x) は
    table[((x & -x) * 0x077CB531) >> 27] を返します
。

式 (x & -x) は、最下位の 1 ビットを再び分離します。可能なワードは 32 個だけであり、符号なし乗算とシフトによってテーブル内の正しい位置にハッシュされます (このアルゴリズムはゼロ入力を処理しません)。

標準的なアルゴリズムは、この例に示すように、MSB から開始して 1 ビットずつ非ゼロ ビットが見つかるまで調べます。これは O(n) 時間で実行されます (n はオペランドのビット長)。一般的な用途には実用的なアルゴリズムではありません。

関数clz1(x)
     x = 0の場合wを返す
    t ← 1 << (w - 1)
    r ← 0
    (x & t) = 0の場合
        t ← t >> 1
        r ← r + 1
    rを
返す

以前のループ手法の改良では、一度に 8 ビットを調べ、最初の非ゼロ バイトに対して 256 (2 ⁸ ) エントリのルックアップ テーブルを使用します。ただし、この手法でも実行時間は依然として O(n) です。

関数clz2(x)
     x = 0の場合wを返す
    t ← 0xff << (w - 8)
    r ← 0
    (x & t) = 0の場合
        t ← t >> 8
        r ← r + 8
    r + テーブル[x >> (w - 8 - r)]
を返す

バイナリ検索は実行時間を O(log ₂ n) に短縮できます。

関数clz3(x)
     x = 0の場合32を返す
    0 ← 0
    if (x & 0xFFFF0000) = 0: n ← n + 16, x ← x << 16
     if (x & 0xFF000000) = 0: n ← n + 8, x ← x << 8
     if (x & 0xF0000000) = 0: n ← n + 4, x ← x << 4
     if (x & 0xC0000000) = 0: n ← n + 2, x ← x << 2
     if (x & 0x80000000) = 0: n ← n + 1
     return n

clz をシミュレートする最も高速な移植可能なアプローチは、バイナリ検索とテーブル検索の組み合わせです。8 ビット テーブル検索 (2 ^{8 =256 1 バイト エントリ) は、バイナリ検索の下位 3 つの分岐を置き換えることができます。64 ビット オペランドには追加の分岐が必要です。より広い幅の検索を使用できますが、実際のテーブルの最大サイズは、最近のプロセッサの L1 データ キャッシュのサイズによって制限されます。これは、多くの場合 32 KB です。分岐の保存は、} L1 キャッシュミス のレイテンシによって相殺されます。

CTZのde Bruijn乗算に似たアルゴリズムがCLZでも機能しますが、最上位ビットを分離するのではなく、シフトとビットごとのORを使用して2 ⁿ −1の形式の最も近い整数に切り上げます。^[45]

テーブル[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
                8、12、20、28、15、17、24、7、19、27、23、6、26、5、4、31}
関数clz4 (x)
    は、{1, 2, 4, 8, 16}
    内の各yに対して、x ← x | (x >> y) というテーブルを返します[((x * 0x07C4ACDD) >> 27) % 32]

Prescott やそれ以降の Intel プロセッサのような深いパイプラインを持つプロセッサの場合、予測ミスした分岐 (これらの種類の分岐は本質的に予測不可能) によるパイプライン フラッシュを回避するために、分岐をビット単位の AND 演算子と OR 演算子に置き換える方が高速になる場合があります (さらに多くの命令が必要になりますが)。

関数clz5(x)
    r = (x > 0xFFFF) << 4; x >>= r;
    q = (x > 0xFF) << 3; x >>= q; r |= q;
    q = (x > 0xF) << 2; x >>= q; r |= q;
    q = (x > 0x3) << 1; x >>= q; r |= q;
                                    r |= (x >> 1);
    r を返します。

整数から浮動小数点数へのハードウェア変換機能を備えたプラットフォームでは、指数フィールドを抽出して定数から減算することで、先頭のゼロの数を計算できます。丸め誤差を考慮して修正が必要です。^{[41] [46]}浮動小数点数への変換にはかなりの遅延が発生する可能性があります。この方法は移植性が低く、通常は推奨されません。

int x ; int r ;共用体{ unsigned int u [ 2 ]; double d ; } t ;  
 
        

t . u [ LE ] = 0x43300000 ; // LE はリトルエンディアンの場合は 1 t . u [ ! LE ] = x ; t . d -= 4503599627370496.0 ; r = ( t . u [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // CLZ    
  
  
        
  

先行ゼロカウント（clz）演算は、整数をm  × 2 ^eとしてエンコードする正規化を効率的に実装するために使用できます。ここで、mの最上位ビットは既知の位置（最高位置など）にあります。これは、ニュートン・ラプソン除算を実装したり、ソフトウェアで整数から浮動小数点への変換を実行したり、その他のアプリケーションに使用できます。 ^{[41] [47]}

先頭ゼロカウント (clz) は、clz(x − y) >> 5という恒等式を介して 32 ビット述語 "x = y" (真の場合は 0、偽の場合は 1) を計算するために使用できます。ここで、">>" は符号なし右シフトです。^{[48]これは、} n 1 ビットの最初の文字列を見つけるなど、より高度なビット操作を実行するために使用できます。^[49]式clz(x − y)1 << (16 − clz(x − 1)/2)は、ニュートン法を使用して 32 ビット整数の平方根を計算するための効果的な初期推定値です。^[50] CLZ は、整数を先頭のゼロバイトの数と非ゼロバイトの数としてエンコードする高速データ圧縮技術であるヌル抑制を効率的に実装できます。 ^{[51]また、}一様ランダムな整数の clz を取ることで、指数分布の整数を効率的に生成することもできます。^[41]

2を底とする対数は、 ⌈log ₂ (xy)⌉ ≤ ⌈log ₂ (x)⌉ + ⌈log ₂ (y)⌉であるため、乗算がオーバーフローするかどうかを予測するために使用できます。^[52]

先頭のゼロを数えることと末尾のゼロを数えることは、限られたリソースを使用して有限範囲の関数の周期を見つけることができるゴスパーのループ検出アルゴリズム^{[53]を実装するために一緒に使用することができます。 [42]}

バイナリ GCD アルゴリズムは、末尾のゼロを削除するのに多くのサイクルを費やします。これは、末尾のゼロのカウント (ctz) とそれに続くシフトに置き換えることができます。同様のループは、ひょう石シーケンスの計算にも現れます。

ビット配列は優先度キューの実装に使用できます。このコンテキストでは、find first set (ffs) は「pop」または「最も優先度の高い要素をプルする」操作を効率的に実装するのに役立ちます。Linuxカーネルのリアルタイムスケジューラは、sched_find_first_bit()この目的のために内部的に使用します。^[54]

末尾のゼロを数える演算は、ハノイの塔問題に対する簡単な最適解を与える。ディスクはゼロから番号が付けられ、移動kにおいて、ディスク番号 ctz( k ) は右に可能な限り最短距離移動する（必要に応じて左に戻る）。また、任意のワードを取り、ステップkでビット ctz( k ) を反転することで、グレイコードを生成することもできる。^[42]

• Intel および AMD x86 ベースのプロセッサ用のビット操作命令セット(BMI)
• 末尾のゼロ
• 先頭のゼロ
• 末尾の数字
• 先頭の数字

• ウォーレン・ジュニア、ヘンリー・S. (2013) [2002]. Hacker's Delight (第2版). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-80-321-84268-5.
• アンダーソン、ショーン・エロン (2005) [1997]。「Bit Twiddling Hacks」。スタンフォード大学。2020年1月8日時点のオリジナルよりアーカイブ。 2012年1月3日閲覧。(注: 末尾のゼロをカウントし、2 を底とする対数を計算するための効率的なパブリック ドメイン C 実装をいくつかリストします。)

• Intel イントリンシクス ガイド
• チェス プログラミング Wiki: BitScan: ffs (LS1B と呼ばれる) および log base 2 (MS1B と呼ばれる) のさまざまな実装方法の詳細な説明。