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

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

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

よろしくお願いします。

No.3 ベストアンサー 回答者： kaha 回答日時： 2005/06/04 01:49

==================================

「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 回答日時： 2005/06/02 22:21

例えば、

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

この回答へのお礼

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

お礼日時：2005/06/03 10:49

No.1 回答者： jacta 回答日時： 2005/06/02 17:44

符号ビット+絶対値の処理系では、xが-0の場合には成立しません。

1の補数の場合は成立するように思います。