使用位操作(&运算)代替求余操作 |
您所在的位置:网站首页 › c求余数符号 › 使用位操作(&运算)代替求余操作 |
%运算:a%b
由于我们知道位运算比较高效,在某些情况下,当b为2的n次方时,有如下替换公式: a % b = a & (b-1)(b=2n) 即:a % 2n = a & (2n-1) 例如: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做&运算,会保留原来的数。) 应用看hashMap(JDK7)源码时,发现有此应用: /** * 利用Key的hash值和数组的长度(length),找到key对应在table数组中的下标 * @param h key的hash值 * @param length HashMap中table数组的长度 * @return 下标 */ static int indexFor(int h, int length) { return h & (length-1);//实际上相当于h%length取余数,但&计算速度更快 }此处能应用这个公式,是因为HashMap源码中的数组长度使用roundUpToPowerOf2方法把map中底层数组的长度设置成2n,好像用来减少hash冲突的(是否是用来减少冲突不敢100%确定) private void inflateTable(int toSize) { //为了减少hash冲突,最好把数组设置成2的n次方,此方法用于找到大于toSize的“最小的2的n次方”。 int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } //把number的设置成2的n次方 private static int roundUpToPowerOf2(int number) { return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |