2018.07.12
足し算とビットシフトによる掛け算
掛け算の方法
Javaソースコード - 原始的な方法
Multiplied0.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046
public class Multiplied0 { // 足し算による掛け算 a×b static int multiplied( int a, int b ) { // 変数の宣言 int ans; // aとbのどちらかが0なら0を戻す if ( ( 0 == a ) || ( 0 == b ) ) return 0; // 結果ansの初期値に0を代入 ans = 0; // b回のループを作成 for ( int i = 0; i < b; ++ i ) ans += a; // 結果を戻す return ans; } // メイン public static void main( String[] args ) { // 変数の宣言 int a, b, ans; // 29×25=725 a = 29; b = 25; ans = multiplied( a, b ); System.out.println( a + "×" + b + "＝" + ans ); // 33×109=3597 a = 33; b = 109; ans = multiplied( a, b ); System.out.println( a + "×" + b + "＝" + ans ); // 10001×8828=88288828 a = 10001; b = 8828; ans = multiplied( a, b ); System.out.println( a + "×" + b + "＝" + ans ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis Multiplied0.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac Multiplied0.java
実行
C:\talavax\javasample>java Multiplied0
実行結果
29×25＝725 33×109＝3597 10001×8828＝88288828
ここから、ソースコードの主要部分について解説します。
002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020
// 足し算による掛け算 a×b static int multiplied( int a, int b ) { // 変数の宣言 int ans; // aとbのどちらかが0なら0を戻す if ( ( 0 == a ) || ( 0 == b ) ) return 0; // 結果ansの初期値に0を代入 ans = 0; // b回のループを作成 for ( int i = 0; i < b; ++ i ) ans += a; // 結果を戻す return ans; }
この処理の考え方は簡単ですが、bの値に大きさに比例して計算量が増えていきます。
Javaソースコード - 足し算とビットシフトを使う方法
下の図をみてください、小学校で習う掛け算の筆算で、２９×２５を計算しています。
これは、２９×５＝１４５と２９×２０＝５８０の合計を計算することで７２５（１４５＋５８０）を導いています。
１０進数どうしの掛け算は、掛ける値（２５）の一の位（５）から十の位（２）から百の位（無し）…というように順番に位の値を掛けられる値（２９）に掛けていき、最後に合計値を計算する方法で掛け算の値を導きます。
２進数の掛ける値は、０または１です。１１００１の場合、一の位、八の位、十六の位に１があります。よって、１１１０１を１倍、８倍、１６倍した値を足したものが結果となります。
MultipliedBitshift1.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060
public class MultipliedBitshift1 { // 左ビットシフトと足し算による掛け算 a×b static int multiplied( int a, int b ) { // 変数の宣言 int ans; int checkbit; // aとbのどちらかが0なら0を戻す if ( ( 0 == a ) || ( 0 == b ) ) return 0; // bのビットの有無を確認するための値 checkbit = 1; // 結果ansの初期値に0を代入 ans = 0; // 32回（32ビット）のループを作成 for ( int i = 0; i < 32; ++ i ) { // checbitの位置のビットが1たっだら // ansにaを足す if ( 0 != ( b & checkbit ) ) ans += a; // aを左シフト(×2) a = a << 1; // checkbitを左シフト(×2) checkbit = checkbit << 1; } // 結果を戻す return ans; } // メイン public static void main( String[] args ) { // 変数の宣言 int a, b, ans; // 29×25=725 a = 29; b = 25; ans = multiplied( a, b ); System.out.println( a + "×" + b + "＝" + ans ); // 33×109=3597 a = 33; b = 109; ans = multiplied( a, b ); System.out.println( a + "×" + b + "＝" + ans ); // 10001×8828=88288828 a = 10001; b = 8828; ans = multiplied( a, b ); System.out.println( a + "×" + b + "＝" + ans ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis MultipliedBitshift1.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac MultipliedBitshift1.java
実行
C:\talavax\javasample>java MultipliedBitshift1
実行結果
29×25＝725 33×109＝3597 10001×8828＝88288828
ここから、ソースコードの主要部分について解説します。
002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034
// 左ビットシフトと足し算による掛け算 a×b static int multiplied( int a, int b ) { // 変数の宣言 int ans; int checkbit; // aとbのどちらかが0なら0を戻す if ( ( 0 == a ) || ( 0 == b ) ) return 0; // bのビットの有無を確認するための値 checkbit = 1; // 結果ansの初期値に0を代入 ans = 0; // 32回（32ビット）のループを作成 for ( int i = 0; i < 32; ++ i ) { // checbitの位置のビットが1たっだら // ansにaを足す if ( 0 != ( b & checkbit ) ) ans += a; // aを左シフト(×2) a = a << 1; // checkbitを左シフト(×2) checkbit = checkbit << 1; } // 結果を戻す return ans; }
掛けられる値aもループの中で２倍（a = a << 1）していきます。
以上です。
関連コンテンツ
数値を２進数で表したときの各桁の「０」と「１」に対して演算を行えます。４種類の演算、AND(論理積)、OR(論理和)、XOR(排他的論理和)、NOT(否定)を詳しく説明しています。
2016.03.26
広告
