Comment puis-je m'assurer qu'une division d'entiers est toujours arrondie à l'unité supérieure ?

Question

Je veux m'assurer qu'une division d'entiers est toujours arrondie vers le haut si nécessaire. Existe-t-il une meilleure méthode que celle-ci ? Il y a beaucoup de moulage :-)

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

Answer 1

UPDATE : Cette question a été le sujet de mon blog en janvier 2013 . Merci pour cette excellente question !

---

Obtenir une arithmétique correcte des nombres entiers est difficile. Comme cela a été amplement démontré jusqu'à présent, dès que vous essayez de faire une astuce "intelligente", il y a de fortes chances que vous fassiez une erreur. Et lorsqu'une faille est trouvée, modifier le code pour corriger la faille sans considérer si la réparation casse quelque chose d'autre n'est pas une bonne technique de résolution de problèmes. Jusqu'à présent, nous avons eu, je crois, cinq solutions arithmétiques incorrectes différentes pour ce problème qui n'est pas particulièrement difficile.

La bonne façon d'aborder les problèmes d'arithmétique des nombres entiers - c'est-à-dire la façon qui augmente la probabilité d'obtenir la bonne réponse dès 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 ce faire.

Commencez par lire les spécifications de ce que vous essayez de remplacer. La spécification pour la division d'entiers indique clairement :

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

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

3. Si l'opérande de gauche est le plus petit int représentable et que l'opérande de droite est -1, un débordement se produit. [...] l'implémentation détermine si [une ArithmeticException] est déclenchée ou si le dépassement de capacité n'est pas signalé, la valeur résultante étant celle de l'opérande gauche.

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

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

Rédigez 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 inquiétant, alors éliminons-le. Nous dirons que notre opération a cette spécification :

1. l'opération est rejetée si le diviseur est zéro

2. l'opération échoue 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 le plus petit nombre entier qui est plus grand que le quotient, c'est-à-dire qu'il s'arrondit toujours au supérieur.

Maintenant, nous avons une spécification, donc nous savons que nous pouvons venir avec une conception testable . Supposons que nous ajoutions un critère de conception supplémentaire, à savoir que le problème doit être résolu uniquement à l'aide de l'arithmétique des nombres entiers, plutôt que de calculer le quotient sous forme de double, puisque la solution du "double" a été explicitement rejetée dans l'énoncé du problème.

Alors, que devons-nous calculer ? Il est clair que pour répondre à notre spécification tout en restant uniquement dans l'arithmétique des nombres entiers, nous devons connaître trois faits. Premièrement, quel était le quotient entier ? Deuxièmement, la division était-elle exempte de reste ? Et troisièmement, si non, 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 que c'est intelligent ? Non. Beau ? Non. Court ? Non. Correct selon la spécification ? Je le crois, mais je ne l'ai pas entièrement testé. Ça a l'air plutôt bien.

Nous sommes des professionnels ici ; utilisez les bonnes pratiques d'ingénierie. Faites des recherches sur vos outils, spécifiez le comportement souhaité, envisagez d'abord les cas d'erreur, et écrire le code pour souligner son exactitude évidente. Et lorsque vous trouvez un bogue, demandez-vous si votre algorithme n'est pas profondément défectueux avant de commencer à intervertir au hasard le sens des comparaisons et de casser des choses qui fonctionnent déjà.

Answer 2

Toutes les réponses données ici jusqu'à présent semblent plutôt trop compliquées.

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

( dividend + divisor - 1 ) / divisor 

Source : Conversion des numéros, Roland Backhouse, 2001

Answer 3

La réponse finale basée sur l'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 pour cette réponse

Division d'un nombre entier ' / est défini pour arrondir vers zéro (7.7.2 de la spécification), mais nous voulons arrondir vers le haut. Cela signifie que les réponses négatives sont déjà arrondies correctement, mais que 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 elle peut être soit l'arrondi d'une valeur négative vers le haut, soit l'arrondi d'une valeur positive vers le bas.

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 de nombres entiers ' ^ sur les deux valeurs donnera lieu à un bit de signe 0 dans ce cas, ce qui signifie un résultat non négatif, de sorte que le contrôle (a ^ b) >= 0 dé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.

Le seul contrôle restant est alors de savoir si un arrondi a eu lieu, pour lequel a % b != 0 fera l'affaire.

Les leçons apprises

L'arithmétique (entière ou autre) n'est pas aussi simple qu'il n'y paraît. Il faut réfléchir soigneusement à tout moment.

De plus, bien que ma réponse finale ne soit peut-être pas aussi "simple", "évidente" ou même "rapide" que les réponses en virgule flottante, elle a une qualité rédemptrice très importante pour moi : j'ai maintenant raisonné la réponse, et je suis donc certain qu'elle est correcte (jusqu'à ce que quelqu'un de plus intelligent me dise le contraire ). regard furtif dans la direction d'Eric -).

Pour obtenir le même sentiment de certitude quant à la réponse en virgule flottante, il faudrait que je réfléchisse davantage (et peut-être plus compliqué) à la question de savoir s'il existe des conditions dans lesquelles la précision de la virgule flottante pourrait être un obstacle, et si Math.Ceiling fait peut-être quelque chose d'indésirable sur les "bonnes" entrées.

Le chemin parcouru

Remplacez (notez que j'ai remplacé le deuxième myInt1 con myInt2 (en supposant que c'est ce que vous vouliez dire) :

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

avec :

(myInt1 - 1 + myInt2) / myInt2

La seule réserve est que si myInt1 - 1 + myInt2 déborde le type d'entier que vous utilisez, vous risquez de ne pas obtenir ce que vous attendez.

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

EDIT :
Considérant que cela a la même erreur que l'autre solution entière pour le négatif myInt1 il serait peut-ê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 dans div en utilisant uniquement des opérations sur des nombres entiers.

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

EDIT (une fois de plus, avec émotion) :
L'opérateur de division arrondit vers zéro ; pour les résultats négatifs, c'est exactement ce qui se passe, donc seuls les résultats non négatifs doivent être ajustés. En considérant également que DivRem fait juste un / et un % de toute façon, sautons l'appel (et commençons par la comparaison facile pour éviter le calcul du 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, ceci donne 1

(Pour ma défense, lors de ma dernière tentative, je n'aurais jamais dû essayer de donner une réponse raisonnée alors que mon esprit me disait que j'avais deux heures de retard pour dormir).

Answer 4

Une 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 également votre code très lisible :

int result = myInt.DivideByAndRoundUp(4);

Answer 5

Vous pourriez écrire une aide.

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