Den Durchschnitt von zwei `unsigned int` ohne Overflow berechnen
(devblogs.microsoft.com)- Addieren und dann durch 2 teilen verursacht Overflow
→ (a + b) / 2
- Wenn man die größere der beiden Zahlen kennt, kann man auch die Differenz der beiden Werte zur kleineren Zahl addieren und dann durch 2 teilen
→ low + (high - low) / 2
- Ein Algorithmus, der auch funktioniert, ohne zu wissen, welche Zahl größer ist, wurde 2016 patentfrei
→ (a / 2) + (b / 2) + (a & b & 1)
- SWAR: SIMD within a register
→ (a & b) + (a ^ b) / 2
- Wenn der Compiler 64 Bit unterstützt, einfach casten
→ ((unsigned long long)a + b) / 2
- Und danach folgen Assembler-Codes für die einzelnen Prozessoren ... siehe Original
1 Kommentare
Raymond Chens Blog The Old New Thing behandelt ein breites Themenspektrum, von Hintergrundgeschichten zur Windows-Entwicklung bis hin zu verschiedensten anderen Themen.
In Korea erschien eine Übersetzung unter dem Titel „Raymond Chens 282 Geschichten aus der Windows-Entwicklung“, sie ist inzwischen jedoch vergriffen.