代码之家 › 专栏 › 技术社区 › Rohit

偶数边界上成对未设置位的计数

bit-manipulation

Rohit · 技术社区 · 14 年前

给定一个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)

我可以做一个面具,两个一组,然后比较,但是我在找更好的。还有比这更快的吗:

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

如果我想计算偶数边界上成对的非零位的数目呢?最好的方法是什么?

4 回复 | 直到 14 年前

Zimbabao 14 年前

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的回答,我试着让我的回答简短一点。

ruslik 14 年前

这是一个简单的问题,但你说的方式让我害怕:)

我们先试着对 1 s(你会明白为什么)32位:

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

编辑:刚刚看到这句话 给定64位数字 ... 应忽略MSB之后的额外零填充 . 在什么MSB之后?你的意思是输入是一个字节吗?还是文字?

Zimbabao 14 年前

这是32位的。。0x555555是依赖项。。是设定位的数量顺序

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

aka.nice 12 年前

这并不便宜(每对0一个循环+开销),但只是为了暴露一些小技巧。

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