Discussion :

[elglantosimpatico]

Bonjour,

Je cherche donc à trouver la puissance de deux la plus proche d'une nombre et supérieure à celui-ci. Cependant, je voudrais quelque chose de plus raffiné qu'une boucle while avec une série de test. J'ai donc cherché un peu et ai trouvé cet article parlant du sujet :
https://grim7reaper.rolinh.ch/blog/2...e-a-un-nombre/
Cependant, j'ai du mal à comprendre son code et donc à le transposer en Python. Quelqu'un y verrait-il plus clair dans ce qui est écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
unsigned next_highest_power_of_2(unsigned n)
{
    unsigned i;
    --n;
    for(i = 1; i < sizeof n * CHAR_BIT; i <<= 1)
        n |= n >> i;
    return ++n;
}

[BufferBob]

salut,

si l'auteur passait dans le coin il te l'expliquerait sûrement, ce que je retiens perso de son article c'est qu’il n’y a pas de pire cas (sic). en fait et sauf erreur, il fait très exactement ce que tu ne veux pas faire, à savoir une boucle de 1 à n

sinon une méthode parmi d'autres pour faire ça en python pourrait être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

2**len(bin(n)[2:])

c'est moche, et ça marche du tonnerre, sans boucle apparente ;p

[wiztricks]

Salut,

Sans boucle apparente...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
>>> from math import ceil, log, pow
>>> next = lambda x: int( pow(2, ceil(log(x, 2))))
>>> next(20)
32
>>>

- W

[tyrtamos]

Bonjour,

Encore plus simple (si Python version >=3.1):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

2**(n).bit_length()

[edit]: et si on éviter le calcul d'une puissance:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1<<(n).bit_length()

[elglantosimpatico]

Merci pour toutes vos réponses.

salut,

si l'auteur passait dans le coin il te l'expliquerait sûrement, ce que je retiens perso de son article c'est qu’il n’y a pas de pire cas (sic). en fait et sauf erreur, il fait très exactement ce que tu ne veux pas faire, à savoir une boucle de 1 à n

De ce que je comprends, il fait cette boucle dans la section 1 Approche naïve mais dans la section 2 Optimisation cela semble différent.

Du coup, j'en étais arrivé au petit bout de code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
x = 1024
 
# Calculate number of bits
 
nb_bits = x.bit_length()
 
# Calculate number of bits
 
x_new = 2 ** (nb_bits)

Mais suite au message de tyrtamos, il y a en effet bien plus simple.

Cela fonctionne très bien sauf si x est égal à une puissance de 2. Dans ce cas, cela prend la puissance de 2 supérieure. Par exemple, si x = 1024, cela fait 11 bits et 2**11 fait 2048. Mais je peux régler cela avec une condition :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
if x == 2 ** (nb_bits-1):
    x_new = x
else:
    x_new = 1<<(x).bit_length()

Voyez-vous une méthode plus simple/rapide que cette condition ?

J'aurais cependant deux questions. Premièrement par rapport à ce message :

[edit]: et si on éviter le calcul d'une puissance:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1<<(n).bit_length()

Donc cela fonctionne mais j'ai du mal à comprendre exactement ce que cette fonction teste. Par exemple,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1>>(n).bit_length()

[/QUOTE] me renvoi 0 mais je ne comprends pas pourquoi...

Pour finir, quelle est la différence entre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

2**(n).bit_length()

et :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

2**len(bin(n)[2:])

Est-ce juste une différence Python 2.x et Python 3.x où il y a-t-il d'autres subtilités ?

[wiztricks]

Cela fonctionne très bien sauf si x est égal à une puissance de 2. Dans ce cas, cela prend la puissance de 2 supérieure. Par exemple, si x = 1024, cela fait 11 bits et 2**11 fait 2048. Mais je peux régler cela avec une condition :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
if x == 2 ** (nb_bits-1):
    x_new = x
else:
    x_new = 1<<(x).bit_length()

Voyez-vous une méthode plus simple/rapide que cette condition ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1 << (x-1).bit_length()

- W

[BufferBob]

De ce que je comprends, il fait cette boucle dans la section 1 Approche naïve mais dans la section 2 Optimisation cela semble différent.

c'est pareil, la version optimisée contient une boucle également, il la déplie même plus bas dans son article
outre la méthode employée (dans la naïve on compare n avec une puissance de 2 jusqu'à ce que ça dépasse, dans l'optimisée on met tous les bits à 1 et à la fin on incrémente pour avoir la puissance de 2 supérieure), la différence entre les deux tient dans le fait que pour une taille d'entier donné, mettons 16bits, où n=16362, la fonction naïve fera tourner sa boucle 14 fois (jusqu'à tomber sur 16384 > n) tandis que la fonction optimisée fera tourner la sienne 4 fois et ce quelque soit la valeur de n codée sur 16bits

la boucle de la fonction optimisée est pourtant très visible (mais pas forcément très lisible) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (i = 1; i < sizeof(n) * CHAR_BITS; i <<= 1)

si on a un nombre n sur 64 bits par exemple, la variable i dans la boucle prendra successivement les valeurs 1,2,4,8,16 et 32, dernière valeur à ne pas passer la condition d'arrêt de la boucle, donc 6 itérations seulement

l'opérateur << effectue un décalage de x bits vers la gauche, donc si on prend le nombre 1, qu'on codera au minimum dans un type C char (8 bits) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
1      == 00000001
1 << 6 == 00000001 << 6
1 << 6 == 01000000
1 << 6 == 64

idem pour l'opérateur >> qui effectuera un décalage de bits vers la droite

or décaler de x bits vers la gauche ou la droite revient ni plus ni moins à multiplier ou diviser x fois par 2, ça revient donc au même que 2^x, qu'à l'occasion on écrit 2**x en python (ou à l'inverse 2**(1/x) donc), mais les deux écritures reviennent en pratique à la même chose

quant à bin(n)[2:] c'est juste très moche, puisque ça implique une conversion du nombre pour ensuite lui amputer deux caractères, bref c'est pas joli, mais ça marche
ceci dit et même si utiliser n.bit_length() est bien plus élégant, rien ne garantit qu'il n'y a là dedans aucune boucle non plus (je suis près à parier que si)

enfin il faut comprendre que chercher des méthodes optimisées au cycle ou au bit près pour écrire la routine en Python n'a pas vraiment de sens, ça a un sens avec un programme C ou C++ parcequ'on a un contrôle très fin sur le code machine généré et on sait qu' hormis quelques bidouilles salvatrices du compilateur ce qu'on a dans le code source se retrouvera dans le code machine, alors qu'en Python ça n'est pas le cas, par exemple là où n |= n >> i; donnera ~5 instructions une fois compilé, l'équivalent en Python peut très bien occasionner l'exécution de +100 instructions, ce qui fera perdre tout son sens à l'optimisation en question

[wiztricks]

Est-ce juste une différence Python 2.x et Python 3.x où il y a-t-il d'autres subtilités ?

Pour ce genre de question il faut prendre le temps d'aller lire la documentation.
Vous y trouverez les 2 autres méthodes mentionnées ici comme alternatives à... et qu'il n'y a pas de changement côté Python3.

quant à bin(n)[2:] c'est juste très moche, puisque ça implique une conversion du nombre pour ensuite lui amputer deux caractères, bref c'est pas joli, mais ça marche
ceci dit et même si utiliser n.bit_length() est bien plus élégant, rien ne garantit qu'il n'y a là dedans aucune boucle non plus (je suis près à parier que si)

Oui çà boucle mais, le code est écrit en C.

- W

[elglantosimpatico]

Merci beaucoup pour votre aide.