奇技淫巧：快速求log2(x) |
您所在的位置：网站首页 › 在线计算log2 › 奇技淫巧：快速求log2(x) |
|
很多倍增的板子都需要算log，比如说LCA，RMQ，等等（其实我只知道这两个倍增，唉太菜了） 然后计算log有一个math的头文件，里面的log函数就是求出log10(x)，于是求log2(x)就相当于log(x)/log(2) 但是这样算很容易出玄学bug，因为算出来可能是取整×取整，然后就炸了 然后可以自己手打一个log，代码一般都是这样的： int log(int x) { int cnt = -1; while(x) { x >>= 1; cnt++; } return cnt; } //-1表示错误(log0)这个已经很快了，（吧），但是还是有很大的常数。 一般来说可以预处理出所有log，开一个数组，不停的×2×2然后全部预处理出来，以后用的时候查数组就可以了。 接下来重点来了！发放福利！ 今天突然想到了这个问题，然后喜大普奔地找到了个奇技淫巧的代码： int log(int n) { int result = 0; if(n&0xffff0000) {result += 16; n >>= 16; } if(n&0x0000ff00) {result += 8; n >>= 8; } if(n&0x000000f0) {result += 4; n >>= 4; } if(n&0x0000000c) {result += 2; n >>= 2; } if(n&0x00000002) {result += 1; n >>= 1; } return result; }
|
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |