std :: bit_width trouve des bits minimaux requis pour représenter un numéro intégral x comme 1 + plancher (log (x))
Pourquoi std :: bit_width renvoie-t-il 0 pour la valeur 0? Ne devrait-il pas revenir 1, car le nombre de bits requis pour représenter 0 est 1?
De plus, je pense que le 1 dans la formule est un décalage.
3 Réponses :
Il y a un peu d'historique à bit_width .
La fonction qui deviendrait finalement connue sous le nom de bit_width a commencé la vie comme log2 , dans le cadre d'une proposition ajout de fonctions de puissance de puissance entière . log2 a été spécifié pour produire UB lorsqu'il est passé 0.
Parce que c'est ainsi que fonctionnent les logarithmes.
Mais alors, les choses ont changé. La fonction est devenue plus tard log2p1 , et Pour des raisons qui ne sont pas spécifiées, on a donné un contrat plus large (" Contrat large "dans le langage C ++ signifie que plus de choses sont considérées comme une entrée valide). Plus précisément, 0 est une entrée valide et donne la valeur de 0.
qui est pas comment fonctionnent les logarithmes, mais peu importe.
Alors que C ++ 20 a approché la normalisation, A Le conflit de nom a été découvert (PDF) . Le nom log2p1 correspond au nom d'un algorithme IEEE-754, mais c'est radicalement différent. De plus, les fonctions dans d'autres langues avec des entrées et des résultats similaires utilisent un nom comme bit_length . Donc, c'est renommée bit_width .
Et comme il ne fait plus semblant de faire un logarithme, le comportement à 0 peut être ce que nous voulons.
En effet, la fonction Python int.bit_length a exactement le même comportement . Les zéros de premier plan ne sont pas considérés comme une partie de la longueur du bit, et comme une valeur de 0 contient tous les zéros leader ...
Très mineur quitte, mais je ne pense pas qu'il soit exact de dire "UB lorsqu'il est passé 0 ... parce que c'est ainsi que fonctionnent les logarithmes". UB signifie "peut faire littéralement n'importe quoi, y compris avoir des effets en dehors de la valeur de retour de cette fonction". En particulier, le comportement de la nouvelle spécification est 100% conforme à l'ancien, car "Retour 0" est une implémentation parfaitement valide d'UB.
@PSMears: " y compris avoir des effets en dehors de la valeur de retour de cette fonction " C'est également ce qui se passe lorsque vous prenez le logarithme de 0. C'est une chose que vous ne pouvez pas faire, et si vous le faites, alors vos mathématiques sont cassées et cesse d'être des mathématiques réelles.
Il est parfaitement valable (et utile) en mathématiques à étendre la ligne numérique réelle pour inclure plus / moins / moins infinité, et définir le log 0 pour être moins l'infini. Ou pour traiter le journal comme un fonction partielle sur les réels. Cette réponse dit actuellement "c'est pas comment fonctionnent les logarithmes" sur un comportement 100% conforme à la partie que vous décrivez comme "que est comment fonctionnent les logarithmes", qui semble Un peu incohérent :)
@psmears alors qu'est-ce que Tan 90
La fonction anciennement connue sous le nom de log2p1 fonctionne en fait exactement comme un logarithme; Le problème est que la formule qu'il évalue n'est pas plancher (log (n) + 1) mais ceil (log (n + 1)) . Pourquoi le comité ne l'a pas décrit en utilisant la deuxième formule, qui fonctionne pour tous les n , mais a plutôt utilisé le premier qui a une discontinuité maladroite à n = 0 et a donc besoin de besoin Pour être décrit plus verbeux, c'est la supposition de quelqu'un (c'est le comité standard C ++ dont nous parlons, après tout).
Parce que mathématiquement, cela a du sens:
bit_width(x) = log2(round_up_to_nearest_integer_power_of_2(x + 1))
bit_width(0) = log2(round_up_to_nearest_integer_power_of_2(0 + 1))
= log2(1)
= 0
élaborer ce qui a été dit dans les commentaires:
Supposons "la largeur du bit" signifie "le moins de bits requis pour stocker le numéro (entier non négatif)". Intuitivement, nous avons besoin au moins log2 (n) des bits arrondis, il s'agit donc d'une formule proche de ceil (log2 (n)) , donc 255 nécessiterait ceil (log2 (255)) = ceil (7.99 ..) = 8 bits, mais cela ne fonctionne pas pour les pouvoirs de 2, nous pouvons donc ajouter un facteur de fudge de 1 à n Pour obtenir ceil (log2 (n + 1)) . Cela se trouve être mathématiquement équivalent à 1 + plancher (log2 (n)) pour le positif n, mais log2 (0) n'est pas défini ou défini comme quelque chose d'utile comme l'infini négatif dans la version du sol.
Si nous utilisons la formule de plafond pour 0, nous obtenons le résultat. Vous pouvez également voir que je n'ai pas écrit les zéros de premier plan, et comme le souligne Nicol Bolas, 0 est tous les principaux zéros.
| n | bin (n) | bit_width (n) |
|---|---|---|
| 8 | 1000 | 4 |
| 7 | 111 | 3 |
| 6 | 110 | 3 |
| 5 | 101 | 3 |
| 4 | 100 | 3 |
| 3 | 11 | 2 |
| 2 | 10 | 2 |
| 1 | 1 | 1 |
| 0 | 0 |
La norme spécifie ce comportement explicitement, mais ne donne aucune motivation pour cela.
Pourquoi devrait-il retourner 1? Si vous voulez contenir zéro pommes, vous avez besoin de zéro paniers, non? Ainsi, par exemple, si vous deviez stocker les données en longueur et un pointeur vers un tampon de longueur variable, vous n'auriez même pas à utiliser de tampon pour représenter zéro parce que vous auriez une longueur de zéro pour commencer.
Il pourrait s'agir de correspondre au comportement des instructions disponibles sur les processeurs communs. Par exemple, avec ce comportement, il peut être implémenté avec x86
lzcntet un soustraire, sans branches.Je pense que nous avons besoin au moins d'un chiffre pour représenter le nombre 0. Si nous devions décrire l'absence de nombre, je pense que cela nécessiterait 0 longueur.
Une interprétation est qu'elle donne le nombre de bits dont vous avez besoin pour stocker une valeur arbitraire entre 0 et X inclusive. Lorsque x est 0, votre valeur sera toujours 0 et vous n'avez pas du tout à la stocker, vous n'avez donc pas besoin de bits.
Il est également logique d'un autre point de vue: il renvoie la position du 1 bits la plus élevée de la droite, en commençant par 1, donc 0 indiquerait qu'il n'y ait pas du tout 1 bits. Ou, d'un autre point de vue: 2 ^ 0 = 1, donc un nombre de 0 bits peut représenter exactement 1 état: zéro. Par conséquent, zéro bits suffisent pour représenter le nombre zéro.
@RoHitt: Oui, vous avez besoin de la longueur zéro, mais ce n'est pas différent d'avoir à stocker la longueur ou à connaître la longueur maximale possible à l'avance dans les deux cas. Si vous souhaitez représenter le numéro 5, vous avez besoin de 3 bits, mais vous devez en outre vous souvenir d'une manière ou d'une autre que vous avez besoin de 3 bits, sinon vous ne pouviez pas différencier le numéro 5 d'un nombre plus grand, y compris plus de bits lorsqu'ils viennent dans un flux de bits. Et avec zéro, ce n'est pas différent, vous avez besoin de 0 bits pour le stocker, mais vous devez toujours stocker ou vous souvenir d'une manière ou d'une autre combien vous devez lire / écrire - rien dans ce cas.
Nous n'avons pas vraiment besoin d'un chiffre pour représenter zéro. L'utilisation d'un chiffre pour zéro n'est nécessaire que dans une phrase lisible par l'homme où nous devons détecter la présence d'un nombre. Sinon, lorsque nous savons déjà qu'il y a un nombre là-bas, la séquence vide de chiffres est une représentation parfaitement bonne pour zéro, qui est également plus régulière. Essayez d'écrire un algorithme pour convertir les naturales en chaînes de bits de longueur variable et vice versa: c'est plus facile si nous représentons zéro comme la chaîne vide. En effet, lorsque nous avons besoin du zéro à un chiffre, nous devons mettre en œuvre un cas spécial juste pour cela.
@Cherrydt Il existe deux variantes de
bit_width (x): "Nombre de bits requis pour coderx" et "Taille du plus petit objet en béton qui peut stockerx". Le premier est meilleur pour les codes de longueur variable, tandis que le second aide à éviter les cas de bord gênants dans les structures de données emballées.Faire écho aux autres - une autre façon de considérer cela. Si vous voulez seulement enregistrer «seulement zéro», il n'y a rien à enregistrer car zéro n'a pas besoin d'être distingué contre toute autre valeur. Il vous suffit d'enregistrer une valeur, en utilisant 1 ou plusieurs bits, lorsqu'il y a un choix de valeurs.