余剰操作の原理

以前習ったことがありますが、秦に帰る列車の中でこのような問題を見たことを忘れて、考えてみました.
Cは高级な言语で、a-(aはbを取り除きます)*bは言うまでもなくて、“整除”はどのように来ましたか?しかし、バイナリ演算に比べて、アセンブリも「高度な」言語ですが、「div」はどうやって来たのでしょうか.一例を見て、除数の数が2のべき乗であれば:

除数2、バイナリ0000 0010、被除数5、バイナリ0000 0101.除数-1、すなわちこのとき除数が0000 0001となり、両者は操作を行い、結果は0000 0001、残数は1となる.

除数4、バイナリ0000 0100、被除数13、バイナリ0000 1101.除数-1、すなわちこのとき除数が0000 0011となり、両者は操作を行い、結果は0000 0001、残数は1となる.

除数8、バイナリ0000 1000、被除数47、バイナリ0010 1111.除数-1、すなわちこのとき除数が0000 0111となり、両者は操作を行い、結果は0000 0111、残数は7となる.

原理は分かったでしょうが、この方法は2のべき乗数を除いた場合にのみ適用されます.また,この方法はビットマップ法のビットベクトル操作において,見ているのは操作であり,実際には余剰をとる.

#define MAX 1000000  
#define SHIFT 5  
#define MASK 0x1F  
#define DIGITS 32  
  
int a[1+MAX/DIGITS];
//     1
void setbit(int n) 
{ 
 a[n>>SHIFT] |= (1<<(n&MASK)); 
}
//                                                   
void clearbit(int n)  
{  
 a[n>>SHIFT] &= ~(1<<(n&MASK));  
}
//           1    
int test(int n)  
{  
    return a[n>>SHIFT] & (1<<(n&MASK)); 
} 

再び本題に戻る.余剰は回路によるバイナリ除算により実現する、簡単な原理図(具体的には複雑)数電の教科書にあったのを覚えていますが、後日調べてみました.では、バイナリ除法はどうなっていますか.実はネット上で原理を探しています.(TATは高速鉄道で自分で作ったと思っていました)(我々は直接減算で実現できるが、これなら10324を3で割ると非常に複数回循環する.)この場合、私の考えは、1、除数を左に移動して、被除数の最上位に位置合わせまたは小一位になる.(小一位は被除数から左に移動した除数を減算しなければならないので、このとき除数肯定>(除数*ある2のn回))2,除数から左シフト後の除数を減算されます.3,除数が左シフトします.このとき,除数肯定>(除数*ある2のn 1回).....被除数<除数、このときの被除数が剰余となるまで反復し続けます.まず商を考えずに、2381を7で割ると仮定して2つの数を勝手に探します.2381、バイナリ1001 0100 11017、バイナリ111は2381の最上位1001で111を減算して10を得ます.2381-7*256=589に相当します(これは急速に縮小されているので、実際には除数や被除数が非常に大きいか、機械の桁数を超えている場合を除き、操作ごとに何度も読み返すと性能が損なわれるに違いない)589=さっきの答え10+以前に使ったことがない右01001101=1001001001101は再びさっきの行程589の最上位1001から111を繰り返し、10を得る.589-7*64=14141=さっきの答え10+に相当する前に使ったことのない右の001101=10001101...このようにループして、最後に、被除数が1残った場合に残数となる.では、商はどこへ行ったのでしょうか.バイナリ除算の原理を見てください.原理は私と同じですが、シフトを制御し続けなければなりません.さっきの例では、2381を7以下で割るのは計算の過程です.{}の中には計算の答えがあります.()の中には計算に参加していないビットがあります.

   1001 (0100 1101)             //2381
  -0111                        //7
--------------------------
  {0010}(0100 1101)          //  0010>0，        1
  -0011  1                  //      ，        0
      
   0010 01(00 1101)
  -0001 11
----------------------------
  {0000 10}(00 1101)   //  000010>0，     3   1
  -0000 11  1         //  100 111<0，   ，     4   0

除数は右に移動し続けます....このようにループして、最後の答えは101010100で、一番前の1010は前の4回の計算の値です.面倒ですが、回路で実現するのは速いです.