ビットを操るgccビルトイン関数たち

gccのビルトイン関数の中で、ビットに関するもののまとめ。

function	feature
__builtin_clz(unsigned int)	count leading zeros
__builtin_ctz(unsigned int)	count trailing zeros
__builtin_ffs(unsigned int)	find first set bit (1-based)
__builtin_popcount(unsigned int)	population count
__builtin_parity(unsigned int)	parity of bits set

■使い方とか

1. _builtin_clz(x)は、xを二進数にしたときの頭の0の数を返します。

10は、2進数だと、

00000000000000000000000000001010
なので、28が返ってきます。

ぱっと思いつく応用は、2^i <= x < 2^{i+1}となるiを求めるとか。

2. __builtin_ctz(x)は、xを二進数にしたときのお尻の0の数を返します。

00000000000000000000000000001010

なので、10の場合は、1です。

これを使うと、一発で、lsbの位置(o-based)が分かります。ただし、lsbを使いたい場合は、1<< lsbという使い方が多いと思うので、そういう場合は、x & -xの方がやすい。

xは、2で何回割り切れる?かを調べたいとき、これを使えば一発。

3. __builtin_ffs(x)は、lsbの位置を1-basedの数字で返します。

__builtin_ffs(x) = 1 + __builtin_ctz(x)

の関係がなりたちます。特にこれと言って便利なシチュエーションは浮かびません。すいません。

4. __builtin_popcount(x)は、1が立っているビット数を返します。

10の場合は、2が返ってきます。この関数はビットで集合を表す場合に、重宝します。

5. __builtin_parity(x)は、1が立ってるビットのパリティなので、以下の関係が成り立ちます。

__builtin_parity(unsigned int) = __builtin_popcount(x) % 2

これは、包除原理の足すか引くかの判定のときに、使えます。