ビット演算による加減乗除四則演算(Java)

本文は『一文理解面白いビット演算』に続く第二の文章である.
コンピュータの最も基本的な操作ユニットはバイト(byte)であり、1バイトは8ビット(bit)で構成され、1ビットは1つの0または1しか記憶できないが、実際には高低レベルであることが知られている.どんなに複雑な論理、膨大なデータ、クールなインタフェースであっても、最終的にはコンピュータの最下層に現れているのは0101の記憶と演算にすぎない.従って,ビット演算を理解することは,計算機の下位操作原理の理解を向上させるのに役立つ.
一、加算
2つのバイナリ数が異なるか演算の結果は、キャリーを考慮しない場合の結果であり、
2つのバイナリ数と演算の結果に1を含むビットは、キャリーがあるビットである.0101 + 0001 = 0110を例に以下のように分析した.

//   0101 + 0001
0101 ^ 0001 = 0100 //      ，       ，     0100
0101 & 0001 = 0001 //       ，          1
0001 << 1 = 0010   //         ，        

//     0100 + 0010，  +      0

JAvaコード:
再帰

public static int add(int a, int b) {
   if (b == 0) {
       return a;
   } else {
       return add(a ^ b, (a & b) << 1);
   }
}

ループ

public static int add2(int a, int b) {
    int sum = a;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

二、減算
加算の考え方と一致しているが,1つの数を減算することは1つの数を加算する逆の数に等しいにすぎない.
例:5-1=5+(-1).だから、減数された逆の数を求めるだけです.
どのようにして1つの数の反対の数を求めますか?
コンピュータに格納されているのはバイナリの補符号形式で、正数の補符号は原符号と同じで、負数の補符号はこの数の原符号に対して記号ビットを除いた各位を逆にして、それから最後のビットに1を加えます.
例:
1コンピュータにおけるバイナリ表現:0000 0001
-1コンピュータにおけるバイナリ表現:1111 1111
計算プロセスは次のとおりです.
-1のコード:1000,0001
-1の逆符号化:1111 1110
-1の符号化:1111 1111
ここで、1の原符号(0000,0001)から逆得−1の逆符号をとる(1111,1110)
まとめて、1つの数の反対数の求め方は、その数が1桁ごとに逆を取り、末位に1を加えることです.
JAvaコード:

public static int minus(int a, int b) {
    return add(a, add(~b, 1));
}

三、乗算
考えがなければ、まず紙にバイナリ乗算の過程を書くことができます.

        0101    a
    ×   0110    b
    ----------------
        0000    
       0101   
      0101      
   + 0000       
    ----------------
     00011110

2進法を計算する過程を整理します.
初期化積結果は0で、数字bの末位0→1→1→0を順次遍歴し、末位が0の場合、積結果に0を加える、すなわち積は変わらず、Aは左に1ビットシフトする.最下位が1の場合,積結果にAを加え,Aをさらに左にシフトする.
どのように数字bの末位を遍歴しますか?
前述したように、演算を使用して1つの数の末尾を取り、数字b=0になるまで数字bを右に移動し続け、変位を終了することができます.
正負の数の記号の問題に注意してください.ここでは、a、bの2つの数の絶対値に対してその積を計算し、最後にその記号を決定します.
JAvaコードは次のとおりです.

public static int multiply(int a, int b) {
      //            
      int A = a < 0 ? add(~a, 1) : a;
      int B = b < 0 ? add(~b, 1) : b;
      //        
      int P = 0;
      while (B != 0) {
          if ((B & 1) != 0) { //            ，0 or 1
              P = add(P, A);
          }
          A = A << 1;
          B = B >> 1;
      }
      //       
      if ((a ^ b) < 0) {
          P = add(~P, 1);
      }
      return P;
}

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

public static int[] divide(int a, int b) {
      //           
      int A = a < 0 ? add(~a, 1) : a;
      int B = b < 0 ? add(~b, 1) : b;
      //             
      int C = A; //   C
      int N = 0; //  N
      while (C >= B) {
          C = minus(C, B); // C-B
          N = add(N, 1); // N+1
      }
      //      
      if ((a ^ b) < 0) {
          N = add(~N, 1);
      }
      //       
      if (a < 0) {
          C = add(~C, 1);
      }
      return new int[]{N, C};
}

このアルゴリズムはAが大きく,Bが小さい場合に効率が低いことを指摘する必要があるが,どのようにアルゴリズムを最適化してwhileサイクルの回数を減らすのか.
除算は乗算の過程から逆に押されたと考えられる.例えば9÷4=2…1、つまり2*4+1=9です.仮に9で4*2を減らすと、結果は1に等しく、1が4未満であるため、9÷4の商は2であり、残数は1であることが得られる.
4の倍数をどのように決定するかが最終結果に近づく鍵である.int整数型は32ビットあり,先頭を除いてシンボルビットを表し,各ビットの大きさは[2^0,2^1,2^2,,2^30]、最大int整数は2^31−1であることが分かった.したがって,被除数を2^31,2^30,...2^3,2^2,2^1,1の順に乗算することができ,除数がそれらの積より大きいと除数は減算され,減算された残数はサイクルが終わるまで除数として継続することができる.
JAvaコード:

public static int[] divide(int a, int b) {
    //            
    int A = a < 0 ? add(~a, 1) : a;
    int B = b < 0 ? add(~b, 1) : b;

    int N = 0; //   N
    for (int i = 31; i >= 0; i--) {
        //    A>=(B<> i) >= B) { // A ÷ 2^i >= B
            N += (1 << i); // N = N + 2^i
            A -= (B << i); // A = A - B*2^i
        }
    }

    int C = A; //   C
    //      
    if ((a ^ b) < 0) {
        N = add(~N, 1);
    }
    //       
    if (a < 0) {
        C = add(~C, 1);
    }
    return new int[]{N, C};
}