Youhou. Est-ce que quelqu'un aurait une solution rapide pour déterminer la puissance de 2 immédiatement supérieure à un entier positif quelconque ? Plus concrètement, pour determiner n tel que k n'existe pas avec size<=2^k<2^n, si size est l'entier positif quelconque considéré. Pour le moment, j'ai écrit une fonction moche qui le fait (cf plus loin) mais c'est très lent.
Si quelqu'un a une idée, je suis preneur (peu importe que la solution rendue soit n ou 2^n). Merci d'avance.
 
int expDeux(int x) {
  int k=0;
  int p=1;
  while (p<x) {
    k++;
    p<<=1;
  }
  return k;
}

tu masques, tu gardes le bit le plus a gauche de ton entier et tu decales de 1 vers la gauche

 
Euh j'ai pas compris. Tu masques avec quoi ? Et d'ailleurs sauf erreur de ma part, si tu appliques cette méthode en bourrin pour 8 tu obtiendras 16 ce qui n'est pas vraiment le but recherché. Donc silteplait ecris moi un bout de code rapide qui implémente ta methode (ou alors décris au moins le masque). Si c'est plus rapide que ma fonction, eh bien bravo et merci

Certes, mais comment fait-il pour générer son masque puisqu'il ne sait pas a priori où est le bit le plus à gauche ? En fait il me semble qu'il existe une instruction x86 pour le savoir, mais ça ne sera pas portable... Sinon il faut le chercher, ce qui n'est pas plus rapide que la fonction qu'il a déja écrite.

ben jusqu'a preuve du contraire, 16 est la puissance de 2 immédiatement supérieure a 8 ... m'enfin bon ...*
 
dans l'idée c :
 
le but est de masquer les bits de poids les plus faibles
 
ex : 0011 1001 pour obtenir 0010 0000
 
d'ou un masque 0001 1001
 
ce qui fait que 0011 1001 XOR 0001 1001 te donne 0010 0000
 
et 0010 0000 <<= 1 te donne la puissance de 2 immédiatement supérieure

Bon tu n'as pas du comprendre le problème... Le masque "0001 1001", tu l'obtiens comment ? Il n'est pas plus facile à obtenir que le "0010 0000", ou même directement "0100 0000"

Matafan a écrit a écrit : Bon tu n'as pas du comprendre le problème... Le masque "0001 1001", tu l'obtiens comment ? Il n'est pas plus facile à obtenir que le "0010 0000", ou même directement "0100 0000"

 
 
oué bon g rien dit ...
je sais que c possible, mais j'me souviens plus ...
 
j'ai une autre soluce en stock, j'vais manger

si tu fais
 
(x - (x>>1)) << 1  
c'est pas bon ?

 
nan

bon ma soluce avec le masque marche, mais ne sera plus rapide que lorsque l'on est relativement proche de la capacité max du type utilisé
suffit de décaler vers la gauche jusqu'a obtenir 1, et de redécaler ce qu'on a ainsi obtenu d'autant de fois vers la droite
ensuite le XOR, et ensuite le décalage de 1 vers la gauche

En passant par la valeur hexa (sprintf avec %x) et en "jouant" avec le caractère de gauche ? Idée comme ça, mais faudrait approfondir .

carbon_14 a écrit a écrit : En passant par la valeur hexa (sprintf avec %x) et en "jouant" avec le caractère de gauche ? Idée comme ça, mais faudrait approfondir .

 
spa con
 
 
tain ca fait tellement longtemps que j'ai plus joué avec ca en C que j'ai presque oublié tous les ptits trucs  

Hou on est parti dans des trucs là Moi je dis, c'est soit avec un ch'tit bout d'assembleur (avec la fameuse instruction qui donne la position du premier bit à 1), soit une solution qui ne sera pas plus rapide que ce que tu as déjà.

 
remarque que si ton entier occupe effectivement tous les octets du type utilisé, un  
 
2 puissance ((8 * nombre d'octets) - (nombre de decalages a gauche faits jusqu'a obtenir 1  -  1))
 
fait aussi l'affaire je crois
 
c valable dans tous les cas ou tu connais le nombre d'octes utilisés par ton entier

Matafan a écrit a écrit : Hou on est parti dans des trucs là Moi je dis, c'est soit avec un ch'tit bout d'assembleur (avec la fameuse instruction qui donne la position du premier bit à 1), soit une solution qui ne sera pas plus rapide que ce que tu as déjà.

 
ben j'crois me souvenir qu'il  a moyen de l'obtenir aussi en C, mais je sais plus comment
 
ps : avec ce genre de question, fallait s'y attendre

p2sup(80) =>  9
p2sup(81) =>  9
p2sup(82) => 10
 
Voilà une solution simple .

Ca donne pas la racine ?  
Il voudrait la puissance de deux juste supérieure au nombre entré
 
p2sup(80) => 128  
p2sup(81) => 128  
p2sup(82) => 128  
 
p2sup(127) => 128  
p2sup(128) => 256
 
 
 

 
Euh désolé si mes notations matheuses sont un peu tordues mais "determiner n tel que k n'existe pas avec size<=2^k<2^n, si size est l'entier positif quelconque considéré" signifie que si size=8 alors n=3 soit 2^n=8.

 
Euh le problème alors c'est de déterminer le nombre de décalages à gauche pour arriver à 0..01. En programmeur moyen que je suis, j'implémente ce genre de choses avec une bonne grosse boucle. Donc niveau performance, c'est assez moyen.

 
jusqu'a ce que le bit que tu **sors** a gauche soit egal a 1, ce qui sur un nombre grand, meme dans une boucle, prend moins de temps que de boucler en decalant vers la gauche et en testant si c superieur ou pas

En amateur sous-moyen , j'avais une fois essayé de remplacer des divisions par des décalages, mais ça m'apportait pas de gain du tout en vitesse. J'ai été déçu.
 
Si on divise le nombre par deux, n fois, en comptant le nombre de divisions, et ajoutant un => puiss de deux supérieure (genre division euclidienne).

 
et pis une fois que t'as sorti le bit le plus a gauche, si ce qui reste = 0, alors c que ton nombre de depart est une puissance de 2, donc c fini aussi, na !

Au feeling :
Si tu divises par 16, on peut determiner dans quelle zone se trouve le bit supérieur.
Ensuite y a juste à faire un ET (masquage) avec les 4 patterns commencant par 1000 , 0100, 0010 et 0001. (le nombre de zéro après dépend du résultat de la division par 16. Si c'est 0, y en a pas, si c'est 1, c'est 0000, si c'est 2 c'est 0000 0000, etc)
Le premier resultat qui renvoie autre chose que 0 te donne la position du premier 1

carbon_14 a écrit a écrit : En amateur sous-moyen , j'avais une fois essayé de remplacer des divisions par des décalages, mais ça m'apportait pas de gain du tout en vitesse. J'ai été déçu.   Si on divise le nombre par deux, n fois, en comptant le nombre de divisions, et ajoutant un => puiss de deux supérieure (genre division euclidienne).

 
ce qui equivaut donc a decaler a droite jusqu'a ce que tu obtiennes 0
on y arrive
 
 
algo : avec x un entier positif quelconque
 
int aTester = x;
int tmpTest = x;
int tmpBit;
int resu;
int nbDecalages = 0;
bool estPuisDeux = true;
 
while (tmpTest>0)
{
tmpBit = tmpTest >> 1;
if (tmpBit==1) estPuisDeux = false;
tmpTest >>= 1;
nbDecalages++;
}
 
if (estPuisDeux)  
{
resu = aTester;
}
else
{
resu = 2^(nbDecalages + 1)
}
 
 
edit : mais c sur que ca sera ptet pas plus rapide

Exemple :
 

HappyHarry a écrit a écrit :     ce qui equivaut donc a decaler a droite jusqu'a ce que tu obtiennes 0 on y arrive     algo : avec x un entier positif quelconque   int aTester = x; int tmpTest = x; int tmpBit; int resu; int nbDecalages = 0; bool estPuisDeux = true;   while (tmpTest>0) { tmpBit = tmpTest >> 1; if (tmpBit==1) estPuisDeux = false; tmpTest >>= 1; nbDecalages++; }   if (estPuisDeux)   { resu = aTester; } else { resu = 2^(nbDecalages + 1) }     edit : mais c sur que ca sera ptet pas plus rapide

je préfère ma méthode, y a qu'une division et 3 tests (au pire)

 
Bah là aussi il faut tester les chiffres que tu sors. Car si par hasard ils s'amusent à être tous nuls, eh bien alors il faut retourner le chiffre tel quel. Par ailleurs, afin d'obtenir le nombre de chiffres ainsi giclés, il est de bon ton d'utiliser un truc genre "nb++". Et personne ne me fera croire que INCL a besoin de moins de cycles pour s'exécuter que SHL (ou alors les gens qui font des Pentium sont plutôt nuls et non jamais entendus parler des registres à décalage ce qui m'étonnerait beaucoup). Bref de toute façon, vu le calcul final à effectuer avec ta méthode et comme je suis feignant, je reste persuadé que ma solution est meilleure que la tienne. Mais merci quand même de perdre du temps là dessus.

Pour les paresseux (comme moi )
unsigned long Bit[] = { // puissances de deux, précalculées
       0x1L,        0x2L,        0x4L,        0x8L,
      0x10L,       0x20L,       0x40L,       0x80L,
     0x100L,      0x200L,      0x400L,      0x800L,
    0x1000L,     0x2000L,     0x4000L,     0x8000L,
   0x10000L,    0x20000L,    0x40000L,    0x80000L,
  0x100000L,   0x200000L,   0x400000L,   0x800000L,
 0x1000000L,  0x2000000L,  0x4000000L,  0x8000000L,
0x10000000L, 0x20000000L, 0x40000000L, 0x80000000L};
 
On compare jusqu'à trouver...
 
(Ca me sert à compacter des options d'un prog bit à bit sur un long, je voulais éviter les puissances de 2 dynamiques ).

 
j'ai jamais dit le contraire, j'ai d'ailleurs précisé plus haut que cette methode n'est plus rapide que dans le cas ou tu te rapproches de la capacité max du type utilisé

 
Euh c'est séduisant mais je n'ai rien compris Le 16 de "floor(24/16)", il sort d'où ? Il faut le calculer, non ? Avec une bonne vieille boucle ? En outre, qui me dit que celui qui a codé "floor" n'est pas un immonde amateur et que son truc ne prend pas un quart d'heure à faire son calcul (je suis un peu de mauvaise foi) ? En fait à la base, quand j'ai posé la question, j'entretenais secrètement l'espoir que quelqu'un aurait une solution magique à base de % et & qui tiendrait en une ligne... Là pour le moment si optimisation il y a, c'est assez négligeable. Mais merci beaucoup en tout cas.

exo_ a écrit a écrit :     Euh c'est séduisant mais je n'ai rien compris Le 16 de "floor(24/16)", il sort d'où ? Il faut le calculer, non ? Avec une bonne vieille boucle ? En outre, qui me dit que celui qui a codé "floor" n'est pas un immonde amateur et que son truc ne prend pas un quart d'heure à faire son calcul (je suis un peu de mauvaise foi) ? En fait à la base, quand j'ai posé la question, j'entretenais secrètement l'espoir que quelqu'un aurait une solution magique à base de % et & qui tiendrait en une ligne... Là pour le moment si optimisation il y a, c'est assez négligeable. Mais merci beaucoup en tout cas.

non c'est tout le temps 16
ca te permet d'obtenir dans quelle zone de quatre bits se trouve le 1 que tu cherches. (vu 0F correspond à 1111, FF à 1111 1111, etc)

HappyHarry a écrit a écrit :     j'ai jamais dit le contraire, j'ai d'ailleurs précisé plus haut que cette methode n'est plus rapide que dans le cas ou tu te rapproches de la capacité max du type utilisé

 
Et malheureusement ce n'est pas mon cas... En fait, mon problème à la base, c'est d'implémenter l'algorithme de gestion de la mémoire dit "buddy system" (je précise pour les amateurs de ce genre de saloperies). Or, sous le contexte restreint de mon projet, les allocations sont assez rarement supérieures à 2^16.

autre exemple tout con, pour 78 :
 
floor (78 / 16) = 4
 
donc faut foutre 0000 0000 0000 0000
et tester :
 
1000 0000 0000 0000 0000
0100 0000 0000 0000 0000
0010 0000 0000 0000 0000
sinon c'est
0001 0000 0000 0000 0000
 
3 tests max
 
et si la division par 16 tombe juste en plus t'as directement la position du 1.

 
g rien dit alors

 
   
 
si seulement on bidouillait en binaire pour le web, le forum marcherait presque bien  

HappyHarry a écrit a écrit :           si seulement on bidouillait en binaire pour le web, le forum marcherait presque bien

me suis planté c'est pas 0000 0000 0000 0000 c'est 0000 0000 0000

 
C'est mignon tout plein. Reste à savoir si floor est un truc rapide ou pas. Je vais essayer de faire un test de perf.

joce a écrit a écrit :  me suis planté c'est pas 0000 0000 0000 0000 c'est 0000 0000 0000

 
d'ou le 'presque'  

faut faire :
 
 
depart = (floor (size/16)) * 16;
 
décaler depart de 4 bits vers la gauche, et commencer les tests

Pour moi ca c'est suffisant :