nombre nombre de bits définis dans entier

-1

je suis studing différentes méthodes sur le comptage des bits ou des méthodes de comptage de la population fopr entier donné, au cours de ce jour, je cherchais à comprendre comment les algorithmes suivants fonctionnenombre nombre de bits définis dans entier

pop(x)=-sum(x<<i) where i=0:31

Je pense qui calculent après chaque valeur de x, nous aurons

x+2*x+4*x+8*x+16*x+..............+2^31*x =4294967294*x

si on le multiplie par -1, nous obtenons -4294967294*x, mais comment il compte le nombre de bits? S'il vous plaît aidez-moi à comprendre cette méthode well.thanks

Source

2012-03-22 dato datuashvili

Cette méthode ne fonctionne pas. Si vous pensez que cela fonctionne, écrivez-le dans le code et testez-le. – interjay

Visitez ce site: http://graphics.stanford.edu/~seander/bithacks.html Il explique toutes les opérations dont vous avez besoin. – linello

Etes-vous sûr de l'avoir? Si je comprends votre notation, alors mettre 'x = 8' (par exemple) donne une somme de binaire 11111111 11111111 11111111 11111000, donc -sum est binaire 00 ... 001000 = décimal 8. Mais quand j'ai compté les bits à la main, J'ai eu la réponse 1. – TonyK

Je crois que vous dire

$\mathrm{pop}(x) = -\sum_{i=0}^{31} (x \overset{\mathrm{rot}}{\ll} i)$

comme on le voit dans la couverture du livre Hacker's Delight, où le symbole signifie rotation gauche pas gauche changement qui produira des résultats erronés et downvotes.

Cette méthode fonctionne parce que la rotation entraînera l'apparition de tous les chiffres binaires de x dans tous les bits possibles dans tous les termes et en raison du complément de 2.

Prenez un exemple plus simple. Tenez compte des nombres avec seulement 4 chiffres binaires, où les chiffres peuvent être représentés comme ABCD, le moyen de sommation:

ABCD // x <<rot 0 
+ BCDA // x <<rot 1 
+ CDAB // x <<rot 2 
+ DABC // x <<rot 3

Nous notons que chaque colonne a tous A, B, C, D. Maintenant, ABCD en fait des moyens "2³ A + 2² B + 2¹ C + 2⁰ D", de sorte que la somme est juste:

2³ A  + 2² B  + 2¹ C  + 2⁰ D 
+ 2³ B  + 2² C  + 2¹ D  + 2⁰ A 
+ 2³ C  + 2² D  + 2¹ A  + 2⁰ B 
+ 2³ D  + 2² A  + 2¹ B  + 2⁰ C 
—————————————————————————————————————————————————————— 
= 2³(A+B+C+D) + 2²(B+C+D+A) + 2¹(C+D+A+B) + 2⁰(D+A+B+C) 
= (2³ + 2² + 2¹ + 2⁰) × (A + B + C + D)

la (A + B + C + D) est la population d'x et (2³ + 2² + 2¹ + 2⁰) = 0b1111 est -1 dans le complément de 2, donc la sommation est le négatif du nombre de population.

L'argument peut facilement être étendu à des nombres de 32 bits.

Source

2012-03-22 16:19:00 kennytm

#include <stdio.h> 
#include <conio.h> 

unsigned int f (unsigned int a , unsigned int b); 

unsigned int f (unsigned int a , unsigned int b) 
{ 
    return a ? f ((a&b) << 1, a ^b) : b; 
} 

int bitcount(int n) { 
    int tot = 0; 

    int i; 
    for (i = 1; i <= n; i = i<<1) 
     if (n & i) 
      ++tot; 

    return tot; 
} 

int bitcount_sparse_ones(int n) { 
    int tot = 0; 

    while (n) { 
     ++tot; 
     n &= n - 1; 
    } 

    return tot; 
} 

int main() 
{ 

int a = 12; 
int b = 18; 

int c = f(a,b); 
printf("Sum = %d\n", c); 

int CountA = bitcount(a); 
int CountB = bitcount(b); 

int CntA = bitcount_sparse_ones(a); 
int CntB = bitcount_sparse_ones(b); 

printf("CountA = %d and CountB = %d\n", CountA, CountB); 
printf("CntA = %d and CntB = %d\n", CntA, CntB); 
getch(); 

return 0; 

}

Source

2014-12-19 11:46:45 kapilddit

nombre nombre de bits définis dans entier

Répondre

Questions connexes