二进制有关操作模板

wangbinfeng · 2023-07-27 15:01:08 · 算法·理论

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;
     }