読者です 読者をやめる 読者になる 読者になる

ビット演算関連

基本

フラグとして使ったりするときに必須なやつ。

a|=bでフラグを立てる。
a&=~bでフラグを折る。
a^=bでフラグを反転。

シフト

  • <<で左シフト。0で埋められる。
  • >>で右シフト。算術シフトか論理シフトかは決まってないらしい。
    • 算術シフト:最上位ビットはシフト前のが継承されるので、負数も2でわった感じになる。
    • 論理シフト:最上位ビットは0になる。
  • ちなみに手元のLinux(GCC4.3.4,x86)で試したら、signedは算術、unsignedは論理だった。まあさすがにunsignedが論理シフトは仮定していいと思うんだけどどうなんだろう。

ちなみに有名な話だが、シフトの性質上、算術右シフトは端数を負の無限大方向に切り捨てる。除算だと0方向に切り捨てる場合が結構あって、実際C99ではそういう仕様っぽいので、そこを区別するのは重要だとかなんとか。
除算よりも高速に行えるとか、2のべき乗での除算が簡潔に書けるとかいろいろ便利。
ちなみに

nビットより上位のビット列:i>>n==i/(1<<n)
nビットより下位のビット列:i&((1<<n)-1)==i%(1<<n)

とかそういうのもよく使う。

ビットフィールド

いまどき誰も使わないビットフィールド。

union ieee754double {
    double val;
    struct {
        unsigned sign : 1;
        unsigned exp : 11;
        unsigned frac : 52;
    } elems;
};

とかそういうやつ。フラグの管理方法の一種として使えなくもない。

浮動小数点数

浮動小数点数でビットシフトは無理だけどそれっぽいことはできる。
というのはIEEE754は2のべき乗と仮数の積で表したりしてるからなんだろうけど、これをラップした関数があって、それがmath.hのdouble ldexp(double,int)。まあ使いかたは見ればわかるだろ。逆に2進桁数を知りたかったらfrexpだけどこれもマニュアル参照。

あとIEEE754はWikipediaのにざっと目を通すだけで面白いので見るといいと思う。整数として比較できるあたりで感動した。

GCCの__builtin関数

で、今までのはついででこれが本題。

  • int __builtin_clz(unsigned int)

最上位ビットから数えてゼロの連続する個数。つまり2進桁数の大小をひっくり返したような数。
int e;frexp(i, &e);とすると、e+__builtin_clz(i)==sizeof(unsigned int)*8==32になる。

  • int __builtin_ctz(unsigned int)

最下位ビットから数えてゼロの連続する個数。0に対する答えは未定義だけどうちの環境では-1になった。
0以外のiについて、i&-i==1<

  • int __builtin_ffs(unsigned int)

最下位ビットから数えて最初に出現する1の位置(最下位ビットの位置を1とする)。0に対する答えは0。
0以外の数値に対しては、__builtin_ctz(i)+1==__builtin_ffs(i)が成立する。

  • int __builtin_popcount(unsigned int)

引数の2進表記中に出現する1の個数。

  • int __builtin_parity(unsigned int)

__builtin_parity(i)==__builtin_popcount(i)&1、らしい。

上記の関数は、__builtin_popcountl(unsigned long int)のようなlong用関数やlong long 用関数も定義されている。

個人的にはビットリバースがないのが残念。バイトオーダーを反転する__builtin_bswap{32,64}はあるのに。