Nombre de bits non définis appariés aux limites paires

Question

Étant donné un nombre de 64 bits, quel est le meilleur moyen de connaître le nombre de bits non affectés appariés aux limites paires. Le remplissage supplémentaire de zéro après le MSB doit être ignoré.

Par exemple:

Pour les deux numéros 25223 et 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) 

que je pouvais faire un masque, shift-by-2 et comparer, mais je cherche quelque chose de mieux. Y at-il plus rapide que ceci:

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

si je veux compter le nombre de bits non nuls par paires à même des limites? Quelle est la meilleure méthode pour cela?

Answer 1

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

basé sur @rusliks réponse, j'ai essayé de faire ma réponse un peu court.

Answer 2

Ceci est pour 32bits .. 0x55555555 est une dépendance .. est l'ordre du nombre de bits de jeu

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 3

Il est une question simple, mais la façon dont vous mettez ça me fait peur :)

Entre Nous d'abord essayer de le faire à des paires de 1 s (vous comprendrez pourquoi) pour 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 
}; 

Tout ce que nous devons maintenant count_set_bits(unsigned), qui est fonction très connue: http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

Pour compter zéro bits utilisent count_pairs(~n) ou

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: vient d'observer la remarque Compte tenu du nombre 64 bits ... Le rembourrage zéro supplémentaire après le MSB doit être ignorée. Après quoi MSB? Voulez-vous dire que l'entrée est un octet? ou un mot?

Answer 4

Ce n'est pas beaucoup moins cher (une boucle par paire de zéros + frais généraux) mais c'est juste pour exposer quelques astuces.

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