CODEWITHSUNDEEP
bit-manipulation
Rohit
Rohit

Reputation: 7629

Counting Number of Paired Un-set bits At Even Boundaries

Given a 64-bit number what's the best way to find out the number of paired un-set bits at even boundaries. The extra zero padding after the MSB should be ignored.

For example:

For the two numbers 25223 and 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)

I could do a mask, shift-by-2 and compare, but I'm looking for something better. Is there anything faster than this:

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

What if I want to count the number of paired non-zero bits at even boundaries? What's the best method for that?

Upvotes: 0

Views: 337

Answers (4)

aka.nice
aka.nice

Reputation: 9512

This is not much cheaper (one loop per pair of zeroes + overhead) but it's just to expose a few bit tricks.

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

Upvotes: 0

ruslik
ruslik

Reputation: 14890

It's a simple question, but the way you put it scares me :)

Let's first try doing it to pairs of 1 s (you'll see why) for 32 bits:

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

All we need now it count_set_bits(unsigned) , that is very known function: http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

To count zero bits use count_pairs(~n) or 

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

EDIT: just observed the remark Given the 64 bit number... The extra zero padding after the MSB should be ignored. After what MSB? Do you mean the input is a byte? or word?

Upvotes: 3

Zimbabao
Zimbabao

Reputation: 8250

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

based on @rusliks answer, I tried making my answer a bit short.

Upvotes: 1

Zimbabao
Zimbabao

Reputation: 8250

This is for 32bits .. 0x55555555 is a dependency .. is order of number of set bit 

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

Upvotes: 0

Related Questions