xxx 除法\模运算是怎么实现的

在阅读《数据结构预算法分析.Java语言描述》中看到除非运算在计算机中实现为

n%10=n-[n/10]*10

a%b=a-[a/b]*b

除数为2的幂

  • 除数2,二进制为0000 0010,被除数5,二进制为0000 0101。除数-1,即此时除数变为0000 0001,两者进行与操作,结果为0000 0001,余数为1。两者进行或操作,得0000 0111,右移除数的位数,此时为一位,得到商0000 0010,也就是2。

  • 除数4,二进制为0000 0100,被除数13,二进制为0000 1101。除数-1,即此时除数变为0000 0011,两者进行与操作,结果为0000 0001,余数为1。两者进行或操作,得0000 1111,右移除数的位数,此时为两位,得到商0000 0011,也就是3。

  • 除数8,二进制为0000 1000,被除数47,二进制为0010 1111。除数-1,即此时除数变为0000 0111,两者进行与操作,结果为0000 0111,余数为7。两者进行或操作,得0010 1111,右移除数的位数,此时为三位,得到商0000 0101,也就是5。

  • 二进制除法 原理

举例 2381/7

2381 二进制,1001 0100 1101
7 二进制,0111

  1001 (0100 1101)  //2381
- 0111
--------------------
  0010 (0100 1101)  // 此时0010>0,所以商的最高位为1
 -0011  1           // 这一次不够减,所以商的次高位为0,除数继续右移

  0010 01(00 1101)  
 -0001 11           
 -------------------
  0000 10(00 1101)  // 此时0000 10>0,所以商的第3高位为1
 -0000 11 1)        // 此时100减111<0,不够减,所以商的第4高位为0
 
  0000 1000 (1101)
 -0000 0111
 -----------------
  0000 0001 (1101)
 -0000 0001  11
 ----------------- 
  0000 0000  0001

  0010 1001  00
       128 32  4
       164

程序语言中的取余是如何实现的?


为什么很多开源软件中的源码中,使用位运算代替取模操作,比如:a%b取模的形式都被替换成了a&(b-1) ,前提条件是:b为2的幂(乘方)。

原因:位运算实现取模只需5个CPU周期,而取模运算符实现至少需要26个CPU周期(注意,是最少!!!)

为啥要用位运算代替取模呢 为啥要用位运算代替取模呢