L'arrondissement de division entière (au lieu de les tronquer)
J'étais curieux de savoir comment je peux arrondir un nombre à l'entier le plus proche. Par exemple, si j'ai eu:
int a = 59 / 4;
qui serait 14.75 si le calcul en virgule flottante; comment puis-je stocker le résultat dans 15 en "a"?
- Veuillez préciser: dixième Le plus proche (14.8) ou nombre entier le plus proche (15) ?
- depuis un est un int, il doit être arrondi au nombre entier le plus proche, n'est-ce pas?
- désolé l'entier le plus proche
- Regarde de cette façon, mais alors pourquoi dire "au dixième le plus proche" dans l'énoncé du problème? Soit l'énoncé est incorrect ou il y a quelque chose que l'OP veut le faire, qu'il n'est pas spécifier clairement. C'est l'idée derrière demander des éclaircissements.
- hmm, oui, bon point! Je ne suis pas sûr de savoir pourquoi il se pose au sujet de dixièmes lors de stocker le résultat dans un entier.
Vous devez vous connecter pour publier un commentaire.
Cela ne fonctionne que lors de l'attribution d'un int comme il ignore quoi que ce soit après le"."
Edit:
Cette solution ne fonctionnera que dans le cas le plus simple. Une solution plus robuste serait:
std::cout << "exact: " << (-8.0f / 2.0f) << std::endl;
etstd::cout << "rounded: " << (int) (-8.0f / 2.0f + 0.5f) << std::endl;
. première-4
et arrondie est-3
. pour le négatif, vous devriez-0.5
au lieu de0.5
La norme idiome pour entier arrondissement est:
Vous ajoutez le diviseur moins un dividende.
int i = (x + (n / 2)) / n;
?x
et/oun
?int abs(int n);
(à partir de la Norme C) etint signum(int n) { return (n < 0) ? -1 : (n > 0) ? +1 : 0; }
pourrait venir dans maniable.x + n / 2
déborde...int
. Mais si le diviseur ou le dividende est négatif, il produit une réponse incorrecte. L'astuce pour @caf ne fonctionne pas non plus.c = (INT_MAX + (4 - 1)) / 4;
donnec = -536870911
en raison de dépassement d'entier...Un code qui fonctionne pour tout signe de dividende et diviseur:
Si vous préférez une macro:
Le noyau linux macro DIV_ROUND_CLOSEST ne fonctionne pas pour les diviseurs!
int
les valeurs proches de min/max int, c'est la meilleure solution à ce jour.Vous devriez plutôt utiliser quelque chose comme ceci:
Je suppose que vous êtes vraiment essayer de faire quelque chose de plus général:
x + (y-1) a le potentiel de débordement donnant le résultat incorrect; attendu que x - 1 ne underflow si x = min_int...
(Édité)
L'arrondissement des nombres entiers avec virgule flottante est la méthode la plus simple solution de ce problème; cependant, selon le problème est peut-être possible. Par exemple, dans les systèmes embarqués virgule flottante, la solution est peut-être trop coûteux.
Cette opération à l'aide de math entier s'avère être un peu dur et un peu de peu intuitive. Le premier posté solution a bien fonctionné pour les le problème que j'avais utilisé pour, mais après avoir qualifié les résultats sur la plage des entiers, il s'est avéré être très mauvais en général. En regardant à travers plusieurs livres sur le bit se tourner et intégré de mathématiques de retour peu de résultats.
Un couple de notes. Tout d'abord, j'ai testé uniquement pour des entiers positifs, mon travail n'implique pas négatif numérateurs ou les dénominateurs. Deuxièmement, et test exhaustif de 32 bits entiers est de calcul prohibitif, j'ai donc commencé avec 8 bits entiers puis made sûr que j'ai obtenu des résultats similaires avec 16 bits entiers.
J'ai commencé avec les 2 solutions que j'avais déjà proposé:
#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)
#define DIVIDE_WITH_ROUND(N, D) (N == 0) ? 0:(N - D/2)/D + 1;
Ma pensée était que la première version de débordement avec de gros chiffres et de la deuxième underflow avec de petits nombres. Je n'ai pas pris 2 choses en considération. 1.) le 2ème problème est en fait récursive puisque pour obtenir la bonne réponse, vous avez de bien ronde D/2. 2.) Dans le premier cas, vous avez souvent débordement et puis underflow, les deux annulant les uns les autres.
Ici est une erreur de l'intrigue des deux (mauvaises) des algorithmes:
Cette courbe montre que le premier algorithme est seulement mauvaise pour les petits dénominateurs (0 < d < 10). De façon inattendue, il gère en fait grand numérateurs mieux que la version 2.
Voici le tracé de la 2ème algorithme:
Comme prévu, il ne parvient pas pour les petites numérateurs mais échoue également pour les plus grands numérateurs que la 1ère version.
Clairement, c'est le meilleur point de départ pour une version correcte:
#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)
Si votre dénominateurs > 10, alors cela fonctionnera correctement.
Un cas spécial est nécessaire pour D == 1, il suffit de retourner N.
Un cas spécial est nécessaire pour D== 2, = N/2 + (N & 1) //Round up, s'il est impair.
D >= 3 a également des problèmes une fois N devient assez grand. Il s'avère que de plus grands dénominateurs n'ont que des problèmes avec les plus grandes numérateurs. Pour 8 bits signé nombre le problème des points sont
if (D == 3) && (N > 75))
else if ((D == 4) && (N > 100))
else if ((D == 5) && (N > 125))
else if ((D == 6) && (N > 150))
else if ((D == 7) && (N > 175))
else if ((D == 8) && (N > 200))
else if ((D == 9) && (N > 225))
else if ((D == 10) && (N > 250))
(retour D/N pour ces)
Donc, en général, la pointe où le numérateur est mauvaise est quelque part autour
N > (MAX_INT - 5) * D/10
Ce n'est pas exact, mais à proximité. Lorsque vous travaillez avec 16 bits ou plus grand nombre l'erreur < 1% si vous venez de faire un C diviser (troncature) pour ces cas.
De 16 bits des nombres signés les tests serait
if ((D == 3) && (N >= 9829))
else if ((D == 4) && (N >= 13106))
else if ((D == 5) && (N >= 16382))
else if ((D == 6) && (N >= 19658))
else if ((D == 7) && (N >= 22935))
else if ((D == 8) && (N >= 26211))
else if ((D == 9) && (N >= 29487))
else if ((D == 10) && (N >= 32763))
De cours pour les entiers non signés MAX_INT serait remplacé par MAX_UINT. Je suis sûr qu'il y est une formule exacte pour la détermination de la plus grande N qui va travailler pour un particulier D et le nombre de bits mais je n'ai pas plus de temps pour travailler sur ce problème...
(J'ai l'impression de rater ce graphique pour le moment, je vais modifier et ajouter plus tard.)
C'est un graphique de l'8 bits version avec les cas particuliers mentionné ci-dessus:![8 bits signés avec des cas particuliers pour
0 < N <= 10
TroisNoter que, pour les 8 bits de l'erreur est de 10% ou moins pour toutes les erreurs dans le graphique 16 bits, est < de 0,1%.
Comme l'écrit, vous effectuez l'arithmétique des nombres entiers, qui ne tronque tout décimal résultats. Pour effectuer l'arithmétique à virgule flottante, soit modifier les constantes en virgule flottante:
Ou exposez-les à un
float
ou d'un autre type à virgule flottante:De toute façon, vous devez faire la finale de l'arrondissement avec la
round()
fonction dans lemath.h
en-tête, afin d'être sûr de#include <math.h>
et l'utilisation d'un C99 compatible compilateur.float
(IEEE) les limites de la portée utile de cette solution à l'abs(a/b) < 16,777,216.lround
.Du noyau Linux (GPLv2):
typeof()
partie de C ou un compilateur spécifique de l'extension?Vérifier si il y a un reste permet de modifier manuellement le roundup, le quotient de la division entière.
ceil
fonction, pas une bonne arrondissementUne autre utilité des MACROS (DOIT AVOIR):
ROUND
, pasCEIL
Voici ma solution. Je l'aime parce que je trouve ça plus lisible et parce qu'il n'a pas de ramification (ni fi ni ternaires).
Plein programme de test qui illustre l'intention de comportement:
&
dans((a ^ b) & 0x80000000) >> 31;
est redondant, puisque le faible de bits seront jetés après la maj de toute façonEmprunt de @ericbn je visez plutôt définit comme
par exemple 59/4 Quotient = 14, tempY = 2, reste = 3, reste >= tempY donc le quotient = 15;
divide(-59, 4)
.essayez d'utiliser les mathématiques fonction ceil qui fait des arrondis. Mathématiques Ceil !
Si vous êtes à la division des entiers positifs, vous pouvez déplacer vers le haut, faire la division et de vérifier ensuite les bits vers la droite de la vraie b0. En d'autres termes, 100/8 est de 12,5 mais serait de retour 12. Si vous n' (100<<1)/8, vous pouvez vérifier b0 puis après avoir passer le résultat à l'arrière en bas.
Pour certains algorithmes, vous avez besoin d'un uniforme de biais lorsque la "plus proche" est une cravate.
Cela fonctionne indépendamment du signe du numérateur ou du dénominateur.
Si vous souhaitez faire correspondre les résultats de
round(N/(double)D)
(floating-point de la division et de l'arrondi), voici quelques-unes des variations qui tous produisent les mêmes résultats:Remarque: La vitesse relative de
(abs(d)>>1)
vs(d/2)
est susceptible d'être dépendants de la plateforme.int
.return (n+(1<<shift>>1))>>shift;
, ce qui simplifie la forme(n+C)>>shift
(oùC=(1<<shift>>1)
sishift
arrive à être une constante.Le suivant correctement les tours, le quotient de l'entier le plus proche pour à la fois positifs et négatifs opérandes SANS virgule flottante ou les branches conditionnelles (voir assemblée de sortie ci-dessous). Suppose N bits en complément de 2 entiers.
La valeur de l'ARRONDISSEMENT ont le même signe que le dividende (x) et la moitié de la ampleur du diviseur (y). L'ajout de l'ARRONDISSEMENT pour le dividende augmente ainsi sa grandeur avant la division entière tronque l'résultant du quotient. Voici la sortie du compilateur gcc avec-O3 optimisation pour un 32-bit ARM Cortex-M4 processeur:
Quelques solutions de rechange pour la division par 4
Ou en général, de la division par une puissance de 2
Il fonctionne par arrondissement si la partie fractionnaire ⩾ de 0,5, c'est à dire le premier chiffre ⩾ de base/2. En binaire, c'est l'équivalent de l'ajout de la première fractions de peu pour la suite
Cette méthode a un avantage dans les architectures avec un drapeau de s'inscrire, car le porte drapeau de contenir la dernier bit qui a été déplacé hors. Par exemple sur x86, il peut être optimisé en
Il est également facilement étendu pour supporter les entiers signés. Notez que l'expression des nombres négatifs est
nous pouvons le faire fonctionner pour des valeurs négatives et positives avec
TLDR: Voici une macro; utiliser!
Exemple d'utilisation:
Réponse complète:
Certaines de ces réponses sont fous à la recherche! Codeface cloué si! (Voir @0xC0DEFACE de réponse ici). J'aime vraiment le type sans macro ou gcc énoncé de la forme d'expression de plus de la forme d'une fonction, toutefois, si, j'ai écrit cette réponse avec une explication détaillée de ce que je fais (c'est à dire: pourquoi cette mathématiquement œuvres) et de le mettre en 2 formes:
1. Macro, avec des commentaires détaillés pour expliquer le tout:
2. GCC Déclaration Expression forme:
Voir un peu plus sur gcc déclaration des expressions ici.
Réponses:
BASE 2 CONCEPT:
pour plus de détails!J'ai couru dans la même difficulté.
Le code ci-dessous devrait fonctionner pour des entiers positifs.
Je n'ai pas compilé pas encore mais j'ai testé l'algorithme sur une feuille de calcul google (je sais, wtf) et cela fonctionnait.
if(denominator == 1) return numerator;
. Quel est son but?Plus sûr de code C (sauf si vous avez d'autres méthodes de gestion /0):
return (_divisor > 0) ? ((_dividend + (_divisor - 1)) /_divisor) : _dividend;
Ce ne gère pas les problèmes qui se produisent d'avoir une mauvaise valeur de retour comme un résultat de vos données d'entrée non valides, bien sûr.