Comment puis-je m'assurer qu'une division d'entiers est toujours arrondie?

Je veux m'assurer qu'une division d'entiers est toujours arrondie si nécessaire. Y a-t-il une meilleure façon que cela? Il y a beaucoup de casting en cours. :-)

(int)Math.Ceiling((double)myInt1 / myInt2)

MISE À JOUR: Cette question a fait l'objet de mon blog en janvier 2013 . Merci pour la grande question!

Il est difficile d'obtenir une arithmétique entière correcte. Comme cela a été amplement démontré jusqu'à présent, au moment où vous essayez de faire un tour "intelligent", les chances sont bonnes que vous ayez fait une erreur. Et quand une faille est trouvée, changer le code pour corriger la faille sans se demander si la correction rompt autre chose n'est pas une bonne technique de résolution de problème. Jusqu'à présent, nous avons eu, je pense, cinq solutions arithmétiques entières incorrectes différentes à ce problème complètement pas particulièrement difficile.

La bonne façon d'aborder les problèmes arithmétiques entiers - c'est-à-dire la façon qui augmente la probabilité d'obtenir la bonne réponse la première fois - est d'aborder le problème avec soin, de le résoudre étape par étape et d'utiliser de bons principes d'ingénierie pour le faire. alors.

Commencez par lire les spécifications de ce que vous essayez de remplacer. La spécification pour la division entière indique clairement:

1. La division arrondit le résultat vers zéro

2. Le résultat est zéro ou positif lorsque les deux opérandes ont le même signe et zéro ou négatif lorsque les deux opérandes ont des signes opposés

3. Si l'opérande gauche est le plus petit entier représentable et l'opérande droit est –1, un débordement se produit. [...] il est défini par l'implémentation si [une ArithmeticException] est levée ou si le débordement n'est pas signalé, la valeur résultante étant celle de l'opérande de gauche.

4. Si la valeur de l'opérande de droite est zéro, une System.DivideByZeroException est levée.

Ce que nous voulons, c'est une fonction de division entière qui calcule le quotient mais arrondit toujours le résultat vers le haut , pas toujours vers zéro .

Écrivez donc une spécification pour cette fonction. Notre fonction int DivRoundUp(int dividend, int divisor)doit avoir un comportement défini pour chaque entrée possible. Ce comportement indéfini est profondément préoccupant, alors éliminons-le. Nous dirons que notre opération a cette spécification:

1. opération lance si le diviseur est nul

2. opération lance si le dividende est int.minval et le diviseur est -1

3. s'il n'y a pas de reste - la division est 'paire' - alors la valeur de retour est le quotient intégral

4. Sinon, il renvoie le plus petit entier supérieur au quotient, c'est-à-dire qu'il arrondit toujours.

Nous avons maintenant une spécification, nous savons donc que nous pouvons proposer une conception testable . Supposons que nous ajoutions un critère de conception supplémentaire pour que le problème soit résolu uniquement avec une arithmétique entière, plutôt que de calculer le quotient comme un double, car la solution "double" a été explicitement rejetée dans l'énoncé du problème.

Alors, que devons-nous calculer? De toute évidence, pour répondre à nos spécifications tout en restant uniquement en arithmétique entière, nous devons connaître trois faits. Tout d'abord, quel était le quotient entier? Deuxièmement, la division était-elle exempte de reste? Et troisièmement, sinon, le quotient entier a-t-il été calculé en arrondissant vers le haut ou vers le bas?

Maintenant que nous avons une spécification et une conception, nous pouvons commencer à écrire du code.

public static int DivRoundUp(int dividend, int divisor)
{
  if (divisor == 0 ) throw ...
  if (divisor == -1 && dividend == Int32.MinValue) throw ...
  int roundedTowardsZeroQuotient = dividend / divisor;
  bool dividedEvenly = (dividend % divisor) == 0;
  if (dividedEvenly) 
    return roundedTowardsZeroQuotient;

  // At this point we know that divisor was not zero 
  // (because we would have thrown) and we know that 
  // dividend was not zero (because there would have been no remainder)
  // Therefore both are non-zero.  Either they are of the same sign, 
  // or opposite signs. If they're of opposite sign then we rounded 
  // UP towards zero so we're done. If they're of the same sign then 
  // we rounded DOWN towards zero, so we need to add one.

  bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
  if (wasRoundedDown) 
    return roundedTowardsZeroQuotient + 1;
  else
    return roundedTowardsZeroQuotient;
}

Est-ce intelligent? Pas beau? Non. Court? Non. Correct selon la spécification? Je le crois, mais je ne l'ai pas entièrement testé. Cela semble assez bon cependant.

Nous sommes des professionnels ici; utiliser de bonnes pratiques d'ingénierie. Recherchez vos outils, spécifiez le comportement souhaité, examinez d'abord les cas d'erreur et écrivez le code pour souligner son exactitude évidente. Et lorsque vous trouvez un bogue, demandez-vous si votre algorithme est profondément défectueux pour commencer avant de commencer à échanger au hasard les directions des comparaisons et à casser des choses qui fonctionnent déjà.

Jusqu'à présent, toutes les réponses semblent assez compliquées.

En C # et Java, pour un dividende et un diviseur positifs, il vous suffit de faire:

( dividend + divisor - 1 ) / divisor 

Source: Conversion de nombres, Roland Backhouse, 2001

La réponse finale basée sur int

Pour les entiers signés:

int div = a / b;
if (((a ^ b) >= 0) && (a % b != 0))
    div++;

Pour les entiers non signés:

int div = a / b;
if (a % b != 0)
    div++;

Le raisonnement de cette réponse

La division entière ' /' est définie pour arrondir vers zéro (7.7.2 de la spécification), mais nous voulons arrondir. Cela signifie que les réponses négatives sont déjà arrondies correctement, mais les réponses positives doivent être ajustées.

Les réponses positives non nulles sont faciles à détecter, mais la réponse zéro est un peu plus délicate, car cela peut être l'arrondi d'une valeur négative ou l'arrondi d'une valeur positive.

Le pari le plus sûr est de détecter quand la réponse doit être positive en vérifiant que les signes des deux entiers sont identiques. Opérateur xor entier '^ ' sur les deux valeurs se traduira par un bit de signe 0 dans ce cas, ce qui signifie un résultat non négatif, de sorte que la vérification (a ^ b) >= 0détermine que le résultat aurait dû être positif avant l'arrondi. Notez également que pour les entiers non signés, chaque réponse est évidemment positive, donc cette vérification peut être omise.

La seule vérification qui reste est alors de savoir si des arrondis ont eu lieu, pour lesquels a % b != 0 fera le travail.

Leçons apprises

L'arithmétique (entier ou autre) n'est pas aussi simple qu'il y paraît. Penser soigneusement à tout moment.

De plus, bien que ma réponse finale ne soit peut-être pas aussi «simple» ou «évidente» ou peut-être même «rapide» que les réponses en virgule flottante, elle a une très forte qualité de rachat pour moi; J'ai maintenant raisonné à travers la réponse, donc je suis en fait certain que c'est correct (jusqu'à ce que quelqu'un plus intelligent me dise le contraire - regard furtif dans la direction d'Eric -).

Pour obtenir le même sentiment de certitude à propos de la réponse en virgule flottante, je devrais faire plus (et peut-être plus compliqué) en réfléchissant à l'existence de conditions dans lesquelles la précision en virgule flottante pourrait gêner, et si Math.Ceiling peut-être quelque chose d'indésirable sur les entrées «juste à droite».

Le chemin parcouru

Remplacer (notez que j'ai remplacé le second myInt1par myInt2, en supposant que c'était ce que vous vouliez dire):

(int)Math.Ceiling((double)myInt1 / myInt2)

avec:

(myInt1 - 1 + myInt2) / myInt2

La seule mise en garde étant que si vous myInt1 - 1 + myInt2débordez du type entier que vous utilisez, vous n'obtiendrez peut-être pas ce que vous attendez.

Raison pour laquelle c'est faux : -1000000 et 3999 devraient donner -250, cela donne -249

EDIT:
Considérant que cela a la même erreur que l'autre solution entière pour les myInt1valeurs négatives , il pourrait être plus facile de faire quelque chose comme:

int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
  div++;

Cela devrait donner le résultat correct en divutilisant uniquement des opérations entières.

Raison pour laquelle c'est faux : -1 et -5 devraient donner 1, cela donne 0

EDIT (encore une fois, avec sensation):
L'opérateur de division arrondit vers zéro; pour les résultats négatifs, c'est tout à fait exact, donc seuls les résultats non négatifs doivent être ajustés. Considérant également que DivRemne fait que a /et a de %toute façon, sautons l'appel (et commençons par la comparaison facile pour éviter le calcul de modulo quand il n'est pas nécessaire):

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

Raison pour laquelle c'est faux : -1 et 5 devraient donner 0, cela donne 1

(Pour ma propre défense de la dernière tentative, je n'aurais jamais dû tenter une réponse motivée alors que mon esprit me disait que j'avais 2 heures de retard pour dormir)

Occasion parfaite d'utiliser une méthode d'extension:

public static class Int32Methods
{
    public static int DivideByAndRoundUp(this int number, int divideBy)
    {                        
        return (int)Math.Ceiling((float)number / (float)divideBy);
    }
}

Cela rend votre code aussi lisible:

int result = myInt.DivideByAndRoundUp(4);

Vous pourriez écrire un assistant.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}

Vous pouvez utiliser quelque chose comme ce qui suit.

a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)

Certaines des réponses ci-dessus utilisent des flotteurs, c'est inefficace et vraiment pas nécessaire. Pour les entrées non signées, c'est une réponse efficace pour int1 / int2:

(int1 == 0) ? 0 : (int1 - 1) / int2 + 1;

Pour les entrées signées, ce ne sera pas correct

Le problème avec toutes les solutions ici est soit qu'elles ont besoin d'un plâtre, soit un problème numérique. Casting pour flotter ou doubler est toujours une option, mais nous pouvons faire mieux.

Lorsque vous utilisez le code de la réponse de @jerryjvl

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

il y a une erreur d'arrondi. 1/5 serait arrondi, car 1% 5! = 0. Mais c'est faux, car l'arrondi ne se produira que si vous remplacez le 1 par un 3, donc le résultat est 0,6. Nous devons trouver un moyen d'arrondir lorsque le calcul nous donne une valeur supérieure ou égale à 0,5. Le résultat de l'opérateur modulo dans l'exemple supérieur a une plage de 0 à myInt2-1. L'arrondi n'aura lieu que si le reste est supérieur à 50% du diviseur. Ainsi, le code ajusté ressemble à ceci:

int div = myInt1 / myInt2;
if (myInt1 % myInt2 >= myInt2 / 2)
    div++;

Bien sûr, nous avons aussi un problème d'arrondi dans myInt2 / 2, mais ce résultat vous donnera une meilleure solution d'arrondi que les autres sur ce site.