Aufrunden einer Zahl auf nächstes Vielfaches

[Valle]

Hallo DPler!

Ich stehe im Moment leider mathematisch etwas auf dem Schlauch. Ziel ist es, eine ganze Zahl auf das nächste Vielfache von m aufzurunden.
Hier unterscheidet sich die Aufgabe in zwei Situationen:

(1) m ist bereits beim Programmieren bekannt und entspricht einer Zweierpotenz, in meinem Fall 2^12, also 4096.
(2) m ist eine beliebige, unbekanntem ganze Zahl

Hier ein kleiner Demonstrations-Code, der in beiden Fällen tut was er soll, allerdings sehr unschön.

Code:

while zahl % m != 0:
    zahl = zahl + 1

Ich würde mich freuen, wenn ihr mir helfen könntet, die Zahl korrekt aufzurunden. Für die zwei unterschiedlichen Fälle sind auch zwei unterschiedliche Vorgänge in Ordnung, es interessiert mich hier lediglich, wie man in beiden Fällen am besten Vorgehen kann. Bei (1) lässt sich möglicherweise besser mit Bitschupserei arbeiten.

Das Ganze muss unabhängig von jeder Sprache und Bibliothek funktionieren, also kein ceil() o.ä.

Vielen Dank für eure Hilfe!

Liebe Grüße,
Valentin

[Meflin]

Zitat von Valle:

Das Ganze muss unabhängig von jeder Sprache und Bibliothek funktionieren, also kein ceil() o.ä.

Du bist lustig

Für den allgemeinen Fall: Die Signumsfunktion kann man sich Bit-Arithmetisch bauen (siehe z.B.: http://bits.stephan-brumme.com/sign.html, oder noch einfacher mit if-else). Wenn meine Erkältung also mein Hirn grade nicht zu sehr außer Funktion setzt sollte sich das ganze doch in etwa so Lösen lassen:

Code:

x = Zahl
m = Vielfaches, auf das x gerundet werden soll

f = x div m (oder darf man auch keine Integer-Division voraussetzen? Kann man aber zur Not ja mit Modulo bauen...)
fa = sgn(x mod m)
result = (f + fa) * m

[BUG]

Auf 2^12 aufrunden (mit Bitschubserei):

Code:

BIT12 = 1 << 12
MASK11 =  BIT12 - 1; // Bitmaske unterste 11 Bits
if (MASK11 & eingabe != 0) {
  ergebnis = (eingabe & ~MASK11) + BIT12;
} else {
  ergebnis = eingabe;
}

Mit der von Melfin genannten Signum-Funktion würde es so gehen:

Code:

BIT12 = 1 << 12
MASK11 =  BIT12 - 1;
ergebnis = (eingabe & ~MASK11) + (sgn(eingabe & ~MASK11)) << 12;

Das geht beides allerdings nur mit positiven Zahlen gut.

EDIT: Das musste jetzt einfach sein

Delphi-Quellcode:

{$ASMMODE intel}
function roundUp4096(x: longword): longword; pascal;
const
  mask11: longword = (1 shl 12) - 1;
  not_mask11: longword = not ((1 shl 12) - 1);
begin
  asm
    mov edx, eax          // eax = edx = x
    and eax, not_mask11
    xor ecx, ecx          // clear ecx
    and edx, mask11
    setnz cl               // cl = 1 if not zeroflag else 0
    shl ecx, 12
    add eax, ecx
  end;
end;

[bit4bit]

@valle

... also Dein

Delphi-Quellcode:

while zahl % m != 0:
    zahl = zahl + 1

ist äquivalent zu

Delphi-Quellcode:

zahl, m: integer;
zahl := ((zahl + m-1) div m ) * m;

oder hab ich was falsch verstanden ?

Wenn es zeitkritisch ist kann man daran noch einiges optimieren

[Valle]

Hallo,

vielen Dank für eure Antworten!

Jetzt wenn man weiß wie's geht, ist die Sache doch eigentlich ganz einfach.

@Meflin: Die Sache muss unabhängig sein, da der Code Teil eines Betriebssystem-Kernels ist.

Liebe Grüße,
Valentin