シフト演算で3分の1の様な奇数を実現する方法がわかりません。分かり易く説明されているサイトを教えて下さい。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/03/21 12:37:53
  • 終了:2006/03/28 12:40:03

回答(4件)

id:Sampo No.1

Sampo回答回数556ベストアンサー獲得回数1042006/03/21 13:28:19

ポイント10pt

http://q.hatena.ne.jp/1142912272

ダミーURLで申し訳ありません。

1/3 は2進数表記で 0.10101010101010 … となります。

もとの数を、右に2ビットシフトしては足し合わせていけばいいと言うことになります。

int d =《割られる数》;

int result = 0;

for( d>>=2; d>0; d>>=2 ){

result += d;

}

id:uochoco No.2

uochoco回答回数34ベストアンサー獲得回数02006/03/21 14:10:27

ポイント10pt

http://hw001.gate01.com/uochoco/

【URL は関係ない自分のサイト】


 できません♪ 二進数を右シフトして得られるのはもとの2の累乗分の1の値だけ。奇数どころか割る数が2の累乗でなければできません♪


 次のようにすれば3分の1が得られるはずですが、誤差のためうまくいきません♪(Cの記法。a は int で 32 bit であること)


1/4 + 1/16 + 1/64 + 1/256 + …… = 1/3 なので、


a = (a >> 2) + (a >> 4) + (a >> 6) + (a >> 8) + (a >> 10) +

(a >> 12) + (a >> 14) + (a >> 16) + (a >> 18) + (a >> 20) +

(a >> 22) + (a >> 24) + (a >> 26) + (a >> 28) + (a >> 30);


実際にやってみると、概ね3分の1が得られるが、誤差が大きくて実用にならないことに気づくでしょう。これは無限級数を有限項で打ち切っていることと、右シフトの際、余ったビットが消えてしまうことに基因します。


 ビットが消えないようにするため、a を 16 bit,x を 32 bit として、


x = a + (a << 2) + (a << 4) + (a << 6) + (a << 8) + (a << 10) +

(a << 12) + (a << 14);

x >>= 16;


とすれば、かなり正しい結果が得られます(上限はいくつまででしょう?)。でも a がちょうど3の倍数のときは1少ない結果が得られてしまいます。


 最近の CPU はシフト演算が遅いので実用性はありません(Pentium IV ときたひにゃシフトも遅けりゃ除算も遅い。その代わり加減算はむちゃくちゃ速い)。

id:aki73ix No.3

aki73ix回答回数5224ベストアンサー獲得回数272006/03/21 15:30:25

ポイント10pt

http://www.rd.mmtr.or.jp/~bunryu/touhi.shtml

1/3や1/5、1/7などは等比級数で表現できます

とりあえず、8086の実際のコードとあわせて説明していきます

     ∞

1/3=∑{1/4)^k

     k=1

ですから

単純にもとの数を右に2ビットシフトしたものを加算していけば、1/3の近似値が求められます

実際にコードにするとこんな感じでしょう

  char str[256];

  int t;

  GetWindowText(Edit1->Handle,str,256)

  t=atoi(str),s;

  __asm{

     mov eax,t

     mov ebx,0

     shr eax,2

L1:  add ebx,eax

     shr eax,2

     jnz L1

     mov s,ebx

  }

  SetWindowText(Edit1->Handle,s);

100000000を指定すると33333328となります

これは、下位ビットが切り捨てられてしまった結果なので、改良して、小数点以下の演算をするようにしてみます

  char str[256];

  int t;

  GetWindowText(Edit1->Handle,str,256)

  t=atoi(str),s;

  __asm{

     mov eax,t

     mov ebx,0

     mov ecx,0

     mov edx,0

     shr eax,1

     rcr ebx,1

     shr eax,1

     rcr ebx,1

L1:

     add edx,ebx

     adc ecx,eax

     shr eax,1

     rcr ebx,1

     shr eax,1

     rcr ebx,1

     jnz L1

     and eax,eax

     jnz L1

     add edx,0xb0000000

     adc ecx,0

     mov s,ecx

  }

  SetWindowText(Edit1->Handle,s);

最後に、切り捨てられた数値が一定値以上なら切り上げるようにしてやれば、1/3の値が変えるようになります

100000000を指定すると33333333となりましたね

1/5を求める場合も2ビットシフトを利用しますがちょと式が複雑になります

1/5=1/4-1/4^2+1/4^3-1/4^4....

 ∞

=∑-{{1/4)^k*(-1)^k }

 k=1

  char str[256];

  int t;

  GetWindowText(Edit1->Handle,str,256)

  t=atoi(str),s;

  __asm{

     mov eax,t

     mov ebx,0

     mov ecx,0

     mov edx,0

     push ebp

     mov ebp,0

     shr eax,1

     rcr ebx,1

     shr eax,1

     rcr ebx,1

L1:  and ebp,ebp

     jnz L2

     add edx,ebx

     adc ecx,eax

     jmp L3

L2:  sub edx,ebx

     sbb ecx,eax

L3:  not ebp

     shr eax,1

     rcr ebx,1

     shr eax,1

     rcr ebx,1

     jnz L1

     and eax,eax

     jnz L1

     add edx,0xb0000000

     adc ecx,0

     pop ebp

     mov s,ecx

  }

  SetWindowText(Edit1->Handle,s);


1/7を求める場合は1/3と同様な方法なので

     ∞

1/7=∑{1/8)^k

     k=1

を利用し、3ビットシフトの累積を計算します

id:quintia No.4

quintia回答回数562ベストアンサー獲得回数712006/03/21 22:56:59

ポイント10pt

3分の1は、10進数でも2進数でも有限の桁で表現しきれません。

10進数なら、0.333333... と無限に続きます。

参考

\normalsize\displaystyle \sum_{n = 1}^{\infty}  3 \times 10^{-n} = \frac{3}{10} \sum_{n = 1}^{\infty} (\frac{1}{10})^n = \frac{3}{10} \times \frac{1}{1-10^{-1}} = \frac{1}{3}


2進数なら、3は2進数表記で11なので、普通の10進数の筆算の要領で考えると判りますが、0.0101010101.... と無限に続きます。


いずれにせよ、数学的にはこれら、無限数列の和は収束し 3分の1を示すわけですが、コンピュータ上では有限の桁による近似表現でしか表示できないわけで、「シフト演算」で実現できるものではないです。

おそらく質問の本来の意図は「シフト演算」にこだわるものではなく、一般的なコンピュータ上の実数表現での割り算のアルゴリズムを知りたいのでしょうが……。実際は引き算とシフトの繰り返しで、引くことが出来たら1を立て、引くことが出来なかったら0を立てつつシフトしていく、という手法になります。


http://www.den.rcast.u-tokyo.ac.jp/~suzuki/class/dmedia/doc/...

4ページ 除算の項


http://www.info.kanagawa-u.ac.jp/~uchida/HP-uch/CAArithmetic...

27ページ~


google:小数 引き戻し法


などが参考になるかと。

  • id:yoneyore
    質問しておきながら、質問していたことも忘れていました。申し訳ございません。2.、3.、4.の方の答えが求めていた答えと考えておりますので、2.,3.,4.の方にポイント送ります。
    以上、回答遅くなり申し訳ございませんでした。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません