算術右シフトの結果が1/2になる証明がわからない

nビットで符号つき 2 進数で表現できる偶数xを右に１ビット算術シフトして得られるビット並びをnビット符号つき 2 進数として見た数を yとする。y = 1/2*x で あることを証明したいのですが、そう証明すればいいかわかりません。

No.3 回答者： tatsumaru77 回答日時： 2020/09/04 18:16

値が０以上の場合に限定です。

例として８ビットの数値で考えてみます。
偶数なのでシフト前のビットは"①②③④⑤⑥⑦０"になっているはずです。（①～⑦は１又は0のどちらかのビット状態とする）
右に１ビット算術シフトすると"０①②③④⑤⑥⑦"になります。
シフト結果のビットを２倍すると、シフト前と同じになることが証明できれば良いので、
シフト結果のビットを２倍します。筆算で行います。
　①②③④⑤⑥⑦・・・・シフト結果
　　　　　Ｘ１０・・・・２（2進数の１０）
－－－－－－－－－
　０００００００・・・・２の０乗
①②③④⑤⑥⑦　・・・・２の１乗
－－－－－－－－－－－－
①②③④⑤⑥⑦０・・・・２倍した結果

よって、シフト前と同じ値になることが証明されました。

No.2 回答者： cametan_42 回答日時： 2020/09/03 18:39

うーん、この辺参考になるかしらん。

ソフトウェア基礎技術研修-3:
http://ocw.kyushu-u.ac.jp/menu/faculty/09/4/3.pdf

例えば、nビットで符号つき2進数で表現出来るxを

x = ((-2)^(n-1)) * a_{n-1} + Σ(2^k)*a_k ... k = 0〜n-2

と表現して、偶数なのでx mod 2 = 0が前提となる。
右シフトした数yは

y = ((-2)^(n-2)) * a_{n-2} + Σ(2^k)*a_k ... k = 0〜n-3

なので、yをちょっと弄っていけば1/2*xに落ち着いて、終了、とか言うカンジですかね?

No.1 回答者： cametan_42 回答日時： 2020/09/03 17:39

えええええ・・・「証明する」の?

当たり前だと思ってた事を「証明する」ってのは難しいなぁ・・・。

そもそも2進数なんで、桁数が上がれば「2倍」になるわけですよ。自然に。っつー事は桁数が下がれば1/2ですよね。「算術シフト」とかつや～な言い方せんでも「そうならざるを得ない」。
そうならざるを得ない事を「証明しろ」・・・・どないすんねん。

"1" # 1
"10" # 2
"100" # 4
"1000" # 8
"10000" # 16
"100000" # 32
"1000000" # 64
"10000000" # 128
"100000000" # 256

眺めてみれば「でしょ?」
10進数でも桁数上がれば10倍になる・・・っつーか逆に、基本の数「1」の10倍になった時に桁数が上がるのを「10進数」って定義してるわけね(n桁上がれば10^n倍になる)。同じ論法が2進数にも適用される・・・基本の数「1」の2倍になった時に桁数が上がるのを「2進数」としてるわけですよ。従って桁数がn個上がれば基本の数の2^n倍になる。当たり前(逆も考えてみよう)。
その「当たり前の仕組み」を証明する・・・無理なんじゃね(笑)。どうなんだろ。

この回答へのお礼

回答ありがとうございますーー！！

そうなんです。
私もなぜそうなるのかはわかるんですけど、証明問題が出て解けなくて困ってます。。。泣

お礼日時：2020/09/03 17:58