使用位运算替代模运算

落日映苍穹つ 2022-04-06 12:18 197阅读 0赞

昨天的分析HashMap原理的文章里面提到，使用位运算替代取模运算效率高，但位运算只能在特定场景下才能替代%运算。  
  
  
正常情况下：

````
    a % b = a - (a / b)*b 
    
    ````

但如果b的值为2的n次方的时候（n为自然数），这时候就可以用位运算来替代模运算，  
转化如下：

````
    a % b = a & (b-1)
    ````

2的n次方的二进制如下：

````
    `
     0001 2^0  1  
     0010 2^1  2
     0100 2^2  4
     1000 2^3  8
    
    ````

从上面能看到左移一位是放大2倍，右移一位是缩小2倍  
  
  
分别减一后的二进制

````
    
    0000 2^0-1 0
    0001 2^1-1 1
    0011 2^2-1 3
    0111 2^3-1 7
    
    ````

举例  
  
我们算下11%8的模，  
  
11的二进制是：1011  
  
代入上面的公式：

````
    11 % 8 = 11 & （8-1） 
    ````

7的二进制： 0111  
  
  
二者做&(与)运算 ，回忆下运算规则：

````
    & 与。 全1为1， 有0为0。　　任何数与0与都等于0。　　
    | 或。 有1为1， 全0为0。　　任何数与0或都等于原值。
    ~ 非。 逐位取反
    ^ 异或。 相同为0，相异为1。 任何数与0异或都等于原值。
    ````

结果：  
  
1011 & 0111 = 0011  
  
转化成10进制后=3  
  
所以11%8=3  
  
  
这种方法只是适合于求一个数除以二的N次冥才正确，求模的过程，就是2^n-1的中1的个数就是n的值，再与a做&运算，得出来的低位就是我们期望的余数。  
\[b\]\[color=green\]\[size=large\] 有什么问题可以扫码关注微信公众号：我是攻城师(woshigcs)，在后台留言咨询。 技术债不能欠，健康债更不能欠， 求道之路，与君同行。 \[/size\]\[/color\]\[/b\] \[img\]http://dl2.iteye.com/upload/attachment/0104/9948/3214000f-5633-3c17-a3d7-83ebda9aebff.jpg\[/img\]

发表评论取消回复

表情：

评论列表（有 0 条评论，197人围观）

还没有评论，来说两句吧...

相关阅读

相关位运算

位运算位与&，相同位数都是1，结果才是1，按位&&的意思。 a&a=a，a&0=0 位|，相同位数有一个是1，结果就是1，按位||的意思。 a|a=a，a|0=

谁践踏了优雅/ 2022年12月19日 16:17/ 0 赞/ 259 阅读

相关模运算

本文介绍关于模运算的相关知识，并给出大数模运算的方法。一、模的理论和规律 1. 如果n整除A-B，那么就称A和B模n同余。如果A和B模n同余，那么A+C与B+C模n同

今天药忘吃喽~/ 2022年08月14日 01:43/ 0 赞/ 258 阅读

相关位运算

一．逻辑运算符 1.& 位与运算 1) 运算规则位与运算的实质是将参与运算的两个数据，按对应的二进制数逐位进行逻辑与运算。例如：int型常量4和

分手后的思念是犯贱/ 2022年08月04日 15:50/ 0 赞/ 228 阅读

相关位运算

由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。按位与（Bitwise AND），运算符号为& a&b 的操作的结果：a、b中对应位同时为1，则对

缺乏、安全感/ 2022年07月16日 12:46/ 0 赞/ 326 阅读

相关位运算

一．逻辑运算符 1.& 位与运算 1) 运算规则位与运算的实质是将参与运算的两个数据，按对应的二进制数逐位进行逻辑与运算。例如：int型常量4和7

左手的ㄟ右手/ 2022年07月13日 07:59/ 0 赞/ 224 阅读

相关位运算

基础知识位运算是把数字用二进制表示之后，对每一位上0或1的运算。位运算总共只有5种运算：与、或、异或、左移和右移。对于异或操作，需要注意一下`0^0=0; 1^1=0;

末蓝、/ 2022年07月03日 14:26/ 0 赞/ 323 阅读

相关位运算

位运算主要是直接操控 [二进制][Link 1] 时使用，主要目的是节约内存，使你的程序速度更快，还有就是对内存要求苛刻的地方使用，以下是一牛人总结的方法，分享一下：位运算应

骑猪看日落/ 2022年06月13日 09:55/ 0 赞/ 248 阅读

相关使用位运算替代模运算

昨天的分析HashMap原理的文章里面提到，使用位运算替代取模运算效率高，但位运算只能在特定场景下才能替代%运算。正常情况下： a % b = a - (a /

左手的ㄟ右手/ 2022年06月01日 13:42/ 0 赞/ 217 阅读

相关使用位运算替代模运算

昨天的分析HashMap原理的文章里面提到，使用位运算替代取模运算效率高，但位运算只能在特定场景下才能替代%运算。正常情况下： ````

落日映苍穹つ/ 2022年04月06日 12:18/ 0 赞/ 198 阅读

相关位运算(~ 、& 、^ 、|）

借鉴大佬博客：[http://blog.sina.com.cn/s/blog\_60e96a410100mjd2.html][http_blog.sina.com.cn_s_b

刺骨的言语ヽ痛彻心扉/ 2022年02月13日 11:43/ 0 赞/ 389 阅读