演算子を使わない掛算

Question

ｃ＋＋言語の質問です。演算子*を使わずに2個の整数同士の掛け算を出力する方法が分かりません。どなたか教えてくださるとありがたいです。よろしくお願いいたします、

Comments

[jimbe]

c++ のご質問でしたら、タグを c では無く c++ にしてください。

Answer 1

真面目に回答しておきましょう

あなたが、XXX * YYY という問題を出されたとき、筆算でどうやってそれを解くでしょうか。
まさか３桁どおしの掛け算ができないとは言いませんよね？
その方法をそのとおりに、コードにしていけばいいのです

Comments

[episteme]

ひと桁どおしの掛け算に演算子*を使わない方法を説明しないと回答にならない。低評価。

[y_waiwai]

まさに、この問題のキモはそこにあります

１０進数の掛け算をする場合には、*は必要なのかもしれません（あえて、九九のテーブルを使用するなどということは想定しないでおきます）
さて、これを、２進数の掛け算を記述する場合とすると、＊は必要とするんでしょうか

[episteme]

べつに何進数であろうが加算で代替できる。

[y_waiwai]

それがすべてですよｗ

[episteme]

筆算するとき、加算を何度も繰り返すんですか?

[y_waiwai]

そうしてもかまいませんけどねーｗ

[episteme]

筆算を例えに出した意味がないんじゃ?

[kairi003]

ビットで筆算みたいに考えれば計算量がO(N)からO(log(N))まで落ちるのでそういう話じゃないですか？

[kairi003]

「乗算演算子を使わない乗算の実装」の課題をやる人がビット演算を求めているのかはさておき…

[Zuishin]

落ちますか？

[kairi003]

A*Bとして、Bのビットを見て1の桁は桁数分Aを左シフトして足しこむ、みたいな実装すれば、Bを2進数解釈する→最大log_2(B)回のループで済むと思ったのですが

[Zuishin]

なるほど 10 倍するのであれば 4 回ずつ(合わせて 8 回)シフトして 2 倍と 8 倍の二回加算すればいいということですね？

整数としか書いていないので非常に大きな桁の演算に対応するということですか。

一つの方法ではあると思いますが、大喜利なら回答者が自分でコードを書かないと。

[kairi003]

回答者が筆算を例に上げており，２進数の掛け算がどうこういってるのでこんな意図かなと考えた次第です．
不親切で迂遠ですが，質問は明らかに課題っぽいし，そこまで外れた回答でもないと思ったのでここまで低評価がつくのはちょっと可愛そうかなぁと．

[y_waiwai]

まあしかし、加算とシフトで乗算を構成するってのはある意味常識みたいなもんだと思ってましたが、そーでもないんですね

[kairi003]

それを常識として認識している人はこの質問しないと思います...
私はy_waiwaiさんの回答は別解として良いと思いますが，初等な教科書なら発展枠で書かれそうだと思いました

[kairi003]

低評価する人たちという意味ならまぁ，そうですね

[Zuishin]

競技プログラミングなどで多倍長演算するなら普通にやりますが、初心者の課題で「真面目な回答」とあらかじめ言った上でコードもなしに回答する人は他にいないでしょうね。

[episteme]

多桁の筆算に使われるのは 「シフト と 加算 」 じゃない。 「N進数のN倍 と 加算」です。
N=2 のとき(所謂)左シフトと同義になるだけ。

Answer 2

0 + x + x + x + .... のように、0 に x を y 回足せば x＊y が求まります。

Comments

[episteme]

ﾍﾞﾂﾄｱﾝｻｰ貰えるとは思わなんだwww
何かよっぽど難しく考えてたんでしょか?

[episteme]

おや、BA外れた...

[kimuchiiii]

使い方がわからず、間違えてタップしていたようです^^;すみません。
ご回答ありがとうございました。

Answer 3

ｃ＋＋言語の質問です。演算子*を使わずに2個の整数同士の掛け算を出力する方法が分かりません。

次のコードを C++ に書き直してみてください。

#include <stdio.h>

int main(void)
{
	int a, b, c = 0;
	if (scanf("%d%d", &a, &b) != 2) return 1;
	for (int i = 0; i < 32; i++)
		if (b >> i & 1) c += a << i;
	printf("%d\n", c);
}

オーバーフローは考慮していません。

追記
別解

	for (; a; a <<= 1, b >>= 1)
		if (b & 1) c += a;

追記2
ビット演算を使わないコードです。

#include <stdio.h>

int main(void)
{
	int a, b, c = 0;
	if (scanf("%d%d", &a, &b) != 2) return 1;
	for (; a; a += a) {
		if (b % 2) c += a;
		if (b < 0) b--;
		b /= 2;
	}
	printf("%d\n", c);
}

Comments

[kimuchiiii]

解決できました！丁寧にありがとうございました！

[kazuma-s]

どのやり方で解決したのですか？
丁寧ではありません。コードを提示しただけで何の説明もしていません。
意味を理解するのはあなたです。
どうしても理解できないのであれば、どこが分からないかを質問してください。

Answer 4

まず、私の過去回答を参考にしてください。

質問者さんはプログラミングとかを置いといて、『現実世界でならどうするか』を考えたとき、どうしますか？

つまり、算数とかの問題で、『掛け算を使わずに、掛け算(と同等のこと)をせよ』
みたいな感じでしょうか。

例えば3×5を掛け算を使わずに計算する感じです。

掛け算は『足し算を簡略化したもの』ですから、

3×5は『3を5回足したもの』と考えることができますね。

つまり、

3+3+3+3+3

ですね。

これを計算するとき、どうしますか？

私は計算が苦手なので、一つずつやります。

まず3+3をする。6ですね。
この6をノートかなんかに書いておく。
これを記録Xとする。

次に記録Xに+3する。
つまり、6+3=9ですね。
そのまま記録Xを更新する。
(6から9に)

そのまま記録Xに+3する。
9+3=12なので、記録Xを12に更新する。

…とやっていくと、最終的に記録Xが3×5の答えになりますね。

で、最初の3+3以外は常に

記録X = 記録X + <数字>

となっていますね。

でも、最初の3も、

記録X=0

と考えると、0+3=3なので、この規則性は完全に満たします。

これをC++ならC++の書き方で書き下せば良いだけです。

ノートに書いた記録Xは、C++だとノートには書けないので、『変数』で代用。

後はわかりますよね？

Comments

[kimuchiiii]

なんとかできました。丁寧なアドバイスありがとうございました。

Answer 5

前もって掛け算九九みたいなテーブルを用意して，それを使う．

• a * b を計算するとき，テーブルからダイレクトに答えを引けるなら使う．
• 答えを引けないときは，一方の側をより小さい２つの整数に分割する．
  例えば，b を b = c + d として， (a*c) + (a*d) という問題にする．

// 0*0 ～ NT*NT までの結果を引けるテーブルTbl[][]
constexpr unsigned int NT = 10;
unsigned int Tbl[NT][NT];

//※ここでは面倒だからこの関数でTbl[][]の中身を掛け算で作ってるけど，
//  ちまちまと値をハードコーディングなりすればよいかと．
void InitTbl()
{
    for( unsigned int a=0; a<10; ++a )
    {
        for( unsigned int b=0; b<10; ++b )
        {   Tbl[a][b] = a*b;    }
    }
}

//Tbl[][]を使った処理処理．
unsigned int Mul_u( unsigned int a, unsigned int b )
{
    std::stack< std::pair<unsigned int, unsigned int> > Stk;
    Stk.emplace( a,b );

    unsigned int Ans = 0;
    while( !Stk.empty() )
    {
        unsigned int a,b;
        {
            auto X = Stk.top();
            Stk.pop();
            a = X.first;
            b = X.second;
        }

        if( a==0 || b==0 )continue;

        if( a<NT && b<NT )
        {   Ans += Tbl[a][b];   }
        else if( a >= b )
        {
            unsigned int ha = a>>1;
            Stk.emplace( ha, b );
            Stk.emplace( a-ha, b );
        }
        else
        {
            unsigned int hb = b>>1;
            Stk.emplace( a, hb );
            Stk.emplace( a, b-hb );
        }
    }

    return Ans;
}

//a * b の計算
int Mul( int a, int b )
{
    bool Neg = ( (a<0 && b>0) || (a>0 && b<0) );
    unsigned int AbsAns = Mul_u( abs(a), abs(b) );
    return ( Neg ? ( 0 - AbsAns ) : (int)AbsAns );
}

int main(void)
{
    InitTbl();

    int a = 15;
    int b = -88;
    std::cout << Mul(a,b) << std::endl;
    return 0;
}

Comments

[fana]

テーブルの大きさを育てていけば処理が高速になる可能性！