Подсчет количества парных неустановленных битов на четных границах

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

Это простой вопрос, но то, как вы его сформулировали, пугает меня:)

Давайте сначала попробуем сделать это для пар 1 с (вы поймете почему) для 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? Вы имеете в виду, что вход является байтом? или слово?

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

Это не намного дешевле (один цикл на пару нулей + накладные расходы), но это просто разоблачение нескольких битовых уловок.

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

Answer 4

Это для 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;
    }