求余不用模
刺猬@http://blog.csdn.net/littlehedgehog
我们先来看看这个问题如果要求 9除以4余数是多少？ 可能大部分人都会直接用 6%4 这样的C语言表达式吧？平时用也倒是无妨，但是在系统内核这种对速度要求极为严格的地方，这种除法运算的花销可能就有点不太值得了。
注意看下面的数学式子:
9%4=2 ——> 9&(4-1)=2 (%是取模的符号)
也即是 x%(2n)=x&(2n-1)
把上面的数字转化为二进制就好懂了:
(1001b)%(100b),取模也就是把9平均分，而平均每小份分得4，求最后一份剩下多少？
由二进制的运算特点可知，比如(1001b)%(100b),直接可以从除数位数开始在被除数中向高位截就是商，比如这里除数是3位，那么我们直接从3位开始截断被除数1001B，也就是取被除数的3、4位，即商10b，十进制为2，而余数的话就是直接以除数最高位-1 然后在被除数截断，比如这里除数是3位，那么就取2、1位，余数就是01b，有了这个理论，上面的式子就好理解了。余数的截断就是把 除数-1,然后再与被除数进行&运算，这样避免了除法指令，大大加快了运算速度。
不过这里有个注意的地方，就是我这里所指的除数有个特殊性，就是必须是2的次方，也就是必须转化为二进制是以1开头，后全为0的数！
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 houjiaqi1991 的文章《求余不用模》','https://www.xiaopingtou.net/article-52232.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}