Comment compter le nombre de 1 qu'un nombre aura en binaire?

Question

Double Possible:
Meilleur algorithme pour compter le nombre de bits d'un entier de 32 bits?

Comment puis-je compter le nombre de 1's un certain nombre auront en binaire?

Donc, disons que j'ai le nombre 45, ce qui est égal à 101101 en binaire et dispose de 4 1s'en elle. Quel est le moyen le plus efficace d'écrire un algorithme pour ce faire?

Answer 1

Au lieu d'écrire un algorithme pour ce faire de son mieux pour utiliser le construit en fonction. Entier.bitCount()

Ce qui rend ce particulièrement efficace, c'est que la JVM peut considérer ceci comme une valeur intrinsèque. c'est à dire reconnaître et remplacer l'ensemble de la chose avec une seule machine code d'instruction sur une plate-forme qui prend en charge par exemple Intel/AMD

---

Pour démontrer l'efficacité de cette optimisation est

public static void main(String... args) {
    perfTestIntrinsic();

    perfTestACopy();
}

private static void perfTestIntrinsic() {
    long start = System.nanoTime();
    long countBits = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits += Integer.bitCount(i);
    long time = System.nanoTime() - start;
    System.out.printf("Intrinsic: Each bit count took %.1f ns, countBits=%d%n", (double) time / Integer.MAX_VALUE, countBits);
}

private static void perfTestACopy() {
    long start2 = System.nanoTime();
    long countBits2 = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits2 += myBitCount(i);
    long time2 = System.nanoTime() - start2;
    System.out.printf("Copy of same code: Each bit count took %.1f ns, countBits=%d%n", (double) time2 / Integer.MAX_VALUE, countBits2);
}

// Copied from Integer.bitCount()
public static int myBitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

imprime

Intrinsic: Each bit count took 0.4 ns, countBits=33285996513
Copy of same code: Each bit count took 2.4 ns, countBits=33285996513

Chaque nombre de bits à l'aide de la valeur intrinsèque de la version et de boucle prend seulement 0,4 nano-seconde en moyenne. À l'aide d'une copie du même code prend 6x plus (on obtient le même résultat)

Answer 2

Le moyen le plus efficace de compter le nombre de 1 dans une variable de 32 bits v je sais c'est:

v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // c is the result

Mise à jour: je tiens à préciser que ce n'est pas mon code, en fait il est plus vieux que moi. Selon Donald Knuth (The Art of Computer Programming , Vol IV, p 11), le code est d'abord apparu dans le premier manuel de programmation, La Préparation de Programmes sur un Ordinateur Numérique Électronique par Wilkes, Wheeler et Gill (2e Ed 1957, réédité en 1984). Pages 191-193 de la 2e édition du livre présenté Chouette Parallèle Comte par D B Gillies et J C P Miller.

Answer 3

Voir Bit Twidling Hacks et étudier tous les algorithmes de "comptage de bits". En particulier, la méthode de Brian Kernighan est simple et assez rapide si vous attendez une petite réponse. Si vous attendez une réponse uniformément distribuée, la table de recherche pourrait être meilleure.

Answer 4

Ceci s'appelle le poids de Hamming . On l'appelle aussi population count , popcount ou sideways sum .

Answer 5

La suite est soit de "Bit se Tourner les Hacks" de la page ou Knuth les livres (je ne me souviens pas). Il est adapté aux unsigned les entiers 64 bits et fonctionne sur C#. Je ne sais pas si le manque de valeurs non signées en Java qui crée un problème.

En passant, j'écris le code seulement pour la référence; la meilleure réponse est à l'aide de Integer.bitCount() comme @Lawrey dit; car il y a une machine spécifique de code de l'opération pour cette opération dans certains (mais pas tous) Processeurs.

  const UInt64 m1 = 0x5555555555555555;
  const UInt64 m2 = 0x3333333333333333;
  const UInt64 m4 = 0x0f0f0f0f0f0f0f0f;
  const UInt64 h01 = 0x0101010101010101;

  public int Count(UInt64 x)
  {
      x -= (x >> 1) & m1;
      x = (x & m2) + ((x >> 2) & m2);
      x = (x + (x >> 4)) & m4;
      return (int) ((x * h01) >> 56);
  }