De nombreux "grands maîtres", dont Brian Kernighan lui-même ont écrit de nombreux algorithmes utilitaires effectuant des travaux sur les champs de bits que sont nos mots mémoires.
On trouvera donc dans l'article cité, qui des comptage de bit (à 1 ou 0), des tests de parités parallélisables, des rotations de bits, des modulos, des log base 2 (et donc des log base n). L'article prévient en introduction que les problèmes de cache, bande passante mémoire doivent être pris en compte dans l'utilisation de l'algorithme sur l'architecture libre.
Un bien beau texte.
NdM : les extraits de code sont du domaine public d'après l'introduction du document.
Aller plus loin
- Bit Twiddling Hacks (38 clics)
# bonheur
Posté par Troy McClure (site web personnel) . Évalué à 10.
Les big-endian procurent encore plus de plaisir !
[^] # Re: bonheur
Posté par Ramón Perez (site web personnel) . Évalué à 7.
Attendez, je retrouve la photo.
[^] # Re: bonheur
Posté par dco . Évalué à 1.
merci google image
[^] # Re: bonheur
Posté par Croconux . Évalué à 1.
- La batte de baseball (big endian), plus large au bout qu'à la base
- La tour Eiffel (little endian), plus étroite au bout qu'à la base
- Le champignon (bon, là il n'y a pas d'équivalent informatique)
Après pour ce qui est de savoir s'il y a une forme "optimale"...
[^] # Re: bonheur
Posté par viridis (site web personnel) . Évalué à 10.
[^] # Re: bonheur
Posté par Francois Revol (site web personnel) . Évalué à 2.
http://www.idiap.ch/~formaz/doc/glibdocs/glib-byte-order-mac(...)
[^] # Re: bonheur
Posté par Victor STINNER (site web personnel) . Évalué à 2.
http://fr.wikipedia.org/wiki/Endianess
Haypo
[^] # Re: bonheur
Posté par Victor STINNER (site web personnel) . Évalué à 3.
http://fr.wikipedia.org/wiki/RADIX-50
(base 40 tant qu'à faire hein, pour utiliser du modulo & co)
Tiens, au passage, un truc qui m'a bien fait marrer :
http://fr.wikipedia.org/wiki/UTF-EBCDIC
UTF-8, vous connaissez, mais EBCDIC ? « L'Extended Binary Coded Decimal Interchange Code (EBCDIC) est un mode de codage des caractères sur 8 bits créé par IBM à l'époque des cartes perforées » UTF-EBCDIC c'est donc retour vers le futur (Unicode sur carte perforée ? non mais presque).
Haypo qui parle de choses qu'il n'a jamais connues
# Merci
Posté par jjl (site web personnel) . Évalué à 9.
Un gros problème quand on travaille dans l'industrie (au sens general) c'est qu'on a pas le temps de chercher d'aussi beaux algos. AMHA on perd du même coup un interet majeur de notre travail :(
# la quintessence ca n'a pas de sense
Posté par mickael rameau . Évalué à -10.
Ouhaa, le typade est plus rapide ici que sous wordpress.
Je me marre, le gars de lafraise fait du zele sur ces 2 millions euros
Il aurait pas du vendre non il aurait gagner plus sur 10 ans non ?
il aurait du ce faire acheter chez google LOL
pff la vie tranquille, une maison n'importe na oke tous çà.
des enfants en plus
moi si ma mashup grimpe en bourse je vais direct vivre a moutain view
ou à SF ou a NY.
pour dire y a des paysans parmit les geek mais qui sait il rebondira
peut être
a oui j'aime pas trop les t-shirt c'est moche
le lapin de la ratp qui ce coince les doigts dans la porte ...
revenons a mes moutons,
j'ai voulu essayer le code j'ai ajouter un fonction main()
est les includes
#include <stdio.h>
#include <stdlib.h>
int main()
static const char LogTable256[] =
{
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};
gcc algo3.c -o algo3
/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../crt1.o: dans la fonction « _start »:
: référence indéfinie vers « main »
collect2: ld a retourné 1 code d'état d'exécution
comme je trouve pas de réponse pértinante dans google PR
si vous s'avez d'ou viens l'erreur, merci.
ps: les fautes ... j'accepte toute donnation de beschrelle, larousse,
[^] # Re: la quintessence ca n'a pas de sense
Posté par mickael rameau . Évalué à -10.
et pourquoi mon commentaire apparait fermé avec un +
[^] # Re: la quintessence ca n'a pas de sense
Posté par Barnabé . Évalué à 4.
Essaie avec des accolades....
int main(int argc, char **argv)
{
static const char LogTable256[] =
{
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};
/* .... */
return 0;
}
[^] # Re: la quintessence ca n'a pas de sense
Posté par ColonelMoutarde . Évalué à 5.
Pour les fautes, je crois que t'es irrécupérable. Quand au fait que ton commentaire apparaisse fermé avec un [+], c'est qu'il a été modéré négativement par les autres personnes, qui l'ont trouvé "inintéressant". Et franchement, je crois qu'ils n'ont pas vraiment tort.
[^] # Re: la quintessence ca n'a pas de sense
Posté par fork_bomb . Évalué à 10.
# Encore un coup des brevets
Posté par ecyrbe . Évalué à 10.
Il est dit que :
Unfortunately, this method has been patented in the USA on June 6, 2000 by Vladimir Yu Volkonsky and assigned to Sun Microsystems
Heureusement peu après des liens sont donnés pour prouver que le brevet est invalide!
C'est dingue de breveter des techniques pareilles... je comprendrais jamais... heureusement que D.Knuth a ecrit ses bouquins sur l'art de la programmation, sinon on pourrai jamais utiliser de maths en informatique!
# Bravo mais..
Posté par dbaelde (site web personnel) . Évalué à 3.
Je me demande quand même combien de gens ont besoin d'écrire des algos bit à bit en C.. j'ai passé un certain nombre d'années à coder en C, ça m'est arrivé très rarement. Il y a des gens qui ne peuvent pas utiliser la libm pour le log ou la valeur absolue ?
[^] # Re: Bravo mais..
Posté par lasher . Évalué à 4.
Sinon, lorsqu'on entre en phase d'optimisation (et donc que le logiciel tourne déjà bien), et qu'une boucle doit être optimisée, parfois avoir recours à des opérations sur les bits peut accélérer les choses - mais j'ai l'impression que c'est très dépendant de l'architecture cible.
[^] # Re: Bravo mais..
Posté par neologix . Évalué à 10.
Je cite la faq sur le langage C:
De façon plus générale, je ne pense pas que ce osit une bonne idée de beaucoup bosser avec les bits:
exemple, la divison par 2, que certains conseillent d'effectuer par un décalage.
Le problème, c'est que si ton nombre est signé, et que tu fais un décalage à droite, bah le comportement est indéfini (décalage logique ou arithmétique?).
C'est une grosse source de bugs.
Tous ça, c'était surtout utile avant, quand les compilos étaient cons comme des balais. Aujourd'hui, ils optimisent tellement le code qu'il vaut mieux les laisser faire.
Enfin, un argument sensé que j'ai lu je ne sais plus où:
avec des "hacks" comme ça, tu gagnes un peu, mais ce peu va se réduire avec les années (progrès du compilo/métériel). Par contre, tu perds en lisibilité, et pour toujours...
Attention, je ne dis pas que les manipulations de bits (en info :-) sont inutiles, je dis qu'il faut faire attention.
[^] # Re: Bravo mais..
Posté par lasher . Évalué à 3.
Ben tout dépend de quel compilateur on parle. :-)
Au risque de me répéter vis à vis de ce que j'ai pu dire dans d'autres réactions, gcc n'est pas (encore) le plus optimisant des compilos, et on peut clairement faire mieux à la main, si on a le temps et la volonté d'apprendre l'assembleur de la machine cible. Alors que pour faire mieux à la main que certains autres compilateurs, il faut se lever très tôt.
« Enfin, un argument sensé que j'ai lu je ne sais plus où:
avec des "hacks" comme ça, tu gagnes un peu, mais ce peu va se réduire avec les années (progrès du compilo/métériel). Par contre, tu perds en lisibilité, et pour toujours... »
C'est vrai. C'est pour ça que les deux grandes règles de l'optimisation sont :
1°) N'optimise pas.
2°) (pour experts seulement) N'optimise pas encore.
L'optimisation vient en toute fin de développement, lorsque ton code fonctionne déjà bien, sans bug, etc.
Les manipulations de bits, en règle générale, sont tellement dépendants de la machine qu'il est sans doute plus « simple » si on connaît l'architecture cible d'éditer le code assembleur et de les faire soit-même (ou bien d'insérer le code ASM dans le source C, mais non seulement c'est crade, mais en plus les options d'optimisation sont désactivées automatiquement dans certains compilateurs quand ils détectent ce genre de magouille) :-)
[^] # Re: Bravo mais..
Posté par fmaz fmaz . Évalué à 3.
Faire un tri à bulles parce que c'est lisible et qu'il ne faut pas optimiser et que le compilo fera le boulot, ce n'est pas demain que ça fonctionnera.
Un certain nombre de personnes passent leur temps à ce genre d'optimisation pour que kde ou gnome fonctionnent plus vite.
Maintenant, réécrire un code C en assembleur pour utiliser des trucs, je suis d'accord qu'il faut éviter et repousser ça à la fin.
Frédéric
[^] # Re: Bravo mais..
Posté par lasher . Évalué à 3.
L'optimisation intervient tout à la fin, quand tu as déjà fait les bons choix pour ton logiciel (par exemple en utilisant un tri rapide ou un tri fusion pour trier tes éléments). Choisir un bon tri n'est pas faire de l'optimisation, c'est faire de bons choix de conception.
Ce que j'appelle « optimisation » pourrait sans doute plutôt être appelée « micro-optimisation » : on se rend compte qu'on passe 90% du temps dans une boucle, alors on essaie de voir si on ne pourrait pas améliorer la façon dont elle s'exécute. Maintenant, si ta boucle est en réalité un tri à bulle, tu auras beau optimiser et gagner 10 ou 20 % en perfs, tu seras toujours plusieurs ordres de grandeur derrière un tri rapide ou fusion.
C'est pour ça que les (micro-)optimisations viennent en fin de développement : on a déjà réglé le plus gros des détails, et on a déjà une application raisonnablement rapide.
Donc, de mon point de vue, optimiser un tri à bulles ou un tri rapide, c'est *toujours* de l'optimisation. C'est juste que dans un cas, tu optimises un truc pas très efficace.
[^] # Re: Bravo mais..
Posté par Thomas Douillard . Évalué à 4.
Pour généraliser un peu :
Ingrédients : -> un problème à résoudre
-> des solutions
-> un (éventuellement des, mais c'est tout de suite plus compliqué) critères pour juger une solution
Notre problème : Avoir un programme qui fait ce qu'on veut (autrement dit correct)
Nos solutions : tous les programmes corrects possibles.
Notre critère : la minimisation du temps de calcul.
"l'optimisation" telle que tu l'entends peut se voir dans ce cadre comme de la "recherche locale" : on part d'une solution existante et on itère de petits changements sur cette solutions pour minimiser le temps de calcul. Le risque de ce genre d'optimisation est de tomber sur un "optimum local" qui ne soit bien moins bien que l'optimum global (globalement on changera pas grand chose à l'algo en optimisant au niveau assembleur).
Une optimisation à un niveau plus global, tu vas considérer de plus gros changements dans le code (considérer le problème de manière plus abstraite, découper en des tâches, choisir l'algorithme connu le plus efficace pour résoudre les différentes tâches, etc.). C'est plus difficile de faire de l'optim globale automatiquement que de l'optim locale.
Et ce cadre s'applique aussi bien à l'optimisation du code qu'a l'optimisation de pleins d'autres objets, c'est beau non ?
[^] # Re: Bravo mais..
Posté par neologix . Évalué à 4.
le meilleur cours en ligne que je connais (et en plus il est en français):
http://www-clips.imag.fr/commun/bernard.cassagne/Introductio(...)
la FAQ Usenet, une vraie mine d'informations:
http://c-faq.com/
guide (pas) superflu du langage C:
http://www.laas.fr/~matthieu/cours/c-superflu/
Pour des débutants (et même les autres) c'est vraiment génial.
[^] # Re: Bravo mais..
Posté par Krunch (site web personnel) . Évalué à 2.
http://www.byte.com/abrash/
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Bravo mais..
Posté par jjl (site web personnel) . Évalué à 10.
Tous les gens qui ont vraiment besoin d'optimiser les perfs et l'occupation mémoire.
Alors bien sur quand tu bosse avec un x86, plein de mémoire et un gros os, tu t'en fiche un peu. Mais si tu fait de l'embarqué tu n'a pas forcement tout cela, pas de place pour des libs, un os minimalistique et très peu de mémoire.
[my life]
Depuis peu je suis passé d'applis en C++/Python sous Solaris à du C sur DSP. Ce sont deux mondes très différents qui demandent des manières de penser et de coder qui changent du tout au tout.
Quelques chiffres pour fixer les idées :
RAM : 4Go --> 1Mo (code + données)
Vitesse : 2x2.7 GHz --> 720 MHz
Dans ces cas la, loger plusieurs valeurs par octet ou gratter quelques cycles deviens vraiment nécessaire.
[^] # Re: Bravo
Posté par Jimmy . Évalué à 5.
J'ai parfois l'impression que tout le monde ici code des bases de données relationelles en J2EE sur des serveurs virtualisés ...
Mais l'informatique embarquée est un des domaines où notre pingouin préféré a une très forte progression, et bouscule pas mal le marché établi.
Pourtant dans ce domaine, malgré la Loi de Moore, on continue à avoir des besoins de compacité, de faible consommation (donc de faible fréquence, et faible quantité de mémoire) incompatibles avec la "grosse" informatique. Mais avec des besoins de performance quand même importants ! Par exemple, tous les téléphones mobiles modernes sont des systèmes multiprocesseurs, avec 2 à 4 processeurs RISC et DSP ...
On se tourne alors vers des architectures spécifques, comme les DSP, qui présentent un rapport MIPS/Watt très intéressant.
Je rajouterais le chiffre suivant :
RAM : 4Go --> 1Mo (code + données)
Vitesse : 2x2.7 GHz --> 720 MHz
Consommation : 90W --> 0.9W
Mais indépendamment des questions de ressources plus spartiates en embarqué, il y a un domaine où on ne coupe pas à la gestion des bits un par un : c'est quand on est en contact direct avec le hardware. Pour écrire un bit précis dans un registre (sans faire un ràz des autres bits), et même souvent faire une opération read-test-modify-write qu'on aimerait bien non-interruptible, c'est tout simplement indispensable.
Une méthode pour cela est le "champ de bits", en fait une union entre une structure et la valeur globale du registre. On peut ainsi modifier indépendamment les champs de la structure, et lire/écrire la valeur complète dans le registre. Par contre, si on veut être portable il faut le définir deux fois : une fois en big endian, une fois en little endian.
Exemple approximatif en Little Endian :
Ensuite, il y a aussi des parties particulières du code, comme les routines d'interruption ou le bootloader, pour lesquelles les contraintes sont telles qu'on échappe rarement à l'écriture de quelques instructions en assembleur.
[^] # Re: Bravo
Posté par _alex . Évalué à 2.
Les fonctions les plus solicitées de mise à jour de l'écran, des codec (et autre) sont optimisées en assembleur. La version C est en générale aussi présente : vu que le projet fonctionne sur différente architecture, ca facilite le portage.
Ces appareils tournent souvent avec ~8Mo de RAM, et à ~80Mhz en vitesse de pointe, moins si possible pour économiser les batteries.
Et là, point de malloc ou allocation de mémoire dynamique.
[^] # Re: Bravo
Posté par gpe . Évalué à 1.
Par exemple on fait tourner une stack GSM/GPRS/EDGE plus pas mal de chose autour sur un proc à 26MHz + un DSP à 78MHz et 512Ko de Ram. Et je peux te dire que toutes les optims sont les bien venues, même si il faut bien avouer que les compilos ARM (ADS et RVCT) sont particulièrement efficaces. Ils utilisent énormément les manipulations de bits. On utilise aussi GCC et il faut bien avouer que sur ARM il est à la ramasse en terme d'optim. Mais ça ne fait pas tout! Il ne gère pas par exemple la mise du code et/ou données en mémoire rapide, ni l'éclatement d'une boucle pour en accélérer le déroulement, ni le retournement d'une boucle (décrémenter plutôt qu'incrémenter). Donc oui bien souvent on peut faire confiance au compilo mais il ne fait pas tout non plus!
[^] # Re: Bravo mais..
Posté par M . Évalué à 6.
[^] # Re: Bravo mais..
Posté par Ontologia (site web personnel) . Évalué à 4.
Va voir chez Gcu...
http://gcu.info
D'aileurs en passant, merci à Klyr à qui j'ai honteusement piqué l'info...
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
Ce n'est pas si fréquent mais ça arrive: un example ou ce serait utile:
http://primates.ximian.com/~federico/news-2005-10.html#31
J'ai essayé de le faire en faisant des manipulations de bit, mais je n'ai réussi a optimiser qu'en utilisant une instruction assembleur qui compte le nombre de bit mis a 1 dans un mot, ce qui n'existe pas sur x86, forcément ça limite beaucoup l'interet de "l'optimisation"..
[^] # Re: Bravo mais..
Posté par thedidouille . Évalué à 1.
quelle archi dispose d'une instruction permettant de compter les bits ?
Merci!
[^] # Re: Bravo mais..
Posté par reno . Évalué à 3.
si x est un octet pour 0<= x < 0xfe
on peut calculer les valeurs de la table tres rapidement par count_leading_1(0x80 | x), ce qui doit se traduire sur les archis ayant count_leading_1 par deux/trois instructions assembleurs s'exécutant chacune en un cycle (difficile de faire mieux!).
Le probleme c'est pour associer 1 a 0xfe et 0xff.
En théorie c'est simple:
(x >= 0xfe) || count_leading_1(0x80 | x)
Mais le || par court-circuit n'est pas forcément efficace, c'est la ou je sèche pour trouver une formule efficace de manière "portable" (enfin efficace pour les archi qui ont count_leading_1, je ne sais pas si elles ont toutes CMOV)..
J'avais envisagé aussi count_leading_1(0x81 | x) %7 mais le modulo ce n'est pas efficace non plus.
count-leading-1 (ou count-leading-0, c'est la même chose a un non-binaire pres) existe sur PPC, ARMv5+, MIPS32, Alpha avec CIX, mais pas les x86 mais bon "x86 sucks" comme d'habitude :-(
Voila, c'est de mémoire, je ne garanti pas qu'il n'y ait pas d'erreur..
Tu peux m'envoyer un mail si tu veux discuter du sujet.
[^] # Re: Bravo mais..
Posté par ribwund . Évalué à 2.
C'est posix et ca donne le premier bit a 1.
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
J'ai fait un google sur ffs.c et je suis tombé sur:
>>
int ffs(mask)
register int mask;
{
register int bit;
if (mask == 0)
return(0);
for (bit = 1; !(mask & 1); bit++)
mask >>= 1;
return(bit);
}
<<
Et je ne pense pas qu'un compilateur soit capable de remplacer ce code la, par l'instruction assembleur correspondante, pourtant la il s'agit de darwin qui tournait a l'origine sur PPC qui possède cette instruction (enfin l'équivalent qui compte le nombre de 0)..
Quelqu'un a un PPC pour vérifier si ce code est bien compilé en assembleur par un not suivi de cntlzw?
Si oui alors les compilateurs sont vraiment plus fort que je ne le pensais..
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
count_leading_1 te donne le nombre de 1 consécutif du coté poids fort, pas l'index du premier bit a 1 en partant du coté poids faible comme ffs..
[^] # Re: Bravo mais..
Posté par ribwund . Évalué à 3.
— Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
et sinon dans /usr/src/linux/include/asm-i386/bitops.h, en 3 instructions assembleur:
/**
* fls - find last bit set
* @x: the word to search
*
* This is defined the same way as ffs.
*/
[1] http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#Other-(...)
[^] # Re: Bravo mais..
Posté par thedidouille . Évalué à 1.
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
Je vais tester ça.
[^] # Re: Bravo mais..
Posté par thedidouille . Évalué à 1.
c'est vrai que "count_leading_1" est une instruction vraiment utile (plus qu'un compteur de bits). je pensais que pour tout ce qui était manipulations de bits, l'architecture x86 était la plus aboutie.
Si j'ai un jour une question de ce genre, je sais a qui la posée.
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
Euh, il ne faudrait pas me prendre pour un gourou, hein!
Il me *semble* que le modulo ce n'est pas efficace (pas d'instruction pour ça directement) et faire mieux que la fonction de gtk n'est pas si facile, c'est quand même juste un load, la mémoire est lente certes, mais ça ne fait quand même pas beaucoup de cycle..
> je pensais que pour tout ce qui était manipulations de bits, l'architecture x86 était la plus aboutie.
Ah? Ca n'est pas ma perception..
En tout cas, je ne l'ai pas trouvé 'count-leading-1' (ou 0) sur x86, ni sur SPARC d'ailleurs (pour ne pas taper que sur x86) et ni sur IA64 (Intel ne m'aide décidement pas).
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
Donc la formule peut valoir le cout sur x86, chouette!
Reste a trouver une maniere efficace de traiter le cas particulier de 0xfe, 0xff, quelqu'un a une idée?
(x >= 0xfe) || (__builtin_clz(~(0xffffff80 | x)) - 24)
ou
(__builtin_clz(~(0xffffff81 | x)) - 24) % 7
ou ...
[^] # Re: Bravo mais..
Posté par reno . Évalué à 2.
(x < 128) || (x >= 0xfe) || (__builtin_clz(~x) - 24)
ou
(((x+2)&0xff) < 130) + (__builtin_clz(0xfe & ~x) & 7)
Et pas mal de variantes possibles..
[^] # Re: Bravo mais..
Posté par benoar . Évalué à 2.
!(x ^ 0xff) || !((x ^ 0xff) - 1)
non ?
Sinon, pourquoi est-ce que la comparaison ne serait "pas efficace" ?
[^] # Re: Bravo mais..
Posté par ribwund . Évalué à 3.
(dans lib/hweight.c)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.