Comment trouver la plus grande puissance de 2 moins que le nombre donné

J'ai besoin de trouver la plus grande puissance de 2 inférieure au nombre donné.
Et je l'ai coincé et ne peut pas trouver une solution.

Code:

public class MathPow
{
   public int largestPowerOf2 (int n)
   {
        int res = 2;        
        while (res < n) {
                res =(int)Math.pow(res, 2);
        }

        return res;
   }
}

Cela ne fonctionne pas correctement.

Test de sortie:

Arguments Actual Expected
-------------------------
9         16     8       
100       256    64      
1000      65536  512     
64        256    32

Comment résoudre ce problème?

source d'informationauteur nazar_art

  1. 11

    Changement res =(int)Math.pow(res, 2); à res *= 2; Ce sera le retour de la puissance de 2 supérieure à res.

    Le résultat final que vous cherchez est donc enfin être res /2 après le temps est terminé.

    Pour empêcher que le code de débordement de la valeur int de l'espace que vous devrait/pourrait changer le type de res à double/long, tout ce qui peut contenir des valeurs plus élevées que int. En fin de compte vous devez voter qu'une seule fois.

  2. 39
    Integer.highestOneBit(n-1);

    Pour n <= 1 la question n'a pas vraiment de sens. Que faire dans ce gamme est laissé au lecteur intéressé.

    La est une bonne collection de bits se tourner les algorithmes Hacker Plaisir.

  3. 9

    Vous pouvez utiliser cette peu de bidouille:

    v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;
  4. 8

    Pourquoi ne pas utiliser les journaux?

    public int largestPowerOf2(int n) {
    return (int)Math.pow(2, Math.floor(Math.log(n) / Math.log(2));
}

    log(n) /log(2) vous indique le nombre de fois 2 va dans un certain nombre. En prenant la parole, vous obtient la valeur de l'entier arrondi vers le bas.

  5. 7

    Il y a une belle fonction dans Integer qui est utile, numberOfLeadingZeros.

    Avec elle, vous pouvez faire

    0x80000000 >>> Integer.numberOfLeadingZeros(n - 1);

    Qui fait des choses bizarres quand n est 0 ou 1, mais pour ces entrées n'est pas bien défini "puissance la plus élevée de deux de moins que n".

    edit: cette réponse est encore mieux

  6. 6

    Vous pourriez éliminer le bit le moins significatif dans n jusqu'à ce que n est une puissance de 2. Vous pouvez utiliser l'opérateur au niveau du bit ET avec n et n-1, ce qui permettrait d'éliminer le bit le moins significatif dans n jusqu'à ce que n est une puissance de 2. Si à l'origine, n est une puissance de 2, alors tout ce que vous avez à faire est de réduire la n de 1.

    public class MathPow{
   public int largestPowerOf2(int n){
      if((n & n-1) == 0){ //this checks if n is a power of 2
         n--; //Since n is a power of 2 we have to subtract 1
      }
      while((n & n-1) != 0){ //the while will keep on going until n is a power of 2, in which case n will only have 1 bit on which is the maximum power of 2 less than n. You could eliminate the != 0 but just for clarity I left it in
         n = n & n-1; //we will then perform the bitwise operation AND with n and n-1 to eliminate the least significant bit of n 
      }
      return n;
   }
}

    EXPLICATION:

    Lorsque vous avez un nombre n (qui n'est pas une puissance de 2), la plus grande puissance de 2 inférieure n est toujours le bit le plus significatif dans n. Dans le cas d'un nombre n qui est une puissance de 2, la plus grande puissance de 2 inférieure à n est la droite peu avant le peu qui est dans n.

    Par exemple, si nous avons eu 8 (qui est de 2 à la 3ème puissance), sa représentation binaire est de 1000 0 qui est en gras serait la plus grande puissance de 2 avant de n. Puisque nous savons que chaque chiffre binaire représente une puissance de 2, alors, si nous avons n sous la forme d'un nombre est une puissance de 2, la plus grande puissance de 2 inférieure à n serait la puissance de 2 avant, ce qui serait le morceau avant de le seul bit dans n.

    Avec un nombre n, qui n'est pas une puissance de 2 et n'est pas 0, nous savons que, dans la représentation binaire de n aurait plusieurs bits, ces bits ne représentent qu'une somme de différentes puissances de 2, le plus important serait le bit le plus significatif. Ensuite, nous pourrions en déduire que n est que le bit le plus significatif, plus quelques autres bits. Puisque n est représenté dans une certaine longueur de bits et le bit le plus significatif est la plus haute puissance de 2, on peut représenter avec le même nombre de bits, mais il est aussi le plus petit nombre que nous pouvons représenter avec beaucoup de bits, nous pouvons conclure que le bit le plus significatif est la plus haute puissance de 2 inférieure à n, parce que si nous ajoutons une autre pour le représenter à la prochaine puissance de 2, on a une puissance de 2 supérieure à n.

    EXEMPLES:

    Par exemple, si nous avions 168 (qui est 10101000 en binaire) le tout en prendrait 168 et soustraire 1 167 (qui est 10100111 en binaire). Ensuite, nous ferions de la bit-à-bit ET sur les deux numéros.
    Exemple:

      10101000
& 10100111
------------
  10100000

    Nous avons maintenant le nombre binaire 10100000. Si on soustrait 1 de il en et nous utilisons le bit à bit ET sur les deux numéros nous obtenons 10000000 qui est de 128, ce qui est 2 à la puissance de 7.

    Exemple:

      10100000
& 10011111
-------------
  10000000

    Si n ont été à l'origine d'une puissance de 2, alors nous devons soustraire 1 à partir de n. Par exemple, si n est de 16, qui est 10000 en binaire, nous soustraire 1 qui nous laisserait 15, qui est 1111 en binaire, et on le stocke dans n (ce qui est le cas). Nous avons ensuite aller dans le temps ce qui ne l'opérateur au niveau du bit ET avec n et n-1, ce qui serait de 15 (en binaire 1111) & 14 (en binaire 1110).

    Exemple:

      1111
& 1110
--------
  1110

    Nous nous retrouvons maintenant avec 14. Nous effectuons ensuite le bit à bit ET avec n et n-1, qui est de 14 (binaire 1110) & 13 (binaire 1101).

    Exemple:

      1110
& 1101
---------
  1100

    Maintenant, nous avons 12 et nous avons seulement besoin d'éliminer un dernier bit le moins significatif. Encore une fois, nous avons ensuite exécuter le bit à bit ET sur n et n-1, qui est de 12 (en binaire 1100) et 11 (en binaire 1011).

    Exemple

      1100
& 1011
--------
  1000

    Nous sommes enfin à gauche avec 8 qui est la plus grande puissance de 2 inférieure à 16.

  7. 3
    public class MathPow
{
   public int largestPowerOf2 (int n)
   {
        int res = 2;        
        while (res < n) {
                res =res*2;
        }

        return res;
   }
}
  8. 3

    Vous êtes à la quadrature res à chaque fois, ce qui signifie que vous calculer 2^2^2^2 au lieu de 2^k.

    Changer votre évaluation suivantes:

    int res = 2;
while (res * 2 < n) {
    res *= 2;
}

    Mise à jour:

    Bien sûr, vous avez besoin de vérifier pour dépassement des intdans ce cas, la vérification de

    while (res <= (n - 1) /2)

    semble beaucoup mieux.

  9. 3

    Ici est un circuit de décalage de bits de la méthode que j'ai écrit à cet effet:

    public static int nextPowDown(int x, int z) {
    if (x == 1)
        return z;
    return nextPowDown(x >> 1, z << 1);
}

    Ou plus courte définition:

    public static int nextPowTailRec(int x) {
    return x <= 2 ? x : nextPowTailRec(x >> 1) << 1;
}

    Donc dans votre méthode principale de laisser le z argument toujours égale 1. C'est dommage que les paramètres par défaut ne sont pas disponibles ici:

    System.out.println(nextPowDown(60, 1));                //prints 32
System.out.println(nextPowDown(24412, 1));             //prints 16384
System.out.println(nextPowDown(Integer.MAX_VALUE, 1)); //prints 1073741824
  10. 2

    Trouver le premier ensemble de bits de gauche à droite et de faire tous les autres bits de 0.

    Si il ya seulement 1 bit puis shift droit par un.

  11. 1
    public class MathPow
{
   public int largestPowerOf2(int n)
   {
        int res = 1;        
        while (res <= (n-1)/2)
        {
            res = res * 2;
        }

        return res;
   }
}
  12. 1

    Si le nombre est un entier, vous pouvez toujours la changer en binaire puis de trouver le nombre de chiffres.

    n = (x>>>0).toString(2).length-1
  13. 0
    p=2;
while(p<=n)
{
    p=2*p;
}
p=p/2;
  14. 0

    Si le nombre est une puissance de deux, alors la réponse est évidente. (juste de décalage de bits) si pas bien alors il est peut également être atteint par le décalage de bits.

    trouver la longueur de la nombre donné en représentation binaire. (13 en binaire = 1101 ; longueur est de 4)

    alors
    shift 2 par (4-2) //4 est la longueur de la nombre donné en binaire

    le ci-dessous de code java permettra de résoudre ce pour BigIntegers(donc en gros pour tous les nombres).

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        

    String num = br.readLine();
    BigInteger in = new BigInteger(num);
    String temp = in.toString(2);

    System.out.println(new BigInteger("2").shiftLeft(temp.length() - 2));
  15. 0

    J'ai vu un autre BigInteger solution ci-dessus, mais qui est en fait assez lent. D'une manière plus efficace si nous voulons aller au-delà integer et long est 

    BigInteger nvalue = TWO.pow(BigIntegerMath.log2(value, RoundingMode.FLOOR));

    où TWO est tout simplement BigInteger.valueOf(2L)

    et BigIntegerMath est prise à partir de la Goyave.

  16. 0

    Je pense que c'est la façon la plus simple de le faire.

    Integer.highestOneBit(n-1);

  17. 0

    Simple les opérations sur les bits doivent travailler 

     public long largestPowerOf2 (long n)
 {      
 //check already power of two? if yes simply left shift
    if((num &(num-1))==0){
        return num>>1;
    }

  //assuming long can take 64 bits     
    for(int bits = 63; bits >= 0; bits--) {
        if((num & (1<<bits)) != 0){
            return (1<<bits);
        }
    }
    //unable to find any power of 2
    return 0;   
  }
  18. 0

    Un peu en retard mais...

    (En supposant que nombre 32 bits.)

    n|=(n>>1);
n|=(n>>2);
n|=(n>>4);
n|=(n>>8);
n|=(n>>16);
n=n^(n>>1);

    Explication:

    La première | permet de s'assurer de l'origine de transmission haut et le 2e plus haut sommet bits sont définis. Le deuxième | fait en sorte que ces deux, et les deux sont, etc, jusqu'à ce que vous frappez tous les 32 bits. Ie

    100010101 -> 111111111

    Puis on enlève tous, mais le haut bits par xor avec la chaîne de 1 avec une chaîne de 1 est décalé à gauche, et nous nous retrouvons avec juste un peu haut, puis 0.