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ソースコードの例です。
下の図をみてください、小学校で習う掛け算の筆算で、29×25を計算しています。
これは、29×5=145と29×20=580の合計を計算することで725(145+580)を導いています。
10進数どうしの掛け算は、掛ける値(25)の一の位(5)から十の位(2)から百の位(無し)…というように順番に位の値を掛けられる値(29)に掛けていき、最後に合計値を計算する方法で掛け算の値を導きます。
コンピュータはビット(0 or 1)で情報を持っているので、内部では2進数で計算しています。そこで、上図の10進数の筆算を2進数の筆算に書き換えてみます。(下図)
これは、10進数の筆算と同様に掛ける値(11001)の一の位(1)からニの位(0)、四の位(0)、八の位(1)か、十六の位(1)を掛ける値(11101)に最後に合計します。
2進数の掛ける値は、0または1です。11001の場合、一の位、八の位、十六の位に1があります。よって、11101を1倍、8倍、16倍した値を足したものが結果となります。
また、これをビットシフトで説明すると、11101を左ビットシフト0回(1倍)、左ビットシフト3回(8倍)、左ビットシフト4回(16倍)した値の合計となります。
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の各位のビットが1かどうかを判定するに使うもので、1から開始してfor文の中で2倍(checkbit = checkbit << 1)にしています。
ビットのAND演算( 0 != ( b & checkbit ) )で、各位のビットが1であると判定されたときに合計を格納する変数ansにaを足していきます。
掛けられる値aもループの中で2倍(a = a << 1)していきます。
■関連コンテンツ
ビットシフト | ビットのずらしかた |
時間計測 | 時間を計測する方法を解説 |
計算結果の表示 | 四則演算(足し算/引き算/掛け算/割り算)について |
for文 | 繰り返し処理に使用するfor文について解説 |
■新着情報
2022.07.07 | 外部プログラムの実行 | exeファイル実行 |
2022.07.06 | 完全数 | 6=1+2+3 |