[C++] Casten, wanneer moet het?

[JeRa]

Ik ben redelijk bekend met de datatypen en de bijbehorende limieten in C++, maar ik betrap mezelf er keer op keer op dat ik eigenlijk niet weet waarom ik cast.

Neem het volgende stukje code uit een audiomixer die ik pas geleden heb geschreven:

C++:

typedef signed short int16;
typedef unsigned char uint8;
...
uint8 _vol_l;
int16 *_buffer;
...
function mix(int16 *ptr) {
...
ptr[i] += (_buffer[i] * (_vol_l / 255));
...

Ik vermenigvuldig dus de waarde _buffer[i], een int16, met de fractionele waarde _vol_l / 255, welke dus een float of een double moet zijn? Uiteindelijk blijkt de volgende code te werken:

C++:

ptr[i] += (int16)(_buffer[i] * ((float)_vol_l / 255));

Maar ik vind het nogal triviaal en weet niet waarom bv. _buffer[i] geen cast vereist. Wie kan me uitleggen hoe C++ omgaat met casts en berekeningen of me naar een pagina doorverwijzen waar het goed beschreven staat?

edit:
...en nog iets, waarom zijn (int8 *) en (char *) niet hetzelfde, als ik int8 als volgt gedefinieerd heb?

C++:

typedef signed char int8;

Ik gebruik gcc.

[ Voor 9% gewijzigd door JeRa op 01-03-2004 18:34 . Reden: nog 'n vraag :-) ]

[Macros]

Laatste vraag: char is standaard unsigned.

[Zoijar]

vol_l_ / 255 is 0 als vol_l_ < 255. Vandaar dat je naar float cast, zodat je een fractionele waarde kan krijgen. Aangezien die uitkomst nu al float is, hoef je de buffer niet meer te casten. Aan het einde cast je weer naar int, in feite is dat afronden.
Overigens cast je in C++ op deze manier: static_cast<float>(vol_l_)

[ Voor 53% gewijzigd door Zoijar op 01-03-2004 18:51 ]

[JeRa]

Macros schreef op 01 maart 2004 @ 18:41:
Laatste vraag: char is standaard unsigned.

Ok, ik heb de dagelijkse n00b-fout weer gemaakt

Zoijar schreef op 01 maart 2004 @ 18:49:
vol_l_ / 255 is 0 als vol_l_ < 255. Vandaar dat je naar float cast, zodat je een fractionele waarde kan krijgen. Aangezien die uitkomst nu al float is, hoef je de buffer niet meer te casten. Aan het einde cast je weer naar int, in feite is dat afronden.
Overigens cast je in C++ op deze manier: static_cast<float>(vol_l_)

Bedankt, heldere uitleg
Overigens is die C++-stijl cast wel erg omslachtig, waarom is dat zo gedaan en niet bv. float(_vol_l)?

[ Voor 4% gewijzigd door JeRa op 01-03-2004 19:36 ]

[Cuball]

wat jij gebruikt zijn nog oude C casts

in C++ heb je een alternatief voor deze typische C cast namelijk een static_cast<type>(e)

verder zijn er nog enkele andere cast ook mogelijk:
http://www.uwyn.com/resou...coding_standard/x629.html

[PommeFritz]

JeRa schreef op 01 maart 2004 @ 19:35:
Overigens is die C++-stijl cast wel erg omslachtig, waarom is dat zo gedaan en niet bv. float(_vol_l)?

Omdat dat laatste geen cast is maar een runtime conversie. Er wordt dus een nieuw object aangemaakt (een float).
De cast is compile time.

[Zoijar]

JeRa schreef op 01 maart 2004 @ 19:35:
Bedankt, heldere uitleg
Overigens is die C++-stijl cast wel erg omslachtig, waarom is dat zo gedaan en niet bv. float(_vol_l)?

Omdat er in C++ duidelijk onderscheid is gemaakt tussen de verschillende soorten casts. (en hun veiligheid)

static_cast<> is de statische cast, ie. deze types kunnen compile time in elkaar omgezet worden. Bv van in naar float etc.

dynamic_cast<> is de dynamische cast, en kan gebruikt worden om downcasts te doen. Dus runtime van base naar derived class. Deze cast kan een exception veroorzaken, als base != derived.

const_cast<> kan je tussen const en non-const tpyes casten. Dus bv 'const char*' naar 'char*'

reinterpret_cast<> kan je haast compleet "vrij" mee casten, en is dus erg gevaarlijk. Dit is handig bij oa het lezen van files, waar je dan bv van 'char*' naar 'mydatatype*' cast.

Ook wordt deze nog soms zelf geimplementeerd:

C++:

template <class To, class From>
To free_cast(From f) {
   union {To t, From f} x;
   x.f = f;
   return x.t;
}

(dit is geen standaard C++, en is extreem gevaarlijk, maar je kan er bv. 'integers' naar 'member function pointers' mee casten.

[ Voor 40% gewijzigd door Zoijar op 01-03-2004 19:56 ]

[RickN]

Macros schreef op 01 maart 2004 @ 18:41:
Laatste vraag: char is standaard unsigned.

Is compiler specific.

[JeRa]

RickN schreef op 01 maart 2004 @ 20:33:
[...]

Is compiler specific.

Sterker nog, hij weigert bij zowel een unsigned als een signed char. Toch, als ik mijn eigen gedefinieerde types int8 of uint8 door char vervang compileert hij netjes. De functie die ik aanroep heeft dan wel een (char *) nodig, maar dan is (uint8 *) toch hetzelfde?

[Zoijar]

RickN schreef op 01 maart 2004 @ 20:33:
Is compiler specific.

Ja idd:

3.9.1.1:
"In any particular implementation, a plain char object can take on either the same values as a signed char or an unsigned char; which one is implementation defined."

[RickN]

JeRa schreef op 01 maart 2004 @ 20:44:
[...]

Sterker nog, hij weigert bij zowel een unsigned als een signed char. Toch, als ik mijn eigen gedefinieerde types int8 of uint8 door char vervang compileert hij netjes. De functie die ik aanroep heeft dan wel een (char *) nodig, maar dan is (uint8 *) toch hetzelfde?

Een char is niet hetzelfde als een unsigned/signed char, simple weg omdat van de ene het teken gedefineert is en van de ander niet.

Verder gaat het er niet om of het waarde bereik "hetzelfde" is (wat ik dan even losjes defineer als: hetzelfde bitpatroon), maar of het type hetzelfde is of niet.

Een rekeningnummer is niet hetzelfde als een telefoonnummer, ook niet als ik er toevallig voor kies om ze beide in een integer op te slaan. (even ervan afgezien of dat een verstandige keuze zou zijn of niet ).

[MSalters]

Ohoh char weer. Er zijn 3 char types, en die zijn verschillend, maar de range van char is een van de andere ranges. Net zoals long en int dezelfde 32 bit range kunnen hebben maar toch verchillende types zijn, of wchar_t en short op een fatsoenlijke compiler

[MSalters]

JeRa schreef op 01 maart 2004 @ 18:12:
Ik ben redelijk bekend met de datatypen en de bijbehorende limieten in C++, maar ik betrap mezelf er keer op keer op dat ik eigenlijk niet weet waarom ik cast.

Neem het volgende stukje code uit een audiomixer die ik pas geleden heb geschreven:

C++:

typedef signed short int16;
typedef unsigned char uint8;
...
uint8 _vol_l;
int16 *_buffer;
...
function mix(int16 *ptr) {
...
ptr[i] += (_buffer[i] * (_vol_l / 255));
...

Ik vermenigvuldig dus de waarde _buffer[i], een int16, met de fractionele waarde _vol_l / 255, welke dus een float of een double moet zijn? Uiteindelijk blijkt de volgende code te werken:

C++:

ptr[i] += (int16)(_buffer[i] * ((float)_vol_l / 255));

Die cast moet ook niet, sterker, die is fout. Het probleem is je evaluatie volgorde, waardoor je een factor < 1 nodig hebt. Dit is sneller en beter:

C++:

  
ptr[i] += (_buffer[i] * _vol_l ) / 255;

Maar ik vind het nogal triviaal en weet niet waarom bv. _buffer[i] geen cast vereist.
Wie kan me uitleggen hoe C++ omgaat met casts en berekeningen of me naar een pagina doorverwijzen waar het goed beschreven staat?

Casts heb je nodig als je een typeconversie wil afdwingen. Jij wilde dat omdat je int/int een float wilde laten opleveren, terwijl het resultaattype een int is. Door er float/int van te maken krijg je wel een float. Andere dingen cast de compiler voor je omdat dat dat enige mogelijke interpretatie is. Meestal zijn casts slecht, helemaal de C stijl (Type)expr

[ Voor 6% gewijzigd door MSalters op 01-03-2004 22:10 . Reden: overquoted ]

[Soultaker]

MSalters schreef op 01 maart 2004 @ 22:09:
Die cast moet ook niet, sterker, die is fout. Het probleem is je evaluatie volgorde, waardoor je een factor < 1 nodig hebt. Dit is sneller en beter:

C++:

  
ptr[i] += (_buffer[i] * _vol_l ) / 255;

Krijg je dan geen problemen wanneer het resultaat van de vermenigvuldiging niet meer in 16 bits past? Of is het resultaat van de vermenigvuldiging van een 16-bits integer met een 8-bits character een integer van tenminste 24 bits?

[Reptile209]

Soultaker schreef op 01 maart 2004 @ 23:13:
[...]

Krijg je dan geen problemen wanneer het resultaat van de vermenigvuldiging niet meer in 16 bits past? Of is het resultaat van de vermenigvuldiging van een 16-bits integer met een 8-bits character een integer van tenminste 24 bits?

Er staat me iets bij dat het grootste type dat al in de expressie zit als resultaat wordt gebruikt, met een eventuele cast naar het eindtype. Dus als er niet al een 16-bits variabele in je vermenigvuldiging zit, zou je een overflow kunnen (moeten?) krijgen. En er zijn vast momenten waarop dat "handig" is...

[igmar]

Macros schreef op 01 maart 2004 @ 18:41:
Laatste vraag: char is standaard unsigned.

Ga daar maar niet van uit, de ANSI standaard zegt daar niks over, en het verschilt per compiler.

[JeRa]

MSalters schreef op 01 maart 2004 @ 22:09:
Die cast moet ook niet, sterker, die is fout. Het probleem is je evaluatie volgorde, waardoor je een factor < 1 nodig hebt. Dit is sneller en beter:

C++:

  
ptr[i] += (_buffer[i] * _vol_l ) / 255;

Bedankt voor je heldere uitleg, maar nu weet ik nog niet hoe bovenstaand werkt. Zorgt de compiler ervoor dat die berekening altijd geldt, dus als bv. _buffer[i] * _vol_l buiten het bereik van een int16 komt er dan extra ruimte wordt gereserveerd? Kan ik dus aannemen dat het geen enkele cast vereist? Een erg mooie oplossing is het iig wel

[curry684]

Wat betreft arithmetic conversions: klikkerdeklik.

En verder als algemene regel over alle casts: nooit doen tenzij je heel zeker weet dat het nodig is. Als je het teveel doet breng je de toekomstbestendigheid van je code enorm in gevaar (stel dat je het originele datatype wijzigt waardoor je ineens downcast ipv upcast...) en bovendien geeft de compiler je ofwel met een error op je falie als je het te weinig doet (unrelated types etc.) oftewel een warning (potential overflow, possible truncation).

[Soultaker]

Het voorbeeld gaat dus goed omdat alle operands tenminste naar ints worden geconverteerd. In het algemeen heb je niet zo veel geluk, ben ik bang. Ik krijg voor code als:

code:

int foo(int a, int b)
{
        return (a*b)/65536;
}

geen enkele waarschuwing, terwijl er wel degelijk 'potential overflow' optreedt (als a*b niet meer in een int past).

[ Voor 5% gewijzigd door Soultaker op 02-03-2004 14:07 ]

[curry684]

Soultaker schreef op 02 maart 2004 @ 14:04:
geen enkele waarschuwing, terwijl er wel degelijk 'potential overflow' optreedt (als a*b niet meer in een int past).

Klopt, die warning zou ook wel verdomd vaak vallen (iedere multiply met 2 ints ) Maar in zeldzamere situaties (die ik zo snel niet meer weet ) heb ik wel eens die potential overflow warning gezien.

[koli-man]

curry684 schreef op 02 maart 2004 @ 12:48:
Wat betreft arithmetic conversions: klikkerdeklik.

En verder als algemene regel over alle casts: nooit doen tenzij je heel zeker weet dat het nodig is. Als je het teveel doet breng je de toekomstbestendigheid van je code enorm in gevaar (stel dat je het originele datatype wijzigt waardoor je ineens downcast ipv upcast...) en bovendien geeft de compiler je ofwel met een error op je falie als je het te weinig doet (unrelated types etc.) oftewel een warning (potential overflow, possible truncation).

Volgens mij kun je ook direct controleren of een cast correct gebeurt met DYNAMIC_DOWNCAST
edit: (hmm...das MFC specifiek)

[ Voor 4% gewijzigd door koli-man op 02-03-2004 14:45 ]

[.oisyn]

Overigens hoef je volgens de standaard niet tussen primitives te casten, dit is bijvoorbeeld legale code

C++:

double b = 1234.5678;
char c = b;

Alleen het is wel zo dat de meeste compilers een warning geven bij een conversion waar mogelijk precisie verloren gaat

PommeFritz schreef op 01 maart 2004 @ 19:44:

Omdat dat laatste geen cast is maar een runtime conversie. Er wordt dus een nieuw object aangemaakt (een float).
De cast is compile time.

Er wordt in alle gevallen een nieuw object aangemaakt. A(b) is niet anders dan (A)b. Als er een constructor bestaat in A die een B accepteert dan wordt die in beide gevallen aangeroepen, en anders de operator A () van B. Als geen van beide bestaan dan is er natuurlijk ook geen conversie mogelijk (even sub/super-classes buiten beschouwing gelaten)

Verder vind ik de termen "compiletime-" en "runtime-casts" een beetje vaag eigenlijk. In feite zijn alle casts (met uitzondering van dynamic_cast) compiletime omdat het type @ compile-time bepaald wordt. Alleen dynamic_cast kijkt @ run-time naar het daadwerkelijke type van een object, wat alleen maar kan als dat object polymorph is (dus virtual functies heeft)

[curry684]

.oisyn schreef op 02 maart 2004 @ 17:52:
Alleen dynamic_cast kijkt @ run-time naar het daadwerkelijke type van een object, wat alleen maar kan als dat object polymorph is (dus virtual functies heeft)

En je RTTI enabled hebt, anders wordt alleen een vtable voor de virtuals aangemaakt en geen identificatiedata op basis waarvan een dynamic_cast kan plaatsvinden.

[.oisyn]

Wat ik een rare opmerking vindt aangezien het uit kunnen zetten van RTTI meer een compiler-extension is imho

[curry684]

.oisyn schreef op 02 maart 2004 @ 19:20:
Wat ik een rare opmerking vindt aangezien het uit kunnen zetten van RTTI meer een compiler-extension is imho

In VS6, VS7.0 en VS7.1 staat het default uit voor nieuwe projecten

[JeRa]

Soultaker schreef op 02 maart 2004 @ 14:04:
Het voorbeeld gaat dus goed omdat alle operands tenminste naar ints worden geconverteerd. In het algemeen heb je niet zo veel geluk, ben ik bang. Ik krijg voor code als:

C++:

int foo(int a, int b)
{
        return (a*b)/65536;
}

geen enkele waarschuwing, terwijl er wel degelijk 'potential overflow' optreedt (als a*b niet meer in een int past).

Waarom is daar wel een potential overflow mogelijk en in die andere code niet? Ik vermenigvuldig immers ook een int16 met een unsigned char, en 255 * 32768 levert toch ook een overflow op? Als het delen door 255 dit voorkomt, waarom werkt dit dan niet bij jouw stukje code?

[curry684]

JeRa schreef op 02 maart 2004 @ 19:29:
[...]

Waarom is daar wel een potential overflow mogelijk en in die andere code niet? Ik vermenigvuldig immers ook een int16 met een unsigned char, en 255 * 32768 levert toch ook een overflow op?

Echter, lees dat linkje eens wat ik een stuk hierboven gaf. Bij een vermenigvuldiging worden beide operanden indien nodig gepromoveerd tot een integer, wat bij jou een overflow voorkomt.

[.oisyn]

curry684 schreef op 02 maart 2004 @ 19:25:
[...]

In VS6, VS7.0 en VS7.1 staat het default uit voor nieuwe projecten

En je punt is...

[ Voor 43% gewijzigd door .oisyn op 02-03-2004 19:55 ]

[curry684]

.oisyn schreef op 02 maart 2004 @ 19:54:
[...]
En je punt is...

Dat iets geen echte extension is als de grootste compiler het standaard toepast

[.oisyn]

Het ging er mij om dat als je gewoon over C++ praat wel enigszins kunt aannemen dat het aan staat, en niet dat een een of andere compiler het standaard uit heeft staan (het gaat tenslotte niet om die compiler)

Je zegt toch ook nooit in topics over exceptions dat je dat wel aan moet zetten? Of iets met for-scope conformance?

[RickN]

curry684 schreef op 02 maart 2004 @ 19:52:
[...]

Echter, lees dat linkje eens wat ik een stuk hierboven gaf. Bij een vermenigvuldiging worden beide operanden indien nodig gepromoveerd tot een integer, wat bij jou een overflow voorkomt.

Behalve als je een evil compiler from hell hebt, waarin de precision van char en short zo gekozen zijn dat het niet past.

[.oisyn]

curry684 schreef op 02 maart 2004 @ 19:52:
[...]

Echter, lees dat linkje eens wat ik een stuk hierboven gaf. Bij een vermenigvuldiging numerical operator worden beide operanden indien nodig gepromoveerd tot een integer, wat bij jou een overflow voorkomt.

[MSalters]

Soultaker schreef op 02 maart 2004 @ 14:04:Ik krijg voor code als:

code:

int foo(int a, int b)
{
        return (a*b)/65536;
}

geen enkele waarschuwing, terwijl er wel degelijk 'potential overflow' optreedt (als a*b niet meer in een int past).

En hoe wou je dat wel schrijven zodat het altijd past en het goede resultaat oplevert? Hint: (a/65536)*b en (a/256)*(b/256) zijn het niet.

[Soultaker]

curry684's uitspraak is een specifiekere versie dan de algemene regel, maar daarom niet minder juist. Hij heeft gelijk dat bij een vermenigvuldiging indien nodig naar een integer wordt geconverteerd; dat betekent niet dat dat bij een andere operatie of zonder noodzaak niet zou gebeuren.

[.oisyn]

Hoe zou je "indien nodig" dan defnieren?

C++:

bool indienNodig () { return true; }

zoeits?

[Soultaker]

Wel inline, hè!

[curry684]

Soultaker schreef op 02 maart 2004 @ 23:04:
curry684's uitspraak is een specifiekere versie dan de algemene regel, maar daarom niet minder juist. Hij heeft gelijk dat bij een vermenigvuldiging indien nodig naar een integer wordt geconverteerd; dat betekent niet dat dat bij een andere operatie of zonder noodzaak niet zou gebeuren.

En op het andere puntje heeft ie ook geen gelijk, want die 'indien nodig' betreft namelijk een kleiner data type dan een int, een long long of een int worden namelijk niet gepromoveerd

.oisyn moet slapie slapie gaan doen

[.oisyn]

Nee jij, want "promotion" impliceert een ophoging kwa rang, dus dat had sowieso al geen long kunnen zijn

.edit: bovendien ging het altijd nog om een char en een short

[ Voor 27% gewijzigd door .oisyn op 03-03-2004 00:02 ]

[curry684]

.oisyn schreef op 02 maart 2004 @ 23:59:
Nee jij, want "promotion" impliceert een ophoging kwa rang, dus dat had sowieso al geen long kunnen zijn

Ergo hij wordt niet gepromoveerd, ergo de 'indien nodig' stond daar goed

* curry684 trapt dit topic van Programming & Webscripting naar Nederlands & Mierenneuken

[ Voor 4% gewijzigd door curry684 op 03-03-2004 00:01 ]

[curry684]

.oisyn schreef op 02 maart 2004 @ 23:59:
.edit: bovendien ging het altijd nog om een char en een short

Maar hij vroeg het verschil met Soultaker's code die wel 2 int's gebruikte

[.oisyn]

Dan blijft het nog altijd over een char en een short gaan

offtopic:
wat een gelul weer, zo eens de bezem door de topic heen halen

[ Voor 10% gewijzigd door .oisyn op 03-03-2004 00:06 ]

[RickN]

MSalters schreef op 02 maart 2004 @ 23:04:
[...]

En hoe wou je dat wel schrijven zodat het altijd past en het goede resultaat oplevert? Hint: (a/65536)*b en (a/256)*(b/256) zijn het niet.

(a*b)/c

=

c*(a/c)*(b/c) + (a/c)*(b%c) + (b/c)*(a%c) + ((a%c)*(b%c))/c

=

(a/c)*b + (b/c)*(a%c) + ((a%c)*(b%c))/c

Ook niet echt relaxed....

[ Voor 7% gewijzigd door RickN op 03-03-2004 00:21 ]

[.oisyn]

RickN schreef op 03 maart 2004 @ 00:15:
Ook niet echt relaxed....

[edit: hier stond eerst onzin]
Mwoa, je zou er nog een paar weg kunnen werken

C++:

int foo (int a, int b) 
{ 
        return a * (b / 65536) + (a * (b % 65536)) / 65536; 
}

(maar het leek dan ook wel verdacht veel op fixed point math )

[ Voor 83% gewijzigd door .oisyn op 03-03-2004 03:41 ]

[MSalters]

Ik ben bang dat dat het algoritme is voor unsigned int. Volgens mij is -1 % 65536 implementation-defined.

[curry684]

MSalters schreef op 03 maart 2004 @ 11:08:
Ik ben bang dat dat het algoritme is voor unsigned int. Volgens mij is -1 % 65536 implementation-defined.

Lijkt me toch van niet, daar dat wiskundig vastligt. -1 gedeeld door 65536 is 0 met een rest van -1, oftewel die modulus hoort -1 te zijn. Ik zou niet weten welk ander resultaat je eruit wil krijgen

[RickN]

Er valt ook wel iets te zeggen voor -1, met een rest van 65535.

Tis maar net wat je defineert, div rond af naar 0, of een rest is altijd positief...

Waarmee ik overigens niet wil zeggen dat ik weet of de C standaard hier iets specificeert.

edit:
Maar mijn oude algebra dictaat zegt wel: "Als a in Z en b in Z\{0}, dan zijn er precies één q in Z en één r in Z zó dat a = qb + r en 0 <= r < |b|."
Een positieve rest dus...

[ Voor 63% gewijzigd door RickN op 03-03-2004 16:44 ]

[Soultaker]

Het lijkt me dat je er voor wil garanderen dat: a == ((a/b)*b + (a%b)) (voor elke a en b), want dat is een essentiële eigenschap van integer division/modules waar je allerlei rekenregels op kunt baseren.

Kies je voor a=2, b=3, dan moet 2%3 (logisch genoeg 2) zijn, aangezien (2/3) als 0 is. Als je echter a=-2 kiest, dan is (-2/3) nog steeds 0, en dus moet de (-2%3) wel -2 zijn. De rest hoeft dan dus niet postief te zijn.

Om er maar een tweede redenatie tegenaan te gooien: het ligt ook voor de hand om de rest r te definiëren als: r = a - (a/b)*b. Als je dan modulus implementeert met behulp van die deling, dan krijg je voor a=-2 en b=3 ook weer netjes -2.

Ik las hier trouwens dat de manier van deling voor ANSI C niet gespecificeerd is, maar dat de manier die hierboven beschreven werd het meest wordt toegepast en daarom overgenomen is in ANSI C99.

[RickN]

Hét argument om deze definitie aan te houden vind ik dat nu |a/b|=|a|/|b| is (wat de enige reden is dat het "logisch" is dat -2/3 = 0). Verder is / nu een deling die afrond naar nul, wat waarschijnlijk eenvoudiger te implementeren is dan een deling die afrond richting min oneindig.

Maar ik vind het niet de netste manier om tot een definitie van a/b en a%b te komen.

Laten we eens alleen uitgaan van:

a = b*(a/b) + (a%b)

Omdat / en % toch nog niet gedefineert zijn vervang ik dit even door:

a = b*q + r

Voor willekeurige a en b zijn er nu oneindige veel paren (q,r) die aan bovenstaande gelijkheid voldoen. Als we willen dat / en % deterministisch zijn zullen we moeten zorgen dat q en r voor elke a en b uniek bepaald zijn.
Hoe? Nou, je zou b.v. q kunnen gaan beperken, maar dat lukt alleen door voor q een vaste waarde waarde te kiezen, alleen dan is r uniek bepaald. Dit is niet erg zinvol, dus laten we proberen r te beperken. Eerste poging:

a = b*q + r /\ -|b| < r < |b|

Is q nu uniek bepaald?
Duidelijk niet, voor (a,b)=(6,4) voldoen zowel (q,r)=(1,2) als (q,r)=(2,-2) en voor (a,b)=(-6,4) voldoen zowel (q,r)=(-1,-2) als (q,r)=(-2,2). Hoe lossen we deze ambiguiteit op? We zouden nu als nog q kunnen gaan beperken met een regel als "q zo dicht mogelijk bij 0". Ik vind het echter netter om r nu nog verder te beperken. -|b| < r <= 0 zou voldoen, maar dan blijkt % niet meer gesloten te zijn in N. Echter met:

a = b*q + r /\ 0 <= r < |b|

zijn q en r uniek waarmee / en % deterministisch gedefineerde (en gesloten) operaties zijn in N en Z.

[ Voor 6% gewijzigd door RickN op 03-03-2004 15:33 ]

[.oisyn]

MSalters schreef op 03 maart 2004 @ 11:08:
Ik ben bang dat dat het algoritme is voor unsigned int. Volgens mij is -1 % 65536 implementation-defined.

a * (b >> 16) + (a * (b & 65535) >> 16)

Voor een vermenigvuldiging maakt het niet uit of het signed of unsigned is: het resultaat (bitpatroon) blijft hetzelfde

Even rekenen: (-12345 * 56789) / 65536 = -10697
-12345 * (56789 >> 16) + (-12345 * (56789 & 65535) >> 16) = -10698

Hmm ok, het verschilt 1

if (result < 0) result++;
(of je moet er gewoon nog ((a ^ b) >> 31) & 1 bij optellen, dan ben je ook klaar

.edit: hmm ik denk alleen dat je dan in de problemen komt bij -65536 < b < 0, aangezien het resultaat van die shift dan -1 oplevert ipv 0. Maar je zou in dat geval natuurlijk ook gewoon delingen kunnen gebruiken ipv shifts

[ Voor 23% gewijzigd door .oisyn op 03-03-2004 16:07 ]

[curry684]

Two words: long long

[.oisyn]

Mja ik vond dat nogal flauw en denk niet dat MSalters dat bedoelde met z'n vraag (vergelijkbaar probleem: wat als je nu hetzelfde probeert de doen met long long?)

[RickN]

Als -1%x niet gespecificeert wordt in de C standaard, dan is -1/x dat ook niet vanwege de gelijkheid a = b*(a/b) + a%b .
Dus als -1%x niet gespecificeert is, is (a*b)/65536 dat ook niet voor unsigned int.

Als -1%x wel gespecificeerd is, kun je het algorithm voor signed int gebruiken maar moet je er voor unsigned int's afhankelijk van de precieze specificatie wel of niet 1 van aftrekken.

[ Voor 10% gewijzigd door RickN op 03-03-2004 16:41 ]

[.oisyn]

quote: http://www.kuzbass.ru:8086/docs/isocpp/expr.html#expr.mul

-4- The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined*.

[Footnote: According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero. --- end foonote]