使用位运算&取余 |
您所在的位置：网站首页 › 二进制除法取余数计算器怎么算的 › 使用位运算&取余 |
|
取余运算符为“%”。但在以前，CPU采用如下方法计算余数（注意，该方法只对2的N次方数系有效）： X & (2^N - 1) 举个例子： 9 % 4 //因为4是2^2；所以可以使用位运算X & (2^N - 1)代替取余 = 9 & ( 4 - 1 ) = 9 & 3 = 1001 & 0011 = 0001 = 1原理： 二进制数乘以2^n，相当于左移n位； 二进制数除以2^n，相当于右移n位； 任何二进制数和1的&操作，还是原来的二进制数 举个例子： 9 转换为二进制为 1001 1001 = 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0 那么： 1001 * 2^1 = (1*2^3 + 0*2^2 + 0*2^1 + 1*2^0）* 2^1 = 2*2^3 + 0*2^2 + 0*2^1 + 2*2^0 = 2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 10010 可知 1001*2，相当于将1001左移一位变成10010 1001 / 2^1 = (1*2^3 + 0*2^2 + 0*2^1 + 1*2^0）/ 2^1 = 1*2^2 + 0*2^1 + 0*2^0 = 100 可知 1001 / 2，相当于将1001右移一位变成100，而且可以知道右移出去的1就是1001 / 2的余数 任意一个数转换成二进制，我们可以分别将它二进制的每一位（1或者0）去乘以 2^n (这里的n从右边开始数依次为 0、1、2 ......) 我们用x表示一个普通的 n 位二进制数的每一位（这个 x 不需要去纠结，它可以是1也可以是0，只是这么表示，对结果没有什么影响），如下： xx...xx = x*2^(n-1) + x*2^(n-2) +...+ x*2^1 + x*2^0 这个数处以一个2^m次方 xx...xx / 2^m = ( x*2^(n-1) + x*2^(n-2) +...+ x*2^1 + x*2^0 ) / 2^m = x*2^(n-1-m) + x*2^(n-1-m) +... + x*2^(m-m) + x*2^(m-1-m) + ... + x*2^(0-m) x*2^(m-m) = x*2^0 ，这就是所得二进制数的最低位，而其后面的那些项x*2^(m-1-m) + ... + x*2^(0-m) 就是余数 这里相当于把 xx...xx 右移了 m 位，而移出去的那 m 位，就是余数（因为前面的都可以整除，后面的是不可以整除的，就是余数） 我们知道： 二进制的 2^m -1，总共有m+1位， 除了最高位 m+1 位为0，其余 m 位都为1 任何二进制数和1的&操作，原数都不变 那么： xx...xx & (2^m -1) 相当于取出了xx...xx 的低 m 位二进制数，也就是上面所说的右移出去的那m位数，也就是余数 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |