ゆるゆるプログラミング

・足し算とビットシフトによる掛け算

足し算とビットシフトを使って整数値どうしの掛け算をする方法を紹介します。

Javaには、掛け算を行う演算子'*'があるので、新しく掛け算が行えるメソッドなどを作成する必要はありません。

ここでは、掛け算がコンピュータ内部でどのように行われているかを理解するために、コンピュータの基本的な演算だけを使って掛け算メソッドを作ってみます。

はじめに、足し算を使って整数の掛け算を行う処理について説明します。

整数の掛け算の式a × bは、aをb回足すと言い換えることができます。よって、for文b回のループを作り、その中でaの値を足していくことで、a × bの結果を得ることが出来ます。

以下が、そのJavaソースコードの例です。

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には、ab回分足した値が代入されます。

この処理の考え方は簡単ですが、bの値に大きさに比例して計算量が増えていきます。

次は、足し算とビットシフトを使って掛け算を行うJavaソースコードの例です。

下の図をみてください、小学校で習う掛け算の筆算で、29×25を計算しています。

掛け算の筆算掛け算の筆算

これは、29×5=14529×20=580合計を計算することで725(145+580)を導いています。

10進数どうしの掛け算は、掛ける値(25)の一の位(5)から十の位(2)から百の位(無し)…というように順番に位の値を掛けられる値(29)に掛けていき、最後に合計値を計算する方法で掛け算の値を導きます。

コンピュータはビット(0 or 1)で情報を持っているので、内部では2進数で計算しています。そこで、上図の10進数の筆算を2進数の筆算に書き換えてみます。(下図)

掛け算の筆算(2進数)掛け算の筆算(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倍)した値の合計となります。

以下が、そのJavaソースコードの例です。

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文について解説

■新着情報

2019.09.13 長さの単位変換 1マイル、1フィートは何m?
2019.09.06 クイックソート 高速に配列に並び替える方法
2019.09.05 中央値(メディアン) 配列に格納されている値の中央値を求める
2019.09.05 最頻値 配列から出現回数が最も多い値の取得
2019.09.03 配列値の反転 配列の反転処理
2019.08.05 トランプの操作 トランプを操作するクラス

 

 

 

 

 

 

 

 

 

Topへ