【Tricks】关于二进制的黑科技

近日,有幸看到一点黑科技,是一些函数:

— Built-in Function: int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.
返回‘1’的个数。

— Built-in Function: int __builtin_ffs (unsigned int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
返回右起第一个‘1’的位置。

对于这些函数,他们全是O(1)的
不仅如此,你还会发现你不包含任何库都可以编译通过
而且你会发现,它们也不是宏 QAQ
是不是感觉很神奇?

经过多方查证,这些是GCC编译器提供的函数
换一句话来,这些下划线函数NOI系列赛可以用QAQ
参见:https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
该系列的其他函数,可以在上面的网址全部查到

最后附上据说是 __builtin_popcount 的源码:

int count(unsigned u){
	u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}