正文
使用 & 进行高效率取余运算
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Java的HashMap源码中用到的(n-1)&hash这样的运算,这是一种高效的求余数的方法
结论:假设被除数是x,对于除数是2n的取余操作x%2n,都可以写成x&(2n-1),位运算效率高!
举例:259%8=259&7=3
原理:因为对8的取余结果肯定小于8
在二级制中,8=(1000)2,因此取余结果肯定小于等于7=(0111)2
因此对于被除数的二进制来说,只需要保证后三位保留下来即可(后三位保留下来肯定小于8)
此时保存下来的结果就是取余结果
259 : 1 0 0 0 0 0 0 1 1
7 : 0 0 0 0 0 0 1 1 1
要保存后面的三个数,就需要使用到位运算:(&运算中1&1=1,1&0=0,0&0=0)
此时位运算结果:0 0 0 0 0 0 0 1 1
转换为10进制就等于3!
注意:只有对于除数是2n,才可以使用此方法进行取余运算
公式:x%2n == x&(2n-1)
使用 & 进行高效率取余运算的更多相关文章- 洛谷 P1226 【模板】快速幂||取余运算
题目链接 https://www.luogu.org/problemnew/show/P1226 题目描述 输入b,p,k的值,求b^p mod k的值.其中b,p,k*k为长整型数. 输入输出格式 ...
- 洛谷P1226 【模板】快速幂||取余运算
题目描述 输入b,p,k的值,求b^p mod k的值.其中b,p,k*k为长整型数. 输入输出格式 输入格式: 三个整数b,p,k. 输出格式: 输出“b^p mod k=s” s为运算结果 S1: ...
- php取余运算(%) 注意事项
<?php //php取余运算(%)的那点事,php取余数用%符号,即为模运算 //理论上应该输出45才对,可是实际运算结果是44 $val=9.45; $result=$val*100; ec ...
- LuoguP1226 【模板】快速幂||取余运算
题目链接:https://www.luogu.org/problemnew/show/P1226 第一次学快速幂,将别人对快速幂原理的解释简要概括一下: 计算a^b时,直接乘的话计算次数为b,而快速幂 ...
- 快速幂 cojs 1130. 取余运算
cojs 1130. 取余运算 ★ 输入文件:dmod.in 输出文件:dmod.out 简单对比时间限制:10 s 内存限制:128 MB [题目描述] 输入b,p,k的值,求b^p ...
- 洛谷——P1226 取余运算||快速幂
P1226 取余运算||快速幂 题目描述 输入b,p,k的值,求b^p mod k的值.其中b,p,k*k为长整型数. 输入输出格式 输入格式: 三个整数b,p,k. 输出格式: 输出“b^p mod ...
- 为什么Java的hash表的长度一直是2的指数次幂?为什么这个(hash&;(h-1)=hash%h)位运算公式等价于取余运算?
1.什么是hash表? 答:简单回答散列表,在hash结构散列(分散)存放的一种数据集结构. 2.如何散列排布,如何均匀排布? 答:取余运算 3.Java中如何实现? 答:hash&(h-1) ...
- python 取余运算
python中取余运算逻辑如下: 如果a 与d 是整数,d 非零,那么余数 r 满足这样的关系: a = qd + r , q 为整数,且0 ≤ |r| < |d|. 经过测试可发现,pytho ...
- codevs 1497取余运算
1497 取余运算 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamon 题目描述 Description 输入b,p,k的值,编程计算bp mod k的值. ...
随机推荐- 详解java定时任务
在我们编程过程中如果需要执行一些简单的定时任务,无须做复杂的控制,我们可以考虑使用JDK中的Timer定时任务来实现.下面LZ就其原理.实例以及Timer缺陷三个方面来解析JavaTimer定时器. ...
- Xdebug文档(五) 代码覆盖分析
代码覆盖分析能在请求时让你知道脚本哪一行(或哪一段)在执行. 相关设置 xdebug.coverage_enable 类型: boolean, 默认值: 1, 始于 Xdebug >= 2.2 ...
- 01HTTP服务&;AJAX编程
HTTP服务&AJAX编程 一.服务器 1. 什么是服务器? 能够提供某种服务的机器(计算机)称为服务器. 2.服务器的分类: 1.按系统分类:Lin ...
- MQTT V3.1--我的理解
最近因为工作需要,需要对推送消息了解,因此对MQTT进行了整理,这里更多的是对MQTT英文版的翻译和理解. MQTT(Message Queue Telemetry Transport),遥测传输协议 ...
- css写带边框的三角形
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
- CALayer 图层
// CALayer 图层属性,继承UIView都有该属性,可设置边框宽度.颜色.圆角.阴影等 UIImageView *imageView = [[UIImageView alloc]initWit ...
- Java事务处理全解析(三)——丑陋的案例
在本系列的上一篇文章中,我们看到了一个典型的事务处理失败的案例,其主要原因在于,service层和各个DAO所使用的Connection是不一样的,而JDBC中事务处理的作用对象正是Connectio ...
- jquery跳出当前的each循环
break----用return false; continue --用return ture; jquery是对象链,所以$(..).each()返回的还是对象集合.each(function(){ ...
- C++编写一个简单的DLL
什么是DLL: 自从微软推出16位的Windows操作系统起,此后每种版本的Windows操作系统都非常依赖于动态链接库(DLL)中的函数和数据,实际上 Windows操作系统中几乎所有的内容都由DL ...
- python脚本 随机定位坐标
import mathimport randomdef rad(dg): return (dg * math.pi / 180)def deg(rd): return (rd * 180 ...
题目链接 https://www.luogu.org/problemnew/show/P1226 题目描述 输入b,p,k的值,求b^p mod k的值.其中b,p,k*k为长整型数. 输入输出格式 ...
题目描述 输入b,p,k的值,求b^p mod k的值.其中b,p,k*k为长整型数. 输入输出格式 输入格式: 三个整数b,p,k. 输出格式: 输出“b^p mod k=s” s为运算结果 S1: ...
<?php //php取余运算(%)的那点事,php取余数用%符号,即为模运算 //理论上应该输出45才对,可是实际运算结果是44 $val=9.45; $result=$val*100; ec ...
题目链接:https://www.luogu.org/problemnew/show/P1226 第一次学快速幂,将别人对快速幂原理的解释简要概括一下: 计算a^b时,直接乘的话计算次数为b,而快速幂 ...
cojs 1130. 取余运算 ★ 输入文件:dmod.in 输出文件:dmod.out 简单对比时间限制:10 s 内存限制:128 MB [题目描述] 输入b,p,k的值,求b^p ...
P1226 取余运算||快速幂 题目描述 输入b,p,k的值,求b^p mod k的值.其中b,p,k*k为长整型数. 输入输出格式 输入格式: 三个整数b,p,k. 输出格式: 输出“b^p mod ...
1.什么是hash表? 答:简单回答散列表,在hash结构散列(分散)存放的一种数据集结构. 2.如何散列排布,如何均匀排布? 答:取余运算 3.Java中如何实现? 答:hash&(h-1) ...
python中取余运算逻辑如下: 如果a 与d 是整数,d 非零,那么余数 r 满足这样的关系: a = qd + r , q 为整数,且0 ≤ |r| < |d|. 经过测试可发现,pytho ...
1497 取余运算 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamon 题目描述 Description 输入b,p,k的值,编程计算bp mod k的值. ...
- 详解java定时任务
在我们编程过程中如果需要执行一些简单的定时任务,无须做复杂的控制,我们可以考虑使用JDK中的Timer定时任务来实现.下面LZ就其原理.实例以及Timer缺陷三个方面来解析JavaTimer定时器. ...
- Xdebug文档(五) 代码覆盖分析
代码覆盖分析能在请求时让你知道脚本哪一行(或哪一段)在执行. 相关设置 xdebug.coverage_enable 类型: boolean, 默认值: 1, 始于 Xdebug >= 2.2 ...
- 01HTTP服务&;AJAX编程
HTTP服务&AJAX编程 一.服务器 1. 什么是服务器? 能够提供某种服务的机器(计算机)称为服务器. 2.服务器的分类: 1.按系统分类:Lin ...
- MQTT V3.1--我的理解
最近因为工作需要,需要对推送消息了解,因此对MQTT进行了整理,这里更多的是对MQTT英文版的翻译和理解. MQTT(Message Queue Telemetry Transport),遥测传输协议 ...
- css写带边框的三角形
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
- CALayer 图层
// CALayer 图层属性,继承UIView都有该属性,可设置边框宽度.颜色.圆角.阴影等 UIImageView *imageView = [[UIImageView alloc]initWit ...
- Java事务处理全解析(三)——丑陋的案例
在本系列的上一篇文章中,我们看到了一个典型的事务处理失败的案例,其主要原因在于,service层和各个DAO所使用的Connection是不一样的,而JDBC中事务处理的作用对象正是Connectio ...
- jquery跳出当前的each循环
break----用return false; continue --用return ture; jquery是对象链,所以$(..).each()返回的还是对象集合.each(function(){ ...
- C++编写一个简单的DLL
什么是DLL: 自从微软推出16位的Windows操作系统起,此后每种版本的Windows操作系统都非常依赖于动态链接库(DLL)中的函数和数据,实际上 Windows操作系统中几乎所有的内容都由DL ...
- python脚本 随机定位坐标
import mathimport randomdef rad(dg): return (dg * math.pi / 180)def deg(rd): return (rd * 180 ...