虽然以前学过，但是已经忘了，在返秦的火车上看到如此问题，于是思考了一下。
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];//置指定位为1void 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的n1次）。。。。不停迭代，直至被除数<除数，这个时候被除数就是余数。我们先来看不考虑商，仅仅考虑取余我们随便找两个数，假设是2381除以7。2381，二进制为1001 0100 11017，二进制为111用2381的最高位1001减去111，得10。相当于2381-7*256 = 589 （这个缩小得很快的，所以其实除非除数和被除数非常大，或者超出机器位数，每次操作要多读几遍，肯定会有性能损失）589 = 刚才的答案10+之前没用过的右边01001101 = 1001001101再次重复刚才的过程589的最高位1001减去111，得10。相当于589-7*64 = 141141 = 刚才的答案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