Nombre de bits utilisés dans int

Question

Si vous avez le numéro binaire 10110, comment puis-je l'obtenir pour retourner 5? par exemple un nombre qui indique combien de bits sont utilisés? Il y a quelques De même exemples ci-dessous:

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

Comment cela peut-il être obtenu le moyen le plus facile en Java? Je suis venu avec la méthode suivante, mais je peux être fait plus rapidement:

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

Answer 1

Le plus simple?

32 - Integer.numberOfLeadingZeros(value) 

Si vous êtes à la recherche d'algorithmes, les développeurs de l'API Java d'accord avec votre opérateurs de bits diviser pour mieux régner 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: Pour rappel à ceux qui ont confiance en la précision des calculs en virgule flottante, exécuter le faisceau d'essai suivant:

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

le premier écart détecté est la suivante:

ffffffffffff 48 49 

Answer 2

Je pense que le log_2 arrondi en place de ce nombre vous donnera ce dont vous avez besoin.

Quelque chose comme:

return (int)(Math.log(value)/Math.log(2)) + 1; 

Answer 3

Vous voulez calculer la base 2 logarithme du nombre - plus précisément:

1 + floor(log2(value))

Java a une méthode Math.log qui utilise la base e, de sorte que vous pouvez faire:

1 + Math.floor(Math.log(value)/Math.log(2))

Answer 4

Faites attention à ce que vous demandez. Une technique très rapide est de faire une consultation de table:

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 int. Bien sûr, cela a des complications pour les valeurs négatives. Une façon plus pratique serait de compter les bits 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; 
} 

Answer 5

Vous voulez vraiment juste trouver la position du bit le plus élevé qui est un 1. Voir this page, sous la rubrique « Trouver base de journal entier 2 d'un nombre entier (alias la position de l'ensemble de bits le plus élevé) ".

Answer 6

De here, une façon de le faire avec juste logique binaire 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; 
} 

Answer 7

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

Answer 8

Malheureusement, il n'y a pas de méthode Integer.bitLength() qui vous donnera directement la réponse.

Un procédé analogue existe pour BigInteger, vous pouvez donc utiliser que l'un:

BigInteger.valueOf(value).bitLength() 

Construire l'objet BigInteger va rendre un peu moins efficace, mais cela ne importe si vous le faites plusieurs millions de fois.

Answer 9

Si vous recherchez le plus rapide (et sans une table, ce qui est certainement plus rapide), ce qui est probablement l'un:

public static int bitLength(int i) { 
    int len = 0; 

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

    return len; 

}