C言語「K&R」の演習2-9について

質問

「プログラミング言語C」、Ｋ＆Ｒの演習2-9についてです。

「2の補数系では、x & (x - 1) により、xの右端の1ビットが消える。なぜか説明せよ。この事実を使って、もっと速いbitcountプログラムを書け。」の前半部分（～を説明せよ）が分かりません。1の補数系ではこうならないのでしょうか？

よろしくお願いします。

回答No.3

kaha · ベストアンサー

==================================
「Cアンサー・ブック　啓学出版」より
==================================
解答

bitcount(n)
unsigned n;
{
　int b;
　for(b=0; n!=0; n&=n-1)
　　　++b;
　return(b)
}

x-1の値の例として２進で1010(10進で10)を考えてみましょう。(x-1)+1はxになります。
2進　　　　　 10進
1010　　x-1　 10
+　1　　　　　+　1
----　　　　　----
1011　　 x　　 11
2進数においては、x-1に1を加えた場合、x-1のもっとも右の0ビットがxにおいて1となります。したがって、xのもっとも右の1のビットに対応するx-1のビットは0となります。これが2の補数を用いている数において、x&(x-1)がもっとも右の1のビットをクリアする理由です。
　4ビットの符号なしの数を考えてみましょう。この数のすべての1のビットを数えるために、もとのbitcountではもっとも右のビットを調べるために4回のシフトを行っていますが、代わりに、"x&(x-1)がxのもっとも右のビットをクリアする"という知識を使うことができます。例として、xを9としてみましょう。
1001　2進であらわした9 (x)
1000　2進であらわした8 (x-1)
----
1000　x&(x-1)
もっとも右の1のビットがクリアされています。結果の値は、2進で1000、10進で8となります。さらに同じことを繰り返します。
1000　2進であらわした8 (x)
0111　2進であらわした7 (x-1)
----
0000　x&(x-1)
ここでももっとも右の1ビットがクリアされます。結果の値は、2進で0000、10進で0です。もうxには1のビットがないので、プロセスは終了します。
　もっとも条件のの悪い場合、すなわちxのすべてのビットが1の場合、ANDを行う数はもとのbitcountのシフト数と同じです。結局、こちらのほうが速いバージョンであるといえます。

回答No.2

BLUEPIXY

例えば、
xとして、奇数の５と偶数の６の場合を考えてみます
ｘ－１の２進表現は（４と５）
１００と１０１です。
ここで、＋１してみることを考えると
１００，１０１
００１，００１＜＋する
１０１，１１０になります。
これは、キャリーの生じる生じない場合に依って
一番右側の０を１にするということになります。
（０に＋１しても桁上げが生じないが１の場合桁上げするから）
このことは、逆に言うとｘの一番右側の１のビットに対応するｘ－１のビットは、０になるということです。
１の補数系ではｘ－１＋１がｘにならない場合があるということだと思います。

お礼

解答していただき、どうもありがとうございました。
でも、「ｘ－１＋１がｘにならない場合がある」ということは、１の補数系で計算するのって大変だなって思っちゃいました、単純に。

回答No.1

jacta

符号ビット+絶対値の処理系では、xが-0の場合には成立しません。1の補数の場合は成立するように思います。