如何不优雅地手写__builtin_clz

在 NOIp 考场上,你随手写了个用到 __builtin_clzll 的二进制优化,然后突然想到下划线开头的东西是不让用的?(其实用了啥事没有)

于是你需要手写这玩意。在了解一些相关 IEEE 754 的知识之后,你意识到浮点数的指数部分恰好就代表二进制下第一个 1 出现在哪里。于是……

fesetround(FE_DOWNWARD);
// 如果需要使用 clz,务必把上面这行语句放在 main 的最开头,否则会出错
int clz(unsigned long long x) {
	double s = x;
	x = *((unsigned long long*) (&s));
	int ret = x >> 52 & ((1<<11)-1);
	ret = 1086 - ret;
	return ret;
}
int ctz(unsigned long long x) {
	x = x&-x;
	double s = x;
	x = *((unsigned long long*) (&s));
	int ret = x >> 52 & ((1<<11)-1);
	return ret - 1023;
}

并且这玩意很快,不会比 builtin 的慢多少。

使用上面的 clz 需要 fesetround 意为改变舍入模式,关于舍入模式看上一篇博客。不过这样做会改变全局的舍入模式,通常 OI 题里不在意这个东西,如果你真的在意的话可以用的时候切换(警告:频繁这样做很慢)