[C] Overflow / Halfflow

[Verwijderd]

Klopt het dat in C geen goede overflow en carry detectie beschikbaar is?
Ik heb het nu maar opgelost door van de most significant bit van een unsigned int een halfflow bit te maken. Als die gezet word door maximaal een positively signed maxint te stoppen in de unsigned int, dan weet ik dat ik over de helft ben gegaan. Ik wil geen signed int gebruiken, want dan doen optellingen het niet meer goed.
Maar dit is eigenlijk een beetje inefficient, toch?

[RobIII]

Euh... ik krijg kortsluiting in mijn hersenpan bij het lezen van je topic.
<snip>laat maar, ik begrijp 't denk ik al</snip>

edit:
Hoe langer ik nadenk over je topic hoe beter ik het dénk te begrijpen: je wil een overflow exception ofzo hebben denk ik?

[ Voor 131% gewijzigd door RobIII op 25-12-2009 01:36 ]

[.oisyn]

Verwijderd schreef op vrijdag 25 december 2009 @ 01:14:
Klopt het dat in C geen goede overflow en carry detectie beschikbaar is?

Het klopt dat die informatie sowieso niet beschikbaar is nee. Op welk platform werk je?

Ik wil geen signed int gebruiken, want dan doen optellingen het niet meer goed.

In 2's complement, wat de meeste processoren zijn, is een signed optelling binair gezien exact identiek aan een unsigned optelling. Er bestaat dan ook maar 1 instructie voor.

RobIII schreef op vrijdag 25 december 2009 @ 01:19:
Feitelijk is een signed/unsigned int precies het zelfde: Een bak bits. Alleen geef jij, voor jezelf en de programmeertaal, er een (un)signed betekenis aan. Is een int unsigned dan is het MSB gewoon een extra bit, is een int signed dan geeft het, wanneer 1, een negatieve waarde aan. Wanneer een signed int dus overflowed boeit dat voor de CPU niet en tel je feitelijk gewoon verder

Onjuist, het boeit de CPU in zoverre dat hij de juiste flags zet. Als je op x86 een CMP doet, wat feitelijk gewoon een SUB is zonder het resultaat op te slaan, dan worden overflow, zero en carry flags ingesteld. De overflow betekent dat ie als signed int is ondergelopen, en de carry betekent dat ie als unsigned int is ondergelopen. En daarom zijn JA (jump above) en JG (jump greater) bijv. niet hetzelfde - de eerste kijkt naar de carry flag en gebruik je voor unsigned compares, en de tweede naar de overflow flag en gebruik je voor signed compares. De bits in een int hebben voor de CPU dus weldegelijk meer betekenis dan alleen een zooi bits.

[ Voor 52% gewijzigd door .oisyn op 25-12-2009 01:36 ]

[RobLemmens]

Helaas is dat de trade off die je moet maken, performance of kwaliteit van resultaat (of hoe je ook noemt) In veel situaties weet je wel wanneer een int enigzins kans heeft op overflowen of niet, sommige weet je zeker van niet... licht er vooral aan wat je aan het berekenen bent. Vooral met data van buitenaf altijd op safe spelen. In asm kun je overigens die ifstatements goed weg moffelen als ik het goed heb en dan zou die performance inpact best mee moeten vallen. Waarschijnlijk dat je compiler dat reeds doet in release? Test het.

[Verwijderd]

Wat ik wil bereiken is dat overflow kan, dat ik dat zie, dat ik dat aantal bijhoudt in een 2e veld, dat ik de maxbeforecarry van het eerste veld afhaal zodat ik verder kan met optellen maar het getal nog steeds klopt.
Wat ik nu gedaan heb is tot de helft gaan van een unsigned int, waarbij MSB gezet word als het over de helft van unsignedmaxint heen gaat. Het enige wat ik dan doe is het clearen van MSB in veld1 en ik tel een bitje op bij veld2. De MSB wordt dan een halfflow bit en mijn MSB is dan MSB-1 (bit 31).

[ Voor 10% gewijzigd door Verwijderd op 25-12-2009 01:41 ]

[RobIII]

.oisyn schreef op vrijdag 25 december 2009 @ 01:29:
Onjuist, het boeit de CPU in zoverre dat hij de juiste flags zet.

Euh, uiteraard. Die dingen hebben wel degelijk nut ja Dat status register is er niet voor niks

.oisyn schreef op vrijdag 25 december 2009 @ 01:29:
De bits in een int hebben voor de CPU dus weldegelijk meer betekenis dan alleen een zooi bits.

Zo letterlijk bedoelde ik 't ook niet. De overflow flag wordt bij elke rekenkundige bewerking (wanneer nodig) bijgewerkt. En dat is telkens wanneer de MSB van waarde wisselt. (En zo zijn er nog een paar bewerkingen die volgens mij de overflow flag (V) bijwerken als ik me niet vergis en uiteraard een aantal instructies die 'm ook weer clearen).

Verwijderd schreef op vrijdag 25 december 2009 @ 01:37:
Wat ik wil bereiken is dat overflow kan, dat ik dat zie, dat ik dat aantal bijhoudt in een 2e veld, dat ik de maxbeforecarry van het eerste veld afhaal zodat ik verder kan met optellen maar het getal nog steeds klopt.
Wat ik nu gedaan heb is tot de helft gaan van een unsigned int, waarbij MSB gezet word als het over de helft van unsignedmaxint heen gaat. Het enige wat ik dan doe is het clearen van MSB in veld1 en ik tel een bitje op bij veld2. De MSB wordt dan een halfflow bit en mijn MSB is dan MSB-1 (bit 31).

Dat maakt al wat meer duidelijk Is 't niet handiger in jouw geval, gezien je om performance verlegen zit, gewoon een groter datatype te nemen? (Natuurlijk afhankelijk van wat er mogelijk is op je platform e.d.).

[ Voor 33% gewijzigd door RobIII op 25-12-2009 01:43 ]

[.oisyn]

@dash: Ik snap niets van je verhaal, behalve de laatste zin, waarvan ik kan vertellen dat dat onzin is. Zoals ik al zei, een signed optelling is exact equivalent aan een unsigned optelling. Heb je niet gewoon een stukje code wat je kunt laten zien?

[ Voor 14% gewijzigd door .oisyn op 25-12-2009 01:43 ]

[Verwijderd]

.oisyn schreef op vrijdag 25 december 2009 @ 01:42:
@dash: Ik snap niets van je verhaal, behalve de laatste zin, waarvan ik kan vertellen dat dat onzin is. Zoals ik al zei, een signed optelling is exact equivalent aan een unsigned optelling. Heb je niet gewoon een stukje code wat je kunt laten zien?

Ja daar heb ik nu ook het licht van gezien.
Praktische vraag: gaat het weghalen van de sign bit van een signed int (zodat het positief wordt) eenvoudig? Of gaat dat net zo als bij een unsigned int (met bit = number & (1 << x))?

[RobIII]

Verwijderd schreef op vrijdag 25 december 2009 @ 01:47:
[...]

Ja daar heb ik nu ook het licht van gezien.
Praktische vraag: gaat het weghalen van de sign bit van een signed int (zodat het positief wordt) eenvoudig?

Casten naar unsigned int. Oftewel: zelfde bak bits, anders bekeken/geïnterpreteerd
Als je de MSB wil clearen kan dat door te AND-en met max_signedint.

code:

10010110
01111111 &
=========
00010110

Even met een byte gedaan, was te lui om nog meer enen en nullen te typen In jouw geval (32 bits) is de "x" in je voorbeeld dus 31. Ik zou mezelf echter dan de lsh operatie besparen en (1<<31) vervangen door een const.

[ Voor 24% gewijzigd door RobIII op 25-12-2009 02:07 ]

[Verwijderd]

RobLemmens schreef op vrijdag 25 december 2009 @ 01:31:
Waarschijnlijk dat je compiler dat reeds doet in release? Test het.

Wat bedoel je precies hiermee?
Ik weet niet wat je bedoelt maar wil het graag testen, als ik hiermee carry detectie kan doen met een unsigned int in C.

[Verwijderd]

RobIII schreef op vrijdag 25 december 2009 @ 01:52:
[...]
Casten naar unsigned int. Oftewel: zelfde bak bits, anders bekeken/geïnterpreteerd

Dien ik ze te casten? Kan ik niet simpelweg de MSB weghalen als het <0 blijkt geworden?

Als je de MSB wil clearen kan dat door te AND-en met max_signedint.

code:

10010110
01111111 &
=========
00010110

Even met een byte gedaan, was te lui om nog meer enen en nullen te typen

== ( number = number & (1 << MSB) ) ?

Maar eigenlijk zou ik gewoon een unsigned int willen gebruiken en die carry kunnen willen detecteren. Zo vreemd dat dat niet kan. Ik bedoel de rest kan wel en dan zou dit niet kunnen.

[RobIII]

Verwijderd schreef op vrijdag 25 december 2009 @ 02:06:

== ( number = number & (1 << MSB) ) ?

Nee, jij cleared nu alles behalve de MSB

number &= 2147483647
of
number &= ~(1<<31)
of
verzin iets creatiefs


Maar ik zie even niet waarom je 'm eigenlijk nou zo graag wil clearen. Kun je eens war duidelijker uitleggen wat je aan 't maken bent, wat je wil bereiken enzo? Dus wat minder abstract? Mijn water zegt me dat je misschien wel eens een verkeerde afslag ergens zou kunnen hebben genomen en wellicht is de oplossing voor je eigenlijke probleem nog wel veel makkelijker dan je denkt.

[ Voor 64% gewijzigd door RobIII op 25-12-2009 02:16 ]

[.oisyn]

Als het je puur gaat om het detecteren van de carry flag moet je gewoon kijken of (a+b < a) waarbij zowel a als b unsigned zijn. Het detecteren van de overflow flag kan met ((a+b) ^ ~(a^b)) & ~INT_MAX

.edit: zo, volgens mij klopt ie nu eindelijk
.edit2: hmmnee toch niet. Maar het ging je blijkbaar toch alleen om de carry

.edit3: ((a+b) ^ a & (~a ^ b) & ~INT_MAX

[ Voor 52% gewijzigd door .oisyn op 25-12-2009 02:30 ]

[Verwijderd]

.oisyn schreef op vrijdag 25 december 2009 @ 02:09:
Als het je puur gaat om het detecteren van de carry flag moet je gewoon kijken of (a+b < a) waarbij zowel a als b unsigned zijn. Het detecteren van de overflow flag kan met ((a+b) & ~(a^b)) & ~INT_MAX

Inderdaad, dat is het gewoon. Thanks!
Carry detecteren zonder de carry uit te lezen :-)
Maar iets zegt me dat als er een call was om simpelweg die carry te kunnen lezen het mogelijk minder werk zou zijn voor de cpu.

[ Voor 20% gewijzigd door Verwijderd op 25-12-2009 02:21 ]

[Verwijderd]

RobIII schreef op vrijdag 25 december 2009 @ 02:09:
[...]

Nee, jij cleared nu alles behalve de MSB

number &= ~(1<<31)

Ahja dit is hem :-)

verzin iets creatiefs

Ik word zo onderhand een geconditioneerde loonslaaf in onze nabijtoekomstige Big Brother DDR2 staat. Creativiteit wordt niet beloond

Maar ik zie even niet waarom je 'm eigenlijk nou zo graag wil clearen. Kun je eens war duidelijker uitleggen wat je aan 't maken bent, wat je wil bereiken enzo? Dus wat minder abstract? Mijn water zegt me dat je misschien wel eens een verkeerde afslag ergens zou kunnen hebben genomen en wellicht is de oplossing voor je eigenlijke probleem nog wel veel makkelijker dan je denkt.

Ik wil een flexibel datatype maken die de komende honderd miljoen miljard jaar niet tegen zijn plafond aanloopt.

[.oisyn]

Als je dan gewoon had gezegd dat je additions met carry wilde doen

[RobIII]

Verwijderd schreef op vrijdag 25 december 2009 @ 02:29:
Ik wil een flexibel datatype maken die de komende honderd miljoen miljard jaar niet tegen zijn plafond aanloopt.

Dat is natuurlijk nogal afhankelijk van hoe vaak je 'm ophoogt (even uitgaande van een 'teller'). Een 32bits int kun je al 136 jaar gebruiken als je 'm iedere seconde 1 keer ophoogt. Doe je dat 1000 keer per seconde dan kun je dus 0.136 jaar vooruit. En met een 64 bits integer kun je als je 1000 keer per seconde ophoogt ruim 584 miljoen jaar vooruit. Waarom dan geen 64 bits integer gebruiken?

[Verwijderd]

RobIII schreef op vrijdag 25 december 2009 @ 02:36:
[...]

Dat is natuurlijk nogal afhankelijk van hoe vaak je 'm ophoogt (even uitgaande van een 'teller'). Een 32bits int kun je al 136 jaar gebruiken als je 'm iedere seconde 1 keer ophoogt. Doe je dat 1000 keer per seconde dan kun je dus 0.136 jaar vooruit. En met een 64 bits integer kun je al je 1000 keer per seconde ophoogt ruim 584 miljoen jaar vooruit. Waarom dan geen 64 bits integer gebruiken?

Ik heb een 32bits pc. Maar dit zou toch niet het probleem moeten zijn, als ik een array van 32bit integers kan bewandelen. Alleen dan moet ik dus mijn eigen generieke add functies schrijven. Maar dit moest ik toch al doen, want ik was van plan een getal te kunnen definieren waarbij er een offset beschreven kan worden zodat je beknopt op kan schrijven dat de eerste honderd intjes allemaal gevuld waren met eentjes zonder daadwerkelijk honderd intjes te declareren.

[RobIII]

Verwijderd schreef op vrijdag 25 december 2009 @ 02:43:
[...]


Ik heb een 32bits pc. Maar dit zou toch niet het probleem moeten zijn, als ik een array van 32bit integers kan bewandelen. Alleen dan moet ik dus mijn eigen generieke add functies schrijven. Maar dit moest ik toch al doen, want ik was van plan een getal te kunnen definieren waarbij er een offset beschreven kan worden zodat je beknopt op kan schrijven dat de eerste honderd intjes allemaal gevuld waren met eentjes zonder daadwerkelijk honderd intjes te declareren.

Zit je nou niet een wiel opnieuw uit te vinden
Allereerst kunnen de meeste 32bits pc's prima met 64bits rekenen. Waarschijnlijk regelt je compiler het al voor je als je een 64 bits datatype declareert en gebruikt. En anders zijn er in 999 v.d. 1000 gevallen geheid allerlei "bigint" libraries voor elk denkbaar platform beschikbaar.

[ Voor 20% gewijzigd door RobIII op 25-12-2009 02:58 ]

[Verwijderd]

RobIII schreef op vrijdag 25 december 2009 @ 02:47:
Zit je nou niet een wiel opnieuw uit te vinden
Allereerst kunnen de meeste 32bits pc's prima met 64bits rekenen. Waarschijnlijk regelt je compiler het al voor je als je een 64 bits datatype declareert en gebruikt. En anders zijn er in 999 v.d. 1000 gevallen geheid allerlei "bigint" libraries voor elk denkbaar platform beschikbaar.

Kan je met die bigints delen, wat voor een ding komt er dan uit? Is die dan ook 'bigint'?

[ Voor 13% gewijzigd door RobIII op 25-12-2009 03:00 . Reden: quote/edit/quote/whoops :+ ]

[RobIII]

Verwijderd schreef op vrijdag 25 december 2009 @ 02:52:
[quote]RobIII schreef op vrijdag 25 december 2009 @ 02:47:
[...]

[...]

Kan je met die bigints delen, wat voor een ding komt er dan uit? Is die dan ook 'bigint'?

Wikipedia: Arbitrary-precision arithmetic

[Verwijderd]

Verwijderd schreef op vrijdag 25 december 2009 @ 02:52:

[...]

Kan je met die bigints delen, wat voor een ding komt er dan uit? Is die dan ook 'bigint'?

En kan ik er dan ook bitwise operations op uitvoeren?

[ Voor 17% gewijzigd door RobIII op 25-12-2009 02:59 ]

[RobIII]

Verwijderd schreef op vrijdag 25 december 2009 @ 02:57:
[...]

En kan ik er dan ook bitwise operations op uitvoeren?

Ja zeg, ga eens lekker wat documentatie doorlezen. We zitten hier niet om iedereen aan 't handje te houden...
We verwachten hier op GoT wel wat eigen initiatief en inzet en het is niet de bedoeling om voor ieder akkefietje weer een post te maken en je vraag te dumpen.

[ Voor 22% gewijzigd door RobIII op 25-12-2009 03:02 ]