*を使わずに掛け算の結果を出すには？

解決

レイ 2001-11-26 10:25:06 No: 50010

Ｃ言語で２つの整数の積を出す場合
*を使いますが、
それを使わずに
ビット演算子を使って結果を出したいのですが、
どうすればいいでしょうか？

新参 2001-12-08 11:50:53 No: 50011

初めまして、新参と申します。

掛け算を筆算でやるとき,掛ける側を一桁ずつ計算して足しますよね。
同じ事を1ビット単位でやれば可能です。

[ex: 45 * 5]
45 = 0x2D = 00101101 B
5 = 0x05 = 00000101 B
          ----------
            00101101
           00000000
          00101101
         00000000
        00000000
       00000000
      00000000
     00000000
     ---------------
     000000011100001 B = 0xE1 = 225

forループと +, << 演算子で計算可能です。
<< は乗算みたいなもんだから使っちゃダメということでしたら
(a + a) == (a << 1) ということで…。

long mlt(long a, long b)
{
  long data, bit;
  for( data = 0, bit = 1 ; bit ; bit <<= 1, a <<= 1 ) {
    if((b & bit) != 0)  data += a;
  }
  return  data;
}

新参 2001-12-08 11:53:44 No: 50012

↑すいません。行頭のスペースは無視されるんですね。

> [ex: 45 * 5]
> ...
> 000000011100001 B = 0xE1 = 225

の部分は筆算を書いたつもりでしたが,無視してください。(^^;

レイ 2001-12-13 11:27:11 No: 50013

新参さん
ありがとうございました。
やってみます。

xen 2006-03-28 17:13:55 No: 50014

今更なんですが、この内容がいまいち理解できないので
説明してくれるかたいませんか？

Blue 2006-03-28 18:04:40 No: 50015

> いまいち理解できないので
いまいちとか、曖昧すぎです。具体的にドコまでわからないのでしょうか？

C言語関係なしに、シフト演算については理解できていますか？

参考)
http://sinzo.web.infoseek.co.jp/joho/kodogozen/01kagaku/004/point004.htm

# プログラマにとって、基本情報技術者レベルの知識は持っていて当然ではないのでしょうか。。。？

xen 2006-03-28 18:25:18 No: 50016

主にbitがどういう役割をしているかがちょっとわかりません。

Blue 2006-03-28 18:49:29 No: 50017

具体的な値を入れてトレースしてみればわかると思いますよ。

11 × 5 の例)

    1011(=11)
×  0101(=5)
--------
  ↓

    1011
×  0001※
--------
    1011

＋

    1011
×  0100※
--------
  101100

  ↓
    1011(=11)
＋101100(=44)
--------
  110111(=55)

※のところを求めるために使っている。

xen 2006-03-28 18:53:00 No: 50018

わかりました。
わざわざありがとうございました。