J'essaie d'optimiser quelques routines d'emballage et de déballage des bits. Pour effectuer l'emballage, je dois calculer le nombre de bits nécessaires pour stocker des valeurs entières. Voici le code actuel.
if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
++r;
n >>= 1;
}
return r;
6 Réponses :
Non versement, utilisez l'opcode de bit-Scan-inverse disponible sur la plupart des architectures modernes. Il est exposé comme un intrinsèque en vue C ++.
Portablement, le code dans la question n'a pas besoin de la manipulation des cas de bord. Pourquoi avez-vous besoin d'un bit pour stocker 0? En tout cas, je vais ignorer les bords du problème. Les tripes peuvent être effectuées efficacement donc:
Vous devriez vérifier l'heure d'exécution pour comprendre la granularité, mais je suppose que cela fait 4 bits à la fois, puis revenir à un bit à un moment le rendrait plus rapide. Les opérations de journalisation seraient probablement plus lentes que les opérations logiques / bits.
if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
r+=4;
n >>= 4; }
while (n) {
r++;
n >>= 1; }
return r;
Ce que vous essayez de faire est de trouver le bit le plus significatif. Certaines architectures ont une instruction spéciale à cet effet. Pour ceux qui ne le font pas, utilisez une méthode de la recherche de table.
Créer une table de 256 entrées, dans laquelle chaque élément identifie la plupart des bits supérieurs.
Soit une boucle à travers chaque octet dans le numéro ou utilisez quelques déclarations IF-IF pour casser pour trouver l'octet non nul le plus zéro.
Je vais vous laisser prendre le reste d'ici.
Sur un processeur rapide avec RAM lente (un PC!) Cela pourrait être plus lent que de simplement faire une boucle. La boucle pour la boucle sera systématiquement dans la région de cent cycles d'horloge, tandis qu'une recherche de mémoire pourrait prendre 10 subshants de millisecondes si les données doivent être pagées à partir du disque (puis vous perturbez le cache donc il y a aussi un coup d'effet ).
Faites une recherche binaire au lieu d'une recherche linéaire.
#ifdef ARCHITECTURE_WITH_BSR asm // ... #else // Use the approach shown above #endif
number_of_bits = log2(integer_number) rounded to the higher integer.
@Matteo, bien sûr, il souhaite optimiser le code, mais ces optimisations de Nitty-Picky conduiront à un code de désordre. Prendre log2 est une approche élégante, propre, lisible et maintenable.
@MAHES: La question indique spécifiquement «quel est le moyen le plus rapide» pour les routines d'emballage de bits / de déballage, qui sont probablement appelées dans des boucles intérieures, où les performances sont critiques. Au lieu d'une poignée d'instructions de montage / bitwise, cette solution consiste à convertir un entier en inteer à un point flottant (qui est lent), une sorte de recherche de table (qui peut déclencher un calcul de cache Miss) / calcul de la série tronquée (pour le journal) et un Conversion retour à int (encore une fois, assez lent). Points malus Si c'est une plate-forme intégrée sans quincaillerie FP, chaque opération de FP doit donc être imitée dans des logiciels.
Vous souhaitez déterminer la base de journal entier 2 d'un nombre (le L = le bit le plus élevé). La page "Bit Twidding Hacks" de Sean Anderson contient plusieurs méthodes allant des bits de comptage évidents dans une boucle aux versions qui utilisent la recherche de table. Notez que la plupart des méthodes démontrées devront être modifiées un peu pour fonctionner avec des INT 64 bits si ce type de portabilité est important pour vous.
Assurez-vous simplement que tout déplacement que vous utilisez pour déterminer le jeu de bits le plus élevé doit être effectué 'sur une version non signée du numéro, car une implémentation de compilateur peut ou non signifier étendre le >> opération sur une valeur signée.
Je n'ai même pas réalisé ce que j'essayais de faire était de calculer la base de journal 2. Logarithmes d'un peu sauté en classe de mathématiques. Ce site avait des trucs utiles. Merci
J'espère que vous n'essayez pas de compresser des données et de préfixer chaque valeur avec le nombre de bits dans la valeur.
Lorsque vous écrivez "32", je présume que tu veux dire taille de (int) * char_bit. Voulez-vous que votre code fonctionne où Tailleof (int) == 8?
Si vous utilisez >>, vous voulez vraiment que n non signé.
@Skizz: Bitpacking est une technique très rapide et efficace ... Je ne sais pas exactement ce que c'est exactement dans sa question, vous pensez qu'il peut être préfixer chaque valeur avec le nombre de bits.
@WizardOdds: Eh bien, je ne peux penser à aucune raison pour que vous souhaitiez calculer le nombre de bits nécessite de contenir un entier. Et même s'il y avait une bonne raison de le faire, vous devez toujours enregistrer quelque part le nombre de bits utilisés (comment d'autre pourriez-vous décoder). Peut-être que c'est de réduire la bande passante sur une liaison lente et le nombre de bits est une limite supérieure pour un bloc de données. Mais alors il y a beaucoup de meilleures façons de faire cela. Je ne sais pas, essayant juste de deviner quelle est la plus grande image parce qu'il y a une chance que l'Op aboie le mauvais arbre.
@Skizz: Ceci est utilisé avec une partie d'une en-tête sur une table. Nous utilisons cela avec la valeur minimale et max pour déterminer le nombre de bits pour l'emballage et est calculé à l'aide de Min et Max enregistré dans l'en-tête pour déballage.
@Matt: Vous stockez donc une séquence de valeurs comme:
(valeur - min) & (number_of_bits (max-min)) et stockage min et bits par valeur dans une en-tête? Donc, vous essayez de comprimer un éventail d'entiers? Il y a beaucoup d'algorithmes là-bas qui feront un meilleur travail de compression que cela.@Skizz: Cela fait partie d'un grand système de base de données. Il stocke plus que des entiers, il stocke également des flotteurs et des cordes. Plusieurs tables, et il doit se comprimer en tant que petite mémoire que possible. J'essaie d'optimiser le système et de le remplacer n'est pas faisable.
@Matt: Peu importe si elles sont des Ints, des flotteurs, des cordes ou peu importe, ils sont juste des octets. Créez une structure contenant toutes les données que vous souhaitez compresser (une ligne d'une table dans la base de données indique), puis utilisez quelque chose comme zlib ( ZLIB.NET ) Pour compresser une instance de la structure:
déflate (& instance, Taille de l'instance) où l'instance est la structure contenant toutes les données. Vous aurez une meilleure meilleure compression en utilisant quelque chose comme Zlib, et vous avez beaucoup testé.@Skizz: Cela ne concerne pas la compression, il s'agit de calculer le nombre de bits pour stocker un nombre. Et si je veux générer du code pour les structures emballées de bits, ou comme cela a été mentionné, calculez le journal 2 d'un numéro?
@Matt: Oui, la question concerne les bits de comptage, c'est pourquoi ce sont des commentaires plutôt que des réponses. Parfois, on obtient des détails obsessionnels sur la mise en œuvre lorsqu'il s'agit de la mise en œuvre qui est faute. Ici, je me suis demandé si l'objectif était de faire de la compression, dans ce cas, de compter les bits est très inefficace (ratio de compression médiocre). Il est inhabituel que les algorithmes ont besoin de savoir que le nombre de bits. C ++ n'autorise pas les déclarations de champ de bits dynamiques, les structures emballées de bits nécessiteraient des métadonnées supplémentaires pour décrire la mise en page, en ajoutant une complexité. Compter les bits ne vous donnerait qu'une approximation du log2.
@Skizz: Il s'agit d'un grand système, à quelques mois de l'expédition. L'ajout de quelque chose comme Zlib serait non seulement en conflit avec la manière dont le système de base de données stocke et récupère des données, il pourrait également nécessairement avoir besoin de retestation massive. Je pense toujours que cela est un moyen viable de stocker des données car tout ce dont nous avons besoin est quelques changements de bits pour obtenir les données et nous pouvons garder le tout en mémoire. En bref, je ne change pas ce qui n'est pas cassé. Aller en arrière sur cela ne provoque aucune petite quantité de stress sur quelque chose qui ne devait pas.
@Matt: Si votre implémentation répond à vos exigences, vous n'avez rien à craindre. Je ne voulais pas causer de stress!
Voir aussi Stackoverflow.com/questions/680002/...