Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

[C++] Bitweise Reloaded - Zuverlässiges Overflow/Underflow?

Werbeanzeige

Schrompf

Alter Hase

  • »Schrompf« ist der Autor dieses Themas

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

1

11.12.2015, 12:01

[C++] Bitweise Reloaded - Zuverlässiges Overflow/Underflow?

Tach,

ja, ich wieder. Ich weiß, dass Integer-Overflow und -Underflow nach C++-Standard Unspecified Behavior sind. Leider würde es mir bei einigen meiner zentralen Bitschubsereien sehr nützen, wenn ich mich auf Zweierkomplement-Effekte verlassen könnte.

Beispiel:

C-/C++-Quelltext

 
1
2
3

uint64_t MachEinser(size_t numBits) { 
  return (uint64_t( 1ull) << numBits) - uint64_t( 1); 
}


Mit numBits == 4 z.B. ergibt das Bitschieben ein b00010000, das minus eins ergibt dann b00001111 - prima. Mit numBits == 64 sprengt der Bitschieber den Integertyp und ergibt 0, das minus eins ergibt dann das gewünschte 0xffffffffffffffff. Aber nur, wenn man sich auf den Overflow/Underflow verlassen kann. Oben zitierte Funktion ergibt hier auf Ubuntu 12 und dem GCC 4.8 für numBits == 64 eine 0. Und 0 ist falsch.

Die Frage lautet also: gibt es irgendwelche Tricks, mit denen ich dem Compiler beibringen kann, Zweierkomplement-Magie zuverlässig auszuführen? Danke.

Randnotiz: das ist wieder ein Parallelpost, der (aktuell noch leere) Thread auf dem ZFX findet sich unter http://zfx.info/viewtopic.php?f=4&t=3928
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

2

11.12.2015, 14:44

~?
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Schrompf

Alter Hase

  • »Schrompf« ist der Autor dieses Themas

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

3

11.12.2015, 15:03

Falls Du mit diesem Minimalschnippsel meinst, ich solle es so umbauen:

C-/C++-Quelltext

 
1

 return ~0ull >> (64 - numBits);


Dann hast Du dabei leider nicht bedacht, dass damit das Scheitern nur auf numBits == 0 verschoben wird. Es gibt aber in jedem Fall einen Wert, für den die Funktion scheitert. Ich habe inzwischen gelernt, dass Overflow und Underflow für unsigned-Typen wohl spezifiziert sind. Mein Problem mit obigem Code ist nicht der Underflow, sondern der Bitshift. Laut zum Beispiel diesem Link maskiert der x86-Shift die Schubweite. Ein (bla << 64) ist also identisch zu (bla << 0), was dann erklären würde, warum obige Funktion für numBits==64 0 ergibt. Anscheinend hat der Visual Studio-Compiler die ganze Zeit zusätzlichen Code eingefügt, um sicherzustellen, dass der Bitshift für Schubweite>63 das erwartete Ergebnis bringt. Interessant.

Meine aktuelle Version nutzt nach ein paar klugen Hinweisen auf dem ZFX nun ein banales Conditional Move, wovon ich mir erhoffe, dass es die Pipeline nicht allzu heftig ausbremst.

C-/C++-Quelltext

 
1

 return (numBits == 0) ? 0 : (~0ull >> (64 - pAnzahl));


Alternativ könnte man eine Bitschubserei ohne Bedingung konstruieren, die zumindest bis numBits < 128 noch stabil funktioniert.

C-/C++-Quelltext

 
1

 return (uint64_t( (~numBits & 64) >> 6)) << (numBits & 63)) - uint64_t( 1);


Aber es kann gut sein, dass die zusätzlichen Datenabhängigkeiten wieder irgendwelche Pipeline Stalls auslösen... das ist dann Detailkampf, den ich mir nochmal anschaue, wenn das Gesamtprojekt dann soweit ist, dass realistische Datensätze zur Verfügung stehen.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Koschi

Alter Hase

Beiträge: 657

  • Private Nachricht senden

4

11.12.2015, 17:38

Weiß nicht ob das Hilft (wahrscheinlich zuviele Rechenschritte).
- anstatt b0001 x mal zu schieben b1111 x mal schieben (einfachhalber mal nur 4 bit)
- sagen wir numBit ist 2 dann ist das Ergbnis b1100
- das dann über nand verknüpfen mit b1111 und raus kommt b0011

Ich meine das Rausschieben der 1er über das Register hinaus sollte definiertes Verhalten sein.

Gruß Koschi
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

5

11.12.2015, 20:24

Wie wär's damit:

C-/C++-Quelltext

 
1
2
3
4
5
6
7

template <typename T>
inline constexpr std::enable_if_t<std::is_unsigned<T>::value, T> gimme(int n)
{
    return ~(~T() << n);
}

auto x = gimme<unsigned>(5);


;)
m4studios

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »dot« (11.12.2015, 20:46)

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

12.12.2015, 04:40

Nach weiterer Diskussion auf ZFX, sollte ich wohl auch hier darauf hinweisen, dass meine Lösung da oben für n = 64 leider ebenfalls undefined Behavior gibt, hatte da was übersehen...
m4studios

Schrompf

Alter Hase

  • »Schrompf« ist der Autor dieses Themas

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

7

12.12.2015, 12:44

Trotzdem Dankeschön euch allen, ich habe schon wieder mächtig viel gelernt! Allein das war's wert.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Werbeanzeige

Ähnliche Themen