取余与取模以及二进制移位技巧

[caipengbo]

对于整数a，b来说，取模运算或者求余运算的方法要分如下两步：

1. 求整数商：c=a/b
2. 计算模或者余数：r=a-(c*b)

求模运算和求余运算在第一步不同 ，取余运算在计算商值向0方向舍弃小数位 ，取模运算在计算商值向负无穷方向舍弃小数位（整数时，是一样的） 例如：4/(-3)约等于-1.3 在取余运算时候商值向0方向舍弃小数位为-1 在取模运算时商值向负无穷方向舍弃小数位为-2 所以 4 rem(-3)=1 4 mod(-3)=-2

[caipengbo]

数左移一位就是乘以2，右移一位就是除以2，传说用位运算效率提高了60%。

乘2^k： n<<k。

敲2566*4的结果: 直接2566<<4就搞定了，又快又准确。

除2^k： n>>k。

那么 mod 2^k 呢？（对2的倍数取模） n&((1<<k)-1) 用通俗的言语来描述就是,对2的倍数取模，只要将数与2的倍数-1做按位与运算即可。