2013/12/24

無限多倍長整数の右シフト

Bignumには右論理シフトが無い、という記事

オーバーフローとシフト演算

おそらく、Javaの場合は最上位bitが符号bitになるんで、シフト対象がわかりますが、Rubyの場合は最上位bitがわかりません。 たぶん型という概念がないんで、最上位bitが32bit目なのか、64bit目なのがわからないんでしょう。

Javaのコードを移植する場合は右論理シフトも要注意です。

論理シフトが無いというより、区別の意味が無いと言った方がいいかなあ。

有限桁数で考えると「最上位bitの扱いの違い」が目につくんだけれど、 無限多倍長整数(2の補数表現)の場合、左には無限にビットが続いていると考える。 正の数なら0が、負の数なら1が無限に続いている。

  5  : ....0000101
 -5  : ....1111011

右シフトする時は単にそのいくらでも続いてるところから0や1が供給 されるだけなんで、算術とか論理とかの区別を持ち込む余地がないのだ。

与える数を有限の範囲でぶった切ってやれば、論理シフトの振る舞いが得られる。

  (define |2^32-1| (- (expt 2 32) 1))
  
  (ash -10 -1)  => -5                          ; -10 >> 1
  (ash (logand -10 |2^32-1|) -1) => 2147483643 ; -10 >>> 1

「左に無限に続いている」という振る舞いは、各種ビット演算で 確かめられる。

  (logbit? 100 -1) => #t  ; -1の100ビット目は1

なお、上の記事中のinteger overflowについては、0を中心としたmoduloが あれば一発である。R6RSのmod0がそのものずばり。

  (mod0 (+ 2147483647 1) (expt 2 32)) => -2147483648

Tag: Programming