2018/07/12 公開
・足し算とﾋﾞｯﾄｼﾌﾄによる掛け算
足し算とビットシフトを使って整数値どうしの掛け算をする方法を紹介します。
Javaには、掛け算を行う演算子'*'があるので、新しく掛け算が行えるメソッドなどを作成する必要はありません。
ここでは、掛け算がコンピュータ内部でどのように行われているかを理解するために、コンピュータの基本的な演算だけを使って掛け算メソッドを作ってみます。
はじめに、足し算を使って整数の掛け算を行う処理について説明します。
整数の掛け算の式a × bは、aをb回足すと言い換えることができます。よって、for文でb回のループを作り、その中でaの値を足していくことで、a × bの結果を得ることが出来ます。
Multiplied0.java ← クリックしてダウンロードページに移動
001: public class Multiplied0 {
002: // 足し算による掛け算 a×b
003: static int multiplied( int a, int b )
004: {
005: // 変数の宣言
006: int ans;
007:
008: // aとbのどちらかが0なら0を戻す
009: if ( ( 0 == a ) || ( 0 == b ) ) return 0;
010:
011: // 結果ansの初期値に0を代入
012: ans = 0;
013:
014: // b回のループを作成
015: for ( int i = 0; i < b; ++ i )
016: ans += a;
017:
018: // 結果を戻す
019: return ans;
020: }
021:
022:
023: // メイン
024: public static void main( String[] args ) {
025: // 変数の宣言
026: int a, b, ans;
027:
028: // 29×25=725
029: a = 29;
030: b = 25;
031: ans = multiplied( a, b );
032: System.out.println( a + "×" + b + "＝" + ans );
033:
034: // 33×109=3597
035: a = 33;
036: b = 109;
037: ans = multiplied( a, b );
038: System.out.println( a + "×" + b + "＝" + ans );
039:
040: // 10001×8828=88288828
041: a = 10001;
042: b = 8828;
043: ans = multiplied( a, b );
044: System.out.println( a + "×" + b + "＝" + ans );
045: }
046: }
Multiplied0.Javaの出力結果
29×25＝725 33×109＝3597 10001×8828＝88288828
ここから、ソースコードの主要部分について解説します。
002: // 足し算による掛け算 a×b
003: static int multiplied( int a, int b )
004: {
005: // 変数の宣言
006: int ans;
007:
008: // aとbのどちらかが0なら0を戻す
009: if ( ( 0 == a ) || ( 0 == b ) ) return 0;
010:
011: // 結果ansの初期値に0を代入
012: ans = 0;
013:
014: // b回のループを作成
015: for ( int i = 0; i < b; ++ i )
016: ans += a;
017:
018: // 結果を戻す
019: return ans;
020: }
for文でb回のループを作成し、そのループ中で変数ansに変数aの値を足しています。これで、変数ansには、aをb回分足した値が代入されます。
この処理の考え方は簡単ですが、bの値に大きさに比例して計算量が増えていきます。
次は、足し算とビットシフトを使って掛け算を行うJavaソースコードの例です。
下の図をみてください、小学校で習う掛け算の筆算で、２９×２５を計算しています。
掛け算の筆算
これは、２９×５＝１４５と２９×２０＝５８０の合計を計算することで７２５（１４５＋５８０）を導いています。
１０進数どうしの掛け算は、掛ける値（２５）の一の位（５）から十の位（２）から百の位（無し）…というように順番に位の値を掛けられる値（２９）に掛けていき、最後に合計値を計算する方法で掛け算の値を導きます。
コンピュータはビット(0 or 1)で情報を持っているので、内部では２進数で計算しています。そこで、上図の１０進数の筆算を２進数の筆算に書き換えてみます。（下図）
掛け算の筆算(２進数)
これは、１０進数の筆算と同様に掛ける値（１１００１）の一の位（１）からニの位（０）、四の位（０）、八の位（１）か、十六の位（１）を掛ける値（１１１０１）に最後に合計します。
２進数の掛ける値は、０または１です。１１００１の場合、一の位、八の位、十六の位に１があります。よって、１１１０１を１倍、８倍、１６倍した値を足したものが結果となります。
また、これをビットシフトで説明すると、１１１０１を左ビットシフト０回（１倍）、左ビットシフト３回（８倍）、左ビットシフト４回(１６倍)した値の合計となります。
MultipliedBitshift1.java ← クリックしてダウンロードページに移動
001: public class MultipliedBitshift1 {
002: // 左ビットシフトと足し算による掛け算 a×b
003: static int multiplied( int a, int b )
004: {
005: // 変数の宣言
006: int ans;
007: int checkbit;
008:
009: // aとbのどちらかが0なら0を戻す
010: if ( ( 0 == a ) || ( 0 == b ) ) return 0;
011:
012: // bのビットの有無を確認するための値
013: checkbit = 1;
014:
015: // 結果ansの初期値に0を代入
016: ans = 0;
017:
018: // 32回（32ビット）のループを作成
019: for ( int i = 0; i < 32; ++ i ) {
020: // checbitの位置のビットが1たっだら
021: // ansにaを足す
022: if ( 0 != ( b & checkbit ) )
023: ans += a;
024:
025: // aを左シフト(×2)
026: a = a << 1;
027:
028: // checkbitを左シフト(×2)
029: checkbit = checkbit << 1;
030: }
031:
032: // 結果を戻す
033: return ans;
034: }
035:
036:
037: // メイン
038: public static void main( String[] args ) {
039: // 変数の宣言
040: int a, b, ans;
041:
042: // 29×25=725
043: a = 29;
044: b = 25;
045: ans = multiplied( a, b );
046: System.out.println( a + "×" + b + "＝" + ans );
047:
048: // 33×109=3597
049: a = 33;
050: b = 109;
051: ans = multiplied( a, b );
052: System.out.println( a + "×" + b + "＝" + ans );
053:
054: // 10001×8828=88288828
055: a = 10001;
056: b = 8828;
057: ans = multiplied( a, b );
058: System.out.println( a + "×" + b + "＝" + ans );
059: }
060: }
MultipliedBitshift1.Javaの出力結果
29×25＝725 33×109＝3597 10001×8828＝88288828
ここから、ソースコードの主要部分について解説します。
002: // 左ビットシフトと足し算による掛け算 a×b
003: static int multiplied( int a, int b )
004: {
005: // 変数の宣言
006: int ans;
007: int checkbit;
008:
009: // aとbのどちらかが0なら0を戻す
010: if ( ( 0 == a ) || ( 0 == b ) ) return 0;
011:
012: // bのビットの有無を確認するための値
013: checkbit = 1;
014:
015: // 結果ansの初期値に0を代入
016: ans = 0;
017:
018: // 32回（32ビット）のループを作成
019: for ( int i = 0; i < 32; ++ i ) {
020: // checbitの位置のビットが1たっだら
021: // ansにaを足す
022: if ( 0 != ( b & checkbit ) )
023: ans += a;
024:
025: // aを左シフト(×2)
026: a = a << 1;
027:
028: // checkbitを左シフト(×2)
029: checkbit = checkbit << 1;
030: }
031:
032: // 結果を戻す
033: return ans;
034: }
for文でint型のビット数の32回のループを作成しています。
変数checkbitは、変数bの各位のビットが１かどうかを判定するに使うもので、１から開始してfor文の中で２倍（checkbit = checkbit << 1）にしています。
ビットのAND演算( 0 != ( b & checkbit ) )で、各位のビットが１であると判定されたときに合計を格納する変数ansにaを足していきます。
掛けられる値aもループの中で２倍（a = a << 1）していきます。
■関連コンテンツ
| ビットシフト | ビットのずらしかた |
| 時間計測 | 時間を計測する方法を解説 |
| 計算結果の表示 | 四則演算（足し算／引き算／掛け算／割り算）について |
| for文 | 繰り返し処理に使用するfor文について解説 |
■新着情報
| 2022.07.07 | 外部プログラムの実行 | exeファイル実行 |
| 2022.07.06 | 完全数 | ６＝１＋２＋３ |
