整数の下位ビットから連続した "0" を数えます。
def CTZ(n: int) -> int:
return (n & -n).bit_length() - 1
"0" のときは "-1" を返します。これは
- Intel x86 プロセッサでは BSF 命令
- 0 のときは不定
- C++ 言語では std::countr_zero(x)
- 0 のときは x のビット幅
に相当します。２進数とCTZの関係は以下の通り
| ２進数 | CTZ |
|---|---|
| ???? 1 | 0 |
| ??? 10 | 1 |
| ?? 100 | 2 |
| ? 1000 | 3 |
| ... | ... |
参考資料