C言語関係掲示板

過去ログ

No.232.ビットカウント


No.1419

教えてください
投稿者---m(2002/04/17 11:46:54)


int bitcount(unsigned x)
{
int i;

for ( i = 0; x != 0; x &= x-1 ) {
++i;
}
return i;
}

何故x &= x-1 で1のビットを数えることができるのでしょうか?
教えてください

No.1421

Re:教えてください(ビットカウント)
投稿者---kikk(2002/04/17 13:23:14)


ども。


>何故x &= x-1 で1のビットを数えることができるのでしょうか?

x &= x-1 だけだと、下位ビットからみていって最初にみつかった1が
セットされているビットを0にする、という動作になります。これを
ループに組み込んで、ビットカウントを行うことができます。

x-1 はビット列でいうと、xを下位から見ていって最初にみつかった1を
0にし、それまでの0を1にするという操作ととらえることもできます。
これは、最初にみつかった1を含めてそれ以下のビットを反転するとも
いえます。したがって、もとのxと & をとると上記のような効果が得られ
ます。

実際に紙とペンで確かめてみるとよろしいかと。その際、引けなかったとき
に発生する借り(borrow)が上位に伝播していくのを確認するとわかると思い
ます。
# 紙とペンはものづくりの必需品です


では。

戻る


「初心者のためのポイント学習C言語」 Last modified:2002.06.22
Copyright(c) 2000-2002 TOMOJI All Rights Reserved