算術演算子を使わずに乗算する方法

Question

演算子を使わない方法が思いつかない

どういう考えで算術演算子を使わずに乗算すればいいかわかりません。
考えたのですが、全然思いつきませんアドバイスでいいので助けてください。

Comments

[mather]

なぜ「算術演算子を使わずに乗算」する必要があるのですか？学校の課題などでしょうか？

[dice142]

過去の質問から察するに学校の課題ですよね？何かしら参考資料が提示されてるのではないですか？

Answer 1

算術演算を論理演算で代用したいという目的であるという前提で検討しました。

考え方を以下に示します。
まず掛け算の前に2つの整数の和を、論理演算子で記述する方法を考えます。
①2つの整数の排他的論理和を取ります。これは繰り上がりがない場合の足し算の結果に等しいです。
②2つの整数の論理積を取ります。bitが1となっている桁は繰り上がりが発生する桁を意味します。
③上記の②の結果を1bitシフトしたものと①の結果について、再び排他的論理和と論理積を取ります。
④上記の③を排他的論理和または論理積が0になるまで繰り返します。これは繰り上がりがなくなることを意味します。
⑤最終的に算出された排他的論理和と論理積の論理和(一方は0なので排他的論理和でもよい)が2数の和になります。
掛け算の場合は、2数が同じ数値という前提で、繰り返す回数を指定すればよいです。

2数の和の計算を論理演算子のみで実現するコードは以下です。

int bitSum(int numA, int numB){
    int result;
    int bitAND;
    int bitANDOld;
    int bitEXOR;
    int bitEXOROld;

    bitANDOld = numA;
    bitEXOROld = numB;
    while(bitEXOROld !=0 && bitANDOld !=0){
        bitAND = (bitANDOld & bitEXOROld) << 1;
        bitEXOR = bitANDOld ^ bitEXOROld;
        bitANDOld = bitAND;
        bitEXOROld = bitEXOR;
    }
    result = bitANDOld | bitEXOROld;

    return result;        
}

掛け算の場合は以下のコードで実現できます。
*for文中の++はご容赦ください。

int bitProduct(int num, int multiple){
    int result = num;
    int bitAND;
    int bitANDOld;
    int bitEXOR;
    int bitEXOROld;

    for(int i = 0; i<multiple -1;i++){
    bitANDOld = num;
    bitEXOROld = result;
    while(bitEXOROld !=0 && bitANDOld !=0){
        bitAND = (bitANDOld & bitEXOROld) << 1;
        bitEXOR = bitANDOld ^ bitEXOROld;
        bitANDOld = bitAND;
        bitEXOROld = bitEXOR;
    }
    result = bitANDOld | bitEXOROld;
    }
    return result;        
}

Answer 2

インクリメントとデクリメントだけで四則演算を全て実装してみました。算術演算子禁止として、Arithmetic operators - cppreference.comにある全ての演算子を使用しないようにしました。また、whileやforおよびgotoを用いたループも禁止しました。

/**
 * Implementation of arithmetic operators without using arithmetic operators.
 * https://en.cppreference.com/w/c/language/operator_arithmetic
 */

#define NDEBUG
#include <assert.h>
#include <stdio.h>

int plu(int a);	// +a
int min(int a);	// -a
int add(int a, int b); // a + b
int sub(int a, int b); // a - b
int pro(int a, int b); // a * b
int div(int a, int b); // a / b
int mod(int a, int b); // a % b

int plu(int a) { return a; }

static inline int min_inc_r(int a, int b)
{
	if (a == 0) return b;
	assert(a < 0);
	return min_inc_r(++a, ++b);
}

static inline int min_dec_r(int a, int b)
{
	if (a == 0) return b;
	assert(a > 0);
	return min_dec_r(--a, --b);
}

int min(int a)
{
	if (a == 0) return 0;
	if (a < 0) return min_inc_r(a, 0);
	return min_dec_r(a, 0);
}

static inline int add_r(int a, int b)
{
	if (b == 0) return a;
	assert(b > 0);
	return add_r(++a, --b);
}

int add(int a, int b)
{
	if (b < 0) return min(add(min(a), min(b)));
	return add_r(a, b);
}

int sub(int a, int b) { return add(a, min(b)); }

static inline int pro_r(int a, int b, int r)
{
	if (b == 0) return r;
	assert(b > 0);
	return pro_r(a, --b, add(r, a));
}

int pro(int a, int b)
{
	if (b == 0) return 0;
	if (b < 0) return pro(min(a), min(b));
	return pro_r(a, b, 0);
}

static inline int div_r(int a, int b, int r)
{
	assert(b > 0);
	if (a == 0) return r;
	if (a < 0) return --r;
	return div_r(sub(a, b), b, ++r);
}

int div(int a, int b)
{
	if (b == 0) return 0; // or error
	if (b < 0) return min(div(a, min(b)));
	if (a < 0) return min(div(min(a), b));
	return div_r(a, b, 0);
}

int mod(int a, int b) { return sub(a, pro(div(a, b), b)); }

int main(void)
{
	printf("+42 = %d\n", plu(42));
	printf("-42 = %d\n", min(42));
	printf("7 + 6 = %d\n", add(7, 6));
	printf("7 - 6 = %d\n", sub(7, 6));
	printf("7 * 6 = %d\n", pro(7, 6));
	printf("7 / 6 = %d\n", div(7, 6));
	printf("7 %% 6 = %d\n", mod(7, 6));
}

div()は、0除算でエラーにならない事を除き、標準の/と動作を合わせたつもりです、たぶん。**速度は全く考慮に入れていません。**インクリメントのオーバーフローやデクリメントのアンダーフローは考慮していませんが、末尾再帰になっていますので、適当に最適化オプションを付けていればスタックオーバーフローは起きないはずです。assert()を有効にしたい場合は#define NDEBUGをコメントアウトしてください。ビット演算子やシフト演算子の実装については力尽きましたので、誰かがやってくれることでしょう。

Answer 3

論理演算子は既に出ているので別の方法で。

本来何を解決したいかわからないので検討違いならすみません。

BigDecimal two = new BigDecimal("2.00");
BigDecimal three = new BigDecimal("3.00");

BigDecimal multiply = two.multiply(three);
System.out.println("結果: " + multiply);

以下追記

C言語でしたね、見落としていましたすみません。
GMPという多倍長計算を非常に高速に行うライブラリがあるのでそれを使いました。

#include <stdio.h>
#include "gmp.h"

int main(int argc, char **argv)
{
    mpz_t a, b, x;
    mpz_init(x);
    mpz_init_set_str(a, "2", 10);
    mpz_init_set_str(b, "3", 10);

    mpz_mul(x, a, b);

    mpz_out_str(stdout, 10, x);

    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(x);
}

Comments

[yukkuri]

この質問はCについてなので、オブジェクト指向のJavaは違う気がしますがどうなんでしょう。

[moonphase]

はい、ご指摘の通りでした・・・Cでの回答を追記しておきました。

Answer 4

論理演算とシフトである程度出来ます。・・・全部は思いつかない；；

論理演算と算術演算

a=(1|(1<<2))→５とか・・・

５×３だと・・(5<<1)+5なんだが・・・“＋”をどうするか？？
・・・例が悪かった＾＾；　1010|101→1111→15・・出来ちゃたｗ
ビットが重ならなければor('|')でなんとかなるが・・・８×３は・・(8<<1)|8で出来る

Comments

[pepperleaf]

リンク先に書いてありますね。
bitだったら、 and すれば、繰り上がりが分かるって。
Xor かと思ったが、大差無い? 複数bitはもう一ひねり必要か。

Answer 5

「乗算器」とかで検索したらどうか？

Answer 6

とりあえずコードだけ。

#include <stdio.h>

int add(int n, int m)
{
	if (n & m){
		return add(n ^ m, (n & m) << 1);
	}

	return n | m;
}

int mul(int n, int m)
{
	int result = 0;

	for ( ; n && m; n >>= 1, m <<= 1){
		if (n & 1){
			result = add(result, m);
		}
	}

	return result;
}

int main()
{
	int n = -100;
	int m = -10;

	printf("%d * %d = %d\n", n, m, mul(n, m));

	return 0;
}

Comments

[YOshim]

そうそう！
私がやりたかったのは正にこれです。
やはり再帰は素晴らしいですね。

Answer 7

シフト演算すれば
i*2 = i<<1
という感じで乗算できますよ。

Answer 8

shsh_さんが再帰を使った方法を載せてますが、再帰を使わない場合は次のようになります。（addの部分だけ）

int add(int a, int b)
{
    while (b != 0)
    {
        int c = (a & b) << 1;
        a ^= b;
        b = c;
    }
    return a;
}

Answer 9

具体的なコードはしめしませんが、つぎのような方針は如何でしょう？

1. 九九の表(一桁の数同士の乗算)と 一桁同士の足し算の表を用意する。
2. 筆算と同様の方法で 上の２つの表を引きながら計算をしていく。

筆算は普通は 10 進でおこないますが、２進数で筆算処理をするなら、小さな表を用意するだけで済ますことができます。
(２進数 <-> １０進の表記変換にいろいろ演算が必要になりますが,それもこの方法で対処できるでしょう)