FreeCMS商业版

功能强大、开源、代码通俗易懂、注释详细、面向二次开发友好!

面向二次开发友好的java开源CMS!打造更好的中国开源jsp java CMS!

FreeCMS商业版V2.7已发布!购买请联系客服QQ 124812878 查看更新日志



在线演示 立即购买 下载免费版 下载商业版用户手册
客服QQ: 124812878 联系电话: 18339991503 Email: freeteam@foxmail.com

使用位运算替代模运算 - 有任何问题请关注公众号留言: 我是攻城师(woshigcs) - ITeye博客

加入收藏夹】     【打印】     【关闭】 来源: 日期:2018-02-03 22:00:01 点击量: 收藏



昨天的分析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做&运算,得出来的低位就是我们期望的余数。
有什么问题可以扫码关注微信公众号:我是攻城师(woshigcs),在后台留言咨询。 技术债不能欠,健康债更不能欠, 求道之路,与君同行。




上一条

下一条

相关新闻
自定义表单
本例固定链接: 分享到:
更多