Soffitto veloce di una divisione intera in C / C ++

Dati i valori interi y , C e C ++ restituiscono entrambi il quoziente q = x/y del floor dell’equivalente in virgola mobile. Mi interessa invece un metodo per restituire il soffitto. Ad esempio, ceil(10/5)=2 e ceil(11/5)=3 .

L’approccio ovvio riguarda qualcosa come:

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

Ciò richiede un confronto e una moltiplicazione aggiuntivi; e altri metodi che ho visto (usati di fatto) implicano il casting come float o double . Esiste un metodo più diretto che eviti la moltiplicazione aggiuntiva (o una seconda divisione) e il ramo, e che eviti anche il cast come numero in virgola mobile?

Per arrotondare …

 q = (x + y - 1) / y; 

o (evitando l’overflow in x + y)

 q = 1 + ((x - 1) / y); // if x != 0 

La risposta di Sparky è un modo standard per risolvere questo problema, ma come ho scritto anche nel mio commento, si corre il rischio di tracimare. Questo può essere risolto utilizzando un tipo più ampio, ma cosa succede se si desidera dividere long long s long long ?

La risposta di Nathan Ernst fornisce una soluzione, ma implica una chiamata di funzione, una dichiarazione di variabile e una condizionale, che lo rende non più breve del codice OPs e probabilmente anche più lento, perché è più difficile da ottimizzare.

La mia soluzione è questa:

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

Sarà leggermente più veloce del codice OPs, perché il modulo e la divisione vengono eseguiti utilizzando la stessa istruzione sul processore, perché il compilatore può vedere che sono equivalenti. Almeno gcc 4.4.1 esegue questa ottimizzazione con il flag -O2 su x86.

In teoria il compilatore potrebbe inline la chiamata di funzione nel codice di Nathan Ernst ed emettere la stessa cosa, ma gcc non l’ha fatto quando l’ho testato. Questo potrebbe essere perché legherebbe il codice compilato a una singola versione della libreria standard.

Come nota finale, nulla di tutto ciò è importante su una macchina moderna, eccetto se si è in un ciclo estremamente stretto e tutti i dati sono in registri o nella cache L1. Altrimenti tutte queste soluzioni saranno ugualmente veloci, tranne forse Nathan Ernst, che potrebbe essere molto più lento se la funzione deve essere recuperata dalla memoria principale.

Per i numeri positivi:

  q = x/y + (x % y != 0); 

È ansible utilizzare la funzione div in cstdlib per ottenere il quoziente e il resto in una singola chiamata e quindi gestire il massimale separatamente, come nel seguente

 #include  #include  int div_ceil(int numerator, int denominator) { std::div_t res = std::div(numerator, denominator); return res.rem ? (res.quot + 1) : res.quot; } int main(int, const char**) { std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl; std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl; return 0; } 

Cosa ne pensi di questo? (richiede y non negativo, quindi non usare questo nel raro caso in cui y è una variabile senza garanzia di non-negatività)

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

Ho ridotto y/y a uno, eliminando il termine x + y - 1 e con esso ogni possibilità di overflow.

Evito x - 1 avvolge quando x è un tipo senza segno e contiene zero.

Per x , negativo e zero firmati si combinano ancora in un singolo caso.

Probabilmente non è un enorme vantaggio per una moderna CPU generica, ma questo sarebbe molto più veloce in un sistema embedded rispetto a qualsiasi altra risposta corretta.

C’è una soluzione per x positivi e negativi ma solo per y positivi con solo 1 divisione e senza rami:

 int ceil(int x, int y) { return x / y + (x % y > 0); } 

Nota, se x è positivo, la divisione è verso zero e dovremmo aggiungere 1 se il promemoria non è zero.

Se x è negativo, la divisione è verso zero, questo è ciò di cui abbiamo bisogno e non aggiungeremo nulla perché x % y non è positivo

Funziona per numeri positivi o negativi.

q = x/y+((x%y!=0)?!((x>0)^(y>0)):0);

Se c’è un resto, controlla se x e y hanno lo stesso segno e aggiunge 1 di conseguenza.

forma generica semplificata,

 int div_up(int n, int d) { return n / d + (((n < 0) ^ (d > 0)) && (n % d)); } //ie +1 iff (not exact int && positive result) 

Per una risposta più generica, le funzioni C ++ per la divisione di interi con strategia di arrotondamento ben definita