人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: riceflow
●カテゴリ:コンピュータ 学習・教育
✍キーワード:サイト シフト 奇数 演算 3分
○ 状態 :キャンセル
└ 回答数 : 4/4件

▽最新の回答へ

1 ● Sampo

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;

}


2 ● uochoco

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 ときたひにゃシフトも遅けりゃ除算も遅い。その代わり加減算はむちゃくちゃ速い)。


3 ● aki73ix

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ビットシフトの累積を計算します


4 ● quintia

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:小数 引き戻し法


などが参考になるかと。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ