二进制按位与&及求余数

按位与&

移位

运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;

在移位运算中我们可知,计算机中的数据都是0和1的序列,当我们把某个数字左移一位,该数字会扩大为原来的2倍;而将其右移一位时,该数字就会缩小为原来的1/2,即相当于对该数字做了一次被2整除的运算。

举例说明:

11的二进制是1011,如果右移一位的话,将变成0101,也就是5。

现在我们考虑11除以8的余数,很显然是3;因为8是2的3次幂,求余时相当于除以2的3次幂,也就是把1011右移3位,该过程会把1011的低3位011给移走,事实上,这个被移走的011就是11除以8的余数!

取余

但是,我们该如何把这个011给保存下来呢?

现在的问题就转化为如何保存11的二进制1011的低三位数字了——这时就是按位与运算出马的时候了!

和1做与运算会保存原来的数字,所以我们就可以用1011&0111来计算。

那么这个0111又是如何得到的呢?

有两种方法,第一种是2^N-1,比如8按照此公式就得出了0111;第二种是8的二进制取反,即1000取反得到0111。

综上所述,位运算求余一定要注意,只适合于除数是2的N次方的情况。其原理就是:对2的N次方求余,就预示着数字将向右移N位;这被右移的N位,就是余数!只要我们再用与运算将这N位保存下来即可!

应用

设X对Y求余,Y等于2^N,公式为:X & (2^N - 1)或X&(~Y)。

例如:14%8,取余数,相当于取出低位,而余数最大为7,14二进制为1110,8的二进制1000,8-1 = 7的二进制为0111,由于现在低位全为1,让其跟14做&运算,正好取出的是其低位上的余数。

1110&0111=110即6=14%8;(此公式只适用b=2n,是因为可以保证b始终只有最高位为1,其他二进制位全部为0,减去1,之后,可以把高位1消除,其他位都为1,而与1做&运算,会保留原来的数。)

因此,按位与&操作是指对两操作数进行按位与运算,其中两位都为1结果为1,其他情况为0。按位与是二目运算符。

实际上相当于h%length取余数,但&计算速度更快。

由于我们知道位运算比较高效,在某些情况下,当b为2的n次方时,有如下替换公式:
a % b = a & (b-1)(b=2n)
即:a % 2n = a & (2n-1)

------ 本文结束------

本文标题:二进制按位与&及求余数

文章作者:Perkins

发布时间:2019年11月18日

原始链接:https://perkins4j2.github.io/posts/19120/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。