ビット演算による加算減算

+,-,*,/,四則演算記号を使用しない場合は,基本ビット演算により加減乗除四則演算を実現する.
1.C++でのビット演算による加算
まず,xとyを&ビット演算することにより,各ビットのキャリーを導いた.そしてxとyに対して^ビット演算を行い,加算ビットのない和を得た.最後に、得られた和を新しいxとし、得られた進位を左に1位(ゼロ位の進位入力は0)シフトして新しいyとし、進位が0になるまで上記の手順を続け、このときxに保存されるのが私たちが要求したxとyの和である.実装コードは次のとおりです.

int add(int a, int b)
{
　　int sum = a;
　　int carry = b;

　　while(carry)
　　{
　　　　int tmps = sum;

　　　　sum = tmps ^ carry;
　　　　carry = (tmps & carry) << 1;
　　}

　　return sum;
}

2.C++でのビット演算による減算
1つの数の反対の数を得るには,この数に対して2−補符号を求めればよい,すなわち逆加算1操作をとる.そして得られた結果に対してこの操作を続けると元の数字が得られる.2−補符号形式の符号化を用いることで,減算演算をスムーズに加算に変換できる.減数に対して2−補符号を求め、被減数に加算すれば差が得られる.以上の研究により,コードに減算を実現することは明らかであり,簡単である.第1ステップは減数を逆にして1を加算し、第2ステップは第1ステップで得られた値と被減数を加算する.具体的なコードは以下の通りです.

int subtract(int a, int b)
{
　　int subtrahend = add(~b, 1);

　　int sub = add(a, subtrahend);

　　return sub;
}

3.C++でのビット演算による乗算
乗算の最も簡単な理解は,被乗数を数回加算することで積を得ることである.負の整数の乗算を考慮して,ここではまず乗数と被乗数に対して絶対値を求め,次に絶対値に対して上述した乗算操作を行う.積記号を決定するルールは、同号が正、異号が負です.この実装は比較的簡単で、コードは以下の通りです.

int multiply(int a, int b)
{
　　//            
　　int multiplier = a < 0 ?  add(~a , 1) : a;
　　int multiplicand = b < 0 ? add(~b, 1) : b;

　　//        
　　int product = 0;
　　int count = 0;

　　while(count < multiplier)
　　{
　　　　product = add(product, multiplicand);
　　　　count = add(count, 1);
　　}

　　//       
　　if((a ^ b) < 0)
　　{
　　　　product = add(~product, 1);
　　}

　　return product;
}

上記の第1の実装方式は簡単であるが,効率が低すぎる.乗数と被乗数が小さければまだしも、大きくなれば効率は耐えられない.ここで実現するこの乗算は,最大log(n)回の加算操作をすれば,積を求めることができる.この方式と第1の方式の同じ点は,ここでも2数の絶対値を先に積し,最後に記号を決定することである.この実装方式は,乗数を手動で計算するシミュレーションである.具体的な手順は以下の通りである:1)乗数が1であるか0であるかによって、加算数が乗数によってシフトされた値をとるか0を決定する.2)各相加算数は乗数の最下位から値を求め,加算数(被乗数)を逐次1ビット左にシフトし,最後のステップ加算3)符号ビットは同号が正異号で負の原則に従う.

int multiply(int a, int b)
{
　　//            
　　int multiplier = a < 0 ?  add(~a , 1) : a;
　　int multiplicand = b < 0 ? add(~b, 1) : b;

　　//        
　　int product = 0;
　　while(multiplier)
　　{
　　　　if(multiplier & 0x1)
　　　　{
　　　　　　product = add(product, multiplicand);
　　　　}

　　　　multiplicand = multiplicand << 1;
　　　　multiplier = multiplier >> 1;
　　}

　　//       
　　if((a ^ b) < 0)
　　{
　　　　product = add(~product, 1);
　　}

　　return product;
}

4.C++におけるビット演算による除算
最も簡単な除算の実現は、除数で被除数を減らすことであり、被除数が除数より小さいときまで、このときに減らす回数は私たちが必要とする商であり、このときの被除数は余数である.唯一注意しなければならないのは商の記号と余数の記号です.商の記号の確定方式も乗算が同じで、すなわち同号が正で、異号が負である.残りの記号は除数された記号と同じです.簡単な乗算実装と同様に,ここではまず2数の絶対値を求め,残数を求める.最後に記号を確定します.実装コードは次のとおりです.

//  
int divide(int a, int b)
{
　　//           
　　int dividend = a < 0 ? add(~a, 1) : a;
　　int divisor = b < 0 ? add(~b, 1) : b;

　　//             
　　int remainder = dividend;
　　int quotient = 0;

　　while(remainder >= divisor)
　　{
　　　　remainder = subtract(remainder, divisor);
　　　　quotient = add(quotient, 1);
　　}

　　//     
　　if((a ^ b) < 0)
　　{
　　　　quotient = add(~quotient, 1);
　　}

　　return quotient;
}

//  
int remainder(int a, int b)
{
　　//           
　　int dividend = a < 0 ? add(~a, 1) : a;
　　int divisor = b < 0 ? add(~b, 1) : b;

　　//             
　　int remainder = dividend;
　　int quotient = 0;

　　while(remainder >= divisor)
　　{
　　　　remainder = subtract(remainder, divisor);
　　　　quotient = add(quotient, 1);
　　}

　　//     
　　if(a < 0)
　　{
　　　　remainder = add(~remainder, 1);
　　}

　　return remainder;
}