Leading zero or trailing zero

code:leading zero and trailing zero

bit 31 bit 0

| |

v v

X = 00000110001001000100010001010010

<---> ^

Leading zero Trailing zero

ビット列の先頭や末尾から見て、最初に1になった場所を報告する

lzcount(X) = 5 tzcount(X) = 1

CPU命令

x86 (i386〜) BS{F,R}, (BMI1) {L,T}ZCNT, (AVX512_CD) VPLZCNT{D,Q}

Arm CLZ

PTX ctz

ハードウェア実装

どうするのが良いんでしょうか…？

ソフトウェア実装

tzcountはpopcountさえ持っていれば簡単:

tzcount(x) := popcount(~x & (x-1))

lzcountは簡単ではないが、bit-reverseとtzcountを持っていれば

lzcount(x) := tzcount(reverse(x))

とはなる

tzcountはpopcountに帰着でき、 #Population_count はワード幅の対数でできるのでそれなりに速いはず。