二进制有关操作模板

1. lowbit：

lowbit(x)是 $x$ 的二进制表达式中最低位的1所对应的值

template<typename T>
T lowbit(T x){
   return x&-x;
}

2. 求二进制中1的个数：

• 【方法一】 库函数：__builtin_popcountll(n)
  • 附库函数的具体实现：

unsigned popcount (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;
}

• 【方法二】 编程实现：
  • 【方法二·①】

template<typename T>
T popcnt(T x){
	T ret=0;
	for(;x;x&=x-1)ret++;
	return ret;
}

• 【方法二·②】

template<typename T>
T popcnt(T x){
	T ret=0;
	for(;x;x>>=1)if(x&1)ret++;
	return ret;
}