二进制有关操作模板

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