java 乗算をシフト演算と加算を割り算で表現する方法

「二つの任意の正の整数の乗算（＊）を、シフト演算の組合わせと除算（／）と加算（＋）のみで解くプログラムを作成しなさい」という課題が出ました。どのようにプログラムを書けばいいか見当がつきません。良ければ教えて下さい。お願いします

No.6 回答者： Tacosan 回答日時： 2021/02/11 02:51

もうちょい細かい条件を追ったところ, おそらく

・加算
・右シフト
・代入またはメソッド呼び出し
の 3つの演算があればあとは努力と根性でなんとかなる. 左シフトは加算 (と代入またはメソッド呼び出し) で代用できるのでなくてもいける. 型を固定すれば比較も使わずにすみそう.

ただし「なんとかなる」だけであって
かなりアホなプログラム
になる.

No.5 回答者： Tacosan 回答日時： 2021/02/05 03:47

Java の言語仕様を確認してみた.

厳密な意味で「シフト演算の組合わせと除算（／）と加算（＋）のみ」っていわれると
比較や代入ができない
のでなんともならん気がする. あと, 「任意の正の整数」で 9^9371 とかもってこられるとさすがにアウトだと思う.

「int (または long) で表すことのできる正の整数で結果もその範囲に収まる」なら, シフト・加算・比較・代入の 4つでいける. むしろ除算が不要.

No.4 回答者： tknakamuri 回答日時： 2021/02/04 09:48

ビット演算は禁止？

No.3 回答者： Tacosan 回答日時： 2021/01/30 23:50

かなり変態的な操作になるけど, 左シフトと右シフトを駆使すれば除算や減算は不要な気がする＞#2.

例えば
x << 28 >>> 31
で x の下から 3ビット目あたりが出てきそう.

No.2 回答者： spookyaction 回答日時： 2021/01/30 14:20

＃１ですが、先の回答ではシフトと加算については触れているが、除算の用途について言及していないので、それについてちょっと追加。

この問題での除算の用途は、10x7を例にすると、7を４＋２＋１に分解するのにつかわれます。7 -> 4+2+1は乗数（あるいは被乗数）を2の累乗の数の和に分解しています。
7を２の累乗数である４で割った余りが３となり、その３を２で割った余りが１となる。こういう演算を繰り返すことによって、乗数を２の累乗の和に分解するわけだが、ここで除算が使われる。ただ剰余演算は使えないということだろうから、余りを求めるには除算と減算を使う必要があると思うのだが、減算も使えないとなるとそのあたりちょっと工夫が必要になるでしょう。

No.1 回答者： spookyaction 回答日時： 2021/01/30 13:03

課題なので、ヒントだけ。

たとえば、10x7をどう実行するか考える。
10x7 = 10 x (4+2+1) = 10x4 + 10x2 + 10x1
10x4は二進にすると、１０の二進数を左に2ビットだけシフトしたもの。
10x2は二進では、１０の二進数を左に1ビットだけシフトしたもの。
10x1はなにもしない。
これらを足し合わせれば10x7を求めることができます。