计算偶数边界处配对未设置位的数量

Question

给定一个 64 位数字，找出偶数边界处配对未设置位的数量的最佳方法是什么。 MSB 之后的额外零填充应被忽略。

例如：

对于两个数字 25223 和 10578，

25223 -- 01 10 00 10 10 00 01 11
          7  6  5  4  3  2  1  0
Count = 2, (at positions 2 and 5)

10578 -- 00 10 10 01 01 01 00 10
          7  6  5  4  3  2  1  0
Count = 1, (at position 1. Ignore position 7)

我可以做一个掩码，移 2 并进行比较，但我正在寻找更好的东西。还有比这更快的吗：

def PairedCount(n):
    c=0
    while(n!=0):
        if((n & 3) == 0):
            c+=1
        n >>= 2;
    return c

如果我想计算偶数边界处配对非零位的数量怎么办？最好的方法是什么？

Answer 1

这是一个简单的问题，但你提出的方式让我感到害怕:)

让我们首先尝试对 32 位的 1 进行处理（你会明白为什么）：

unsigned count_pairs_1(unsigned n){
    n = n & ( n >> 1);  // bit N will be set if bits N and N+1 were set
    n &= 0x55555555;    // we need just those on even position, so ANDing with 0b01..0101
    return count_set_bits(n);  // now we need the number of 1 bits in the result
};

我们现在需要它 count_set_bits(unsigned) ，这是众所周知的函数：http: //www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

要计算零位，请使用 count_pairs(~n) 或

unsigned count_pairs_0(unsigned n){
    n = n | ( n >> 1); // bit N will be zero iff bits N and N+1 were zero
    n |= 0xAAAAAAAA; // all odd bits are set
    return 32 - count_set_bits(n);  // every remaining zero bit corresponds to zero pair in the input
};

编辑：刚刚观察了备注Given 64 位数字...MSB 之后的额外零填充应被忽略。在什么MSB之后？你的意思是输入是一个字节？或词？

Answer 2

unsigned count_pairs_0_n(unsigned n){
  unsigned int i=n;
  unsigned int l=0;
  while(i){l=i;i&=(i-1);}
  n=((l<<1) -1) &(~n);
  return count_pairs_1(n);
}

根据@rusliks 的回答，我尝试让我的答案简短一些。

Answer 3

这是针对 32 位的.. 0x55555555 是一个依赖项.. 是设置位的数量顺序

   int countpairs(int n){
      int o=n;
      int c=0;

      unsigned int i=n;
      unsigned int l=0;
      while(i){l=i;i&=(i-1);}

      n=((l<<1) -1) &(~n);

      while(n){
        unsigned int k= n&(n-1);
        unsigned int k2=k&(k-1);
        unsigned int k3=(n^k) + (k^k2);
        if((n^k) && k^k2 && (n^k)*2 == (k^k2) && ((n^k) & 0x55555555)) {
            c++;
        }
        n=k;
      }
     return c;
    }

Answer 4

这并没有便宜多少（每对零一个循环+开销），但它只是暴露一些小技巧。

size_t count_pairs_of_zeros( your_uint_type x );
{
   // create a mask with even bits set like 0x55555555
   // but independent of bit length 
   your_uint_type mask = 0;
   mask -= 1;
   mask /= 3;

   // replace 01 and 10 pairs by 11
   x |= x>>1;
   x &= mask;
   x |= x<<1;

   // count the pairs of zeros up to most significant bit
   size_t count = 0;
   while( x & (x+1) )
   {
      count++;
      // remove next pair of zeros
      x |= x+1;
      x |= x+1;
   }
   return count;
}