关于乘法运算时钟周期的警示,如果你全开long long导致最后两个点TLE
  • 板块P10788 sql
  • 楼主dxzier
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/5 09:31
  • 上次更新2024/8/5 10:26:41
查看原帖
关于乘法运算时钟周期的警示,如果你全开long long导致最后两个点TLE
310449
dxzier楼主2024/8/5 09:31

在 CPU 的物理电路实现中,一个 64 位串行乘法器可以等效看作如下代码。

//a*b;
for(int i=1;i<=64;i++){
	if(a&1) c+=b;//此处内置一个64位全加法器
	b=b<<1;
	a=a>>1;
}
return c;

而如果使用 int 乘法,则循环的条件将变为 i≤32i\le 32,所调用的加法、左移和右移的次数将减少至原来的一半,可以近似认为等同于时钟周期为 long long 版本的一半。

同时,如果专门设计了相对应的 32 位全加法器电路,所需要的时钟周期还能再缩短为原来的一半。但考虑到时序问题,仅当 64 位全加法器的时钟周期大于二时才会减半。所以这个根使用的 CPU 具体架构有关。

综上所述,long long 乘法的常数大约是 int 乘法的二至四倍。


以上仅为学习数字电路后结合高中物理知识所谈,相关设计仅进行过仿真模拟(限于成本只有加法器实际做过),且使用的理论可能过于古老,与现在 CPU 架构存在差异。原因仅供参考。

2024/8/5 09:31
加载中...