2^nの掛け算

2の掛け算をするときに、ビットシフトさせたときに0で埋めるか1で埋めるかという疑問がわいた。

10 * 2 = 20の場合
10(10進数)は、00001010(2進数)である(8+2=10だから)

10 * 2 は、２進数では０埋めの1ビットシフトに相当するので、
00010100(2)である １０進数だと16+4=20(10)であるのでこれは正。

-10 * 2 = -20の場合
10(10)は、00001010(2)である(8+2=10だから)
-10(10)は、00001010(2)+X=100000000(2)で桁上がりをおこす数に相当する。
よって、X=100000000(2)-00001010(2)=11110110(2)

10 * 2 は、２進数では1ビットシフトに相当するので、
11110110(2)の０埋めの１ビットシフトは、
11101100(2)である この補数は00010100(2)だから 16+4=20である。
よって、-10 * 2 = -20 が成り立つ。

11110110(2)の1埋めの１ビットシフトは、
11101101である この補数は00010011(2)だから 16+2+1=19である。
よって、-10 * 2 = -19になってしまうので、これは成り立たない。

よって常に、ビットシフトさせて0で埋める。



次に、桁あふれの場合を考えてみる。
10 * 16 = 160の場合
10(10)は、00001010(2)である(8+2=10だから)
10 * 16 は、10 * 2^4 なので、２進数では4ビットシフトに相当する。
00001010(2)の単純な4ビットシフトは、10100000(2)である。
これは、符号反転を起こしていて、-01100000(2)=-96である。
符号付き8ビットという制限がある場合、表現できる数は、
-128〜0〜127(10) 80〜00〜7F(16) 10000000〜00000000〜01111111(2) である。
よって、オーバーフローをおこしている。これを抑制して。
 a=10;
 b=16;
 cal=a * b;
 if    ( cal > 127  ) then ans= 127;
 elsif ( cal < -128 ) then ans=-128;
 else  ans=cal;でなにもしない
といったような処理が"今回は"必要になる。

ここからは、VHDL風に記述してみる。

a(7 downto 0) <= "00001010"; の正の数の場合、つまりa(7)='0'の場合。
4ビットシフトさせる場合には、桁上がりして残らない4ビット
つまり、a(6 downto 3) のうちどれか1である時、に　
ans<=127 つまり ans<="01111111";で最大値を返す。
 if ( a(7)='0' ) and
    ( ( a(6) or a(5) or a(4) or a(3) ) = '1' ) 
  then
    ans<="01111111";
 end if; 

a=-10
a(7 downto 0) <= "11110110"; の負の数の場合、つまりa(7)='1'の場合。
4ビットシフトさせる場合には、桁上がりして残らない4ビット
つまり、a(6 downto 3) がいずれか0である時、
各ビットをnotしてどれかが1であるときに　
ans<=-128 つまり ans<="10000000";で最大値を返す。
 if ( a(7)='1' ) and
    ( ( not a(6) or not a(5) or not a(4) or not a(3) ) = '1' ) 
  then
    ans<="10000000";
 end if; 

次回に続く。

ここから嘘！

<del>ここで、排他的論理和 xor を使うと、
  x y (x xor y)
  0 0     0
  0 1     1
  1 0     1
  1 1     0
となる。

よって、目的は、どれかのビット全て一緒か否かを判定すればよいので、
 ( a(6) xor a(5) xor a(4) xor a(3) ) ='1'
と統合することができる。

 統合すると、
  if ( a(6) xor a(5) xor a(4) xor a(3) ) ='1' ) then
    if a(7)='0' then ans<="01111111";
    else             ans<="10000000";
    end if;
 end if; 

で書き表せる。</del>

ここまで嘘

( よく、00001010(2)の補数は、11110110(2) という )
( ※ 68(10)の補数は32(10) そろばんを昔"習わされた"人ならよくわかると思う、わからない人はそろばんで視覚的に理解できるとおもう。というか、引き算で皆無意識にやっているはず ）

※（人間が計算できるレベルでやるので、８ビット固定の符号付き(C言語っぽい表現だと）signed int8)とした。