Comptage de bits utilisés dans int

Si vous avez le nombre binaire 10110 comment puis-je le faire revenir 5? e.g un nombre qui indique combien de bits sont utilisés? Il y a quelques même les exemples ci-dessous:

101 doit revenir 3
000000011 doit retourner 2
11100 devrait revenir 5
101010101 doit retourner 9

Comment cela peut-il être obtenu de la façon la plus simple en Java? Je suis venu avec la méthode suivante, mais je peux être plus rapide:

public static int getBitLength(int value)
{
    if (value == 0)
    {
        return 0;
    }
    int l = 1;
    if (value >>> 16 > 0) { value >>= 16; l += 16; }
    if (value >>> 8 > 0) { value >>= 8; l += 8; }
    if (value >>> 4 > 0) { value >>= 4; l += 4; }
    if (value >>> 2 > 0) { value >>= 2; l += 2; }
    if (value >>> 1 > 0) { value >>= 1; l += 1; }
    return l;
}

en java int toujours utilise 32 bits
Il semble que vous manuellement déroulé une boucle, là.
Le titre est trompeur, car tous les 32 bits sont toujours utilisés dans un int.
Je sais le titre est un peu trompeur, mais je ne sais pas comment l'appeler, si vous avez des suggestions merci de nous l'envoyer et je vais modifier le titre.
Remarque ce sont les mêmes que log2(value)+1 stackoverflow.com/questions/3305059/...

OriginalL'auteur sigvardsen | 2010-05-29

Plus facile?

32 - Integer.numberOfLeadingZeros(value)

Si vous êtes à la recherche pour les algorithmes, les responsables de l'implémentation de l'API Java d'accord avec votre divide-and-conquer bitshifting approche:

public static int numberOfLeadingZeros(int i) {
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

Modifier: Comme un rappel pour ceux qui ont confiance dans la précision des calculs en virgule flottante, exécuter le test suivant harnais:

public static void main(String[] args) {
    for (int i = 0; i < 64; i++) {
        long x = 1L << i;
        check(x);
        check(x-1);
    }
}

static void check(long x) {
    int correct = 64 - Long.numberOfLeadingZeros(x);
    int floated = (int) (1 + Math.floor(Math.log(x) / Math.log(2)));
    if (floated != correct) {
        System.out.println(Long.toString(x, 16) + " " + correct + " " + floated);
    }
}

La première détection d'un écart:

ffffffffffff 48 49

La première solution est la meilleure 🙂
Bon exemple avec la virgule flottante d'erreur.

OriginalL'auteur meriton

6

Malheureusement, il n'existe pas de Integer.bitLength() méthode qui serait vous donner la réponse directement.

Une méthode analogue existe pour BigInteger, de sorte que vous pourriez utiliser:
```
BigInteger.valueOf(value).bitLength()
```
De la construction de la BigInteger objet sera un peu moins efficace, mais qui ne fera que question si vous le faites plusieurs millions de fois.

OriginalL'auteur starblue
2

Vous voulez calculer le logarithme en base 2 du nombre - à-dire:
```
1 + floor(log₂(valeur))
```
Java a de Maths.journal de la méthode qui utilise la base de e, de sorte que vous pouvez faire:
```
1 + Math.floor(Math.log(value) / Math.log(2))
```
Êtes-vous sûr que les erreurs d'arrondi n'aura pas d'incidence sur le résultat?
Raisonnablement sûr! Le seul problème est que pour une valeur de 0, lorsque vous vous retrouvez avec négatif infinis et d'autres belles choses 🙂
Un autre problème donné sont des nombres négatifs, le plus grand ensemble de bits.
Vous avez de la chance, les erreurs d'arrondi manifeste qu'au-delà de la gamme de int. Cependant, pour 0xffffffffffffL, votre code donnerait le résultat incorrect de 49, au lieu de 48. Je vais ajouter le code de test pour ma réponse.

OriginalL'auteur Chris

Attention à ce que vous demandez. Un très rapide de la technique est de faire une table de recherche:

int bittable [] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... };
int numbits (int v)
{
    return bittable [v];
}

où bittable contient une entrée pour chaque type int. Bien sûr qui a des complications pour les valeurs négatives. Un plus pratique serait de compter les bits dans bitfields du nombre

int bittable [16] = {0, 1, 1, 2,  1, 2, 2, 3,  1, 2, 2, 3,  2, 3, 3, 4};
int numbits (int v)
{
    int s = 0;
    while (v != 0)
    {
         s += bittable [v & 15];
         v >>= 4;
    }
    return s;
}

N'est-ce pas le comptage de bits, plutôt que de trouver l'indice de la plus haute bit?

OriginalL'auteur wallyk

1

Vous vraiment voulez juste trouver la position de la plus haute bit à 1. Voir cette page, sous la rubrique "Trouver entier logarithme de base 2 d'un entier (aka la position du bit le plus élevé ensemble)".

OriginalL'auteur Victor Liu

De ici, une façon de le faire avec, juste au niveau du bit et et plus:

int GetHighestBitPosition(int value) {
  if (value == 0) return 0;

  int position = 1;
  if ((value & 0xFFFF0000) == 0) position += 16;
  if ((value & 0xFF00FF00) == 0) position += 8;
  if ((value & 0xF0F0F0F0) == 0) position += 4;
  if ((value & 0xCCCCCCCC) == 0) position += 2;
  if ((value & 0xAAAAAAAA) == 0) position += 1;

  return position;
}

OriginalL'auteur Ken

0

Je pense que l'arrondi log_2 de ce numéro vous donnera ce dont vous avez besoin.

Quelque chose comme:
```
return (int)(Math.log(value) / Math.log(2)) + 1;
```
Êtes-vous sûr que les erreurs d'arrondi n'aura pas d'incidence sur le résultat?
Je pense que oui. Voir Chris réponse 🙂

OriginalL'auteur Oak

int CountBits(uint value)
{
    for (byte i = 32; i > 0; i--)
    {
        var b = (uint)1 << (i - 1);
        if ((value & b) == b)
            return i;
    }
    return 0;
}

OriginalL'auteur realworldcoder

0

Si vous êtes à la recherche pour le plus rapide (et sans table, ce qui est certainement plus rapide), c'est probablement l'un:
```
public static int bitLength(int i) {
    int len = 0;

    while (i != 0) {
        len += (i & 1);
        i >>>= 1;
    }

    return len;

}
```
Pourquoi êtes-vous & " ing len? @ 'len += (i & 1)'. Ne serait-ce pas seulement vous donner un compte sur tous les 1 à une chaîne de bits?

OriginalL'auteur cyanide
0

Entier.toBinaryString(valeur).longueur()

OriginalL'auteur Jacob Abraham
0

Une autre solution est d'utiliser le length() d'un BitSet qui, selon les API

Renvoie la "logique" taille " ... l'indice de
la plus peu ... plus un.

D'utiliser le BitSet vous avez besoin de créer un tableau. Donc, il n'est pas aussi simple que de commencer avec un pur int. Mais vous sortez de la JDK boîte - testés et pris en charge. Il devrait ressembler à ceci:
```
  public static int bitsCount(int i) {
    return BitSet.valueOf(new long[] { i }).length();
  }
```
Appliquée à des exemples dans la question:
```
  bitsCount(0b101); //3
  bitsCount(0b000000011); //2
  bitsCount(0b11100); //5
  bitsCount(0b101010101); //9
```
Lors de la demande de bits de la BitSetme semble être la bonne structure de données.

OriginalL'auteur LuCio

Vous devez vous connecter pour publier un commentaire.