Auf das nächste Vielfache von k aufrunden

Hallo Forum,

habe da ne kleine frage, und zwar: wie kann ich n am schnellsten (!) auf ein vielfaches von k aufrunden? n und k sind natürliche zahlen, und wenn n schon ein vielfaches von k ist soll nix passiern, hier mal ein bsp:

n=15, k=8, ergebnis=16
n=48, k=50, ergebnis=50
n=32, k=8, ergebnis=32

wichtig ist nur, dass es schnell ist, bit-ops sind also nicht unerwünscht, viele if-statements und rechenoperationen hingegen schon. hatte auch schon ein paar ideen wie

n += 8 - (n % k);

hier wird aber immer addiert (z.b. wenn n schon so durch k teilbar wäre)

vielen dank schonmal im voraus

Th

int m = n % k;
if(m > 0)
  n += k - m;

das mit dem if wird sehr wahrscheinlich nicht schneller sein, wegen pipelines und so.

Wieso musst du eigentlich sowas optimieren? Ist das wirklich die einzige Schwachstelle im Code?

hast recht, bins nochmal durchgegangen und hab' festgestellt, dass es gar keinen so entscheidenden vorteil bringt. an alle, die trotzdem noch interesse an dem code haben, hier nochmal die geschichte mit dem aufrunden, so wies bei mir momentan aussieht (k ist übrigens immer 8, habs zuvor verpennt zu erwähnen):

// da gilt n & (k-1) == n % k (für 2er potenzen)
n += 8 - ( n & 7 );
// und da (n & 7) auch 0 sein kann bzw dann 8 - 0 = 8 machen wir noch folgendes
n += ( 8 - (n & 7)) & 7;
// im internet hab ich außerdem noch gefunden:
n += (-n & 7);

wobei ich zugeben muss, dass die variante von Th eindeutig einleuchtender und verständlicher ist

santa klaus schrieb:

wobei ich zugeben muss, dass die variante von Th eindeutig einleuchtender und verständlicher ist

wenn's dir immer noch um speed geht, dann versuch' aus dem code das modulo wegzukriegen. % ist immer superlangsam.

Premature Optimizer schrieb:

santa klaus schrieb:

wobei ich zugeben muss, dass die variante von Th eindeutig einleuchtender und verständlicher ist

wenn's dir immer noch um speed geht, dann versuch' aus dem code das modulo wegzukriegen. % ist immer superlangsam.

hab gerade noch n alten link rausgekramt: http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/(Fast modulo operation) der bestätigt das nur, sind aber auch noch n paar andere interessante optimierungen dabei