Rapide au plafond d’une division d’entier en C / C++

Question

Compte tenu des valeurs entières x et y, le C et le C++ à la fois, de retour comme le quotient q = x/y le plancher de l'équivalent en virgule flottante. Je suis interestd dans une méthode de retour du plafond de la place. Par exemple, ceil(10/5) = 2 et ceil(11/5) = 3.

L'approche évidente implique quelque chose comme:

q = x / y;
if (q * y < x) ++q;

Cela nécessite une comparaison supplémentaire et la multiplication; et d'autres méthodes que j'ai vu (en réalité) impliquent casting en tant que float ou double. Est-il plus directe de la méthode qui évite la supplémentaires de multiplication (ou un deuxième division) et de la direction générale, et qui permet aussi d'éviter de moulage comme un nombre à virgule flottante?

Answer 1

Pour arrondir...

ou (éviter le débordement en x + y)

Answer 2

Pour les nombres positifs :

Answer 3

Sparky la réponse est d'une manière standard pour résoudre ce problème, mais comme je l'ai écrit dans mon commentaire, vous courez le risque de débordements. Cela peut être résolu en utilisant un large type, mais si vous voulez diviser long longs?

Nathan Ernst réponse fournit une solution, mais elle implique un appel de fonction, une déclaration de variable et d'un conditionnel, ce qui ne la rend pas plus courte que la OPs code et probablement même plus lentement, car il est plus difficile à optimiser.

Ma solution est:

q = (x % y) ? x / y + 1 : x / y);

Il sera légèrement plus rapide que l'OPs code, parce que le modulo et la division est effectuée à l'aide de la même instruction sur le processeur, car le compilateur ne peut voir qu'ils sont équivalents. Au moins gcc 4.4.1 effectue cette optimisation -O2 drapeau sur x86.

En théorie, le compilateur peut inline l'appel de la fonction dans Nathan Ernst code et d'émettre la même chose, mais gcc n'a pas fait ça quand je l'ai testé. Ce pourrait être parce qu'il est possible d'attacher le code compilé à une version unique de la bibliothèque standard.

Comme note finale, aucune de ces questions sur une machine moderne, sauf si vous êtes dans une situation extrêmement boucle serrée, et toutes vos données dans les registres ou dans la L1-cache. Sinon, toutes ces solutions seront tout aussi rapides, à l'exception, peut-être Nathan Ernst, qui pourrait être beaucoup plus lent si la fonction doit être récupérée à partir de la mémoire principale.

Answer 4

Vous pouvez utiliser le `` fonction dans cstdlib pour obtenir le quotient et le reste dans un seul appel et la poignée puis le plafond séparément, comme dans les dessous

Answer 5

Comment à ce sujet? (nécessite un y non-négatif, de sorte à ne pas l'utiliser dans les rares cas où y est une variable sans la non-négativité de garantie)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

J'ai réduit y/y pour l'un, en éliminant le terme x + y - 1 et avec elle toute possibilité de débordement.

- Je éviter x - 1 enroulant autour d'lorsqu' x est un type non signé et contient zéro.

Pour la signature de x, négatif et nul encore de combiner dans un seul cas.

Probablement pas un énorme avantage sur un moderne à usage général pour le PROCESSEUR, mais ce serait beaucoup plus rapide dans un système embarqué que toutes les autres réponses correctes.