C: Bithack geht nicht

Nop Gast #6442405
Lesenswert?
• ▲
▼ 
Es geht um eine Popcount-Routine mit Bit-Twiddling. Die funktioniert 
auch, aber nicht mehr, wenn man die Konstanten alle mit dem Suffix UL 
als unsigned long markiert, obwohl das gehen sollte. Gemäß integer 
promotion müßte das IMO ohnehin nach UL (32 bit) promoted werden.

Drei Versionen: die erste ohne Suffixe, die zweite soweit, daß es noch 
geht, die dritte geht nicht mehr. Also wenn man in der Zeile mit der 
Multiplikation nicht nur U, sondern UL hinzufügt (egal zu welcher der 
Konstanten), scheitert es mit verkehrtem Ergebnis.

Getestet mit GCC 9.3.0 64 Bit unter Linux, keine Warnungen erschienen.

1
/*

2
  compile with: gcc -O0 -std=c99 -Wall -Wextra

3
  see Bit Twiddling Hacks:

4
  https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

5
*/

6


7
#include <stdint.h>

8
#include <stdio.h>

9


10
/*works*/

11
uint32_t popcnt_1(uint32_t v) {

12
    v = v - ((v >> 1) & 0x55555555);

13
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);

14
    return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;

15
}

16


17
/*works*/

18
uint32_t popcnt_2(uint32_t v) {

19
    v = v - ((v >> 1) & 0x55555555UL);

20
    v = (v & 0x33333333UL) + ((v >> 2) & 0x33333333UL);

21
    return (((v + (v >> 4)) & 0xF0F0F0FU) * 0x1010101U) >> 24;

22
}

23


24
/*wrong result*/

25
uint32_t popcnt_3(uint32_t v) {

26
    v = v - ((v >> 1) & 0x55555555UL);

27
    v = (v & 0x33333333UL) + ((v >> 2) & 0x33333333UL);

28
    return (((v + (v >> 4)) & 0xF0F0F0FUL) * 0x1010101UL) >> 24;

29
}

30


31
int main (void) {

32
    printf("1: 0xFF00 ones: %u\n", popcnt_1(0xFF00UL)); /*result: 8*/

33
    printf("2: 0xFF00 ones: %u\n", popcnt_2(0xFF00UL)); /*result: 8*/

34
    printf("3: 0xFF00 ones: %u\n", popcnt_3(0xFF00UL)); /*result: 2056*/

35
    return 0;

36
}
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Nop Gast #6442428
Lesenswert?
• ▲
▼ 
Egon D. schrieb:
> Nop schrieb:
>
>> UL (32 bit)
>
> ???
>
>> Getestet mit GCC 9.3.0 64 Bit unter Linux,
> .........................^^^^^^

Ah, danke. Mir war nicht klar, daß "long" 64 Bit hat unter einem 
64-Bit-Linux. Der Code kam von einem Windowssystem mit 64 Bit, wo "long" 
nur 32 Bit hat.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Nop Gast #6442563
Lesenswert?
• ▲
▼ 
Rolf M. schrieb:
> Wenn's ein uint32_t sein soll, nimmt man am besten
> UINT32_C(0x55555555).
> Dann macht der Präprozessor den auf dem System passenden Suffix draus.

Auch ein interessanter Tip, gerade für solche Bithacks.

Wobei einfach nur U als Suffix ja im Normalfall ohnehin passend promoten 
sollte, selbst wenn man auf einem System mit int als 16 Bit ist, da 
müßte das dann nach unsigned long gehen. Also, auch ohne daß es wie hier 
zusammen mit einem uint32_t in einem Ausdruck steht.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Michael X. Gast #6442804
Lesenswert?
• ▲
▼ 
Nop schrieb:
> Rolf M. schrieb:
>> Wenn's ein uint32_t sein soll, nimmt man am besten
>> UINT32_C(0x55555555).
>> Dann macht der Präprozessor den auf dem System passenden Suffix draus.
>
> Auch ein interessanter Tip, gerade für solche Bithacks.

Allgemein sind die Makros in <stdint.h> einen Blick wert. Manche sind 
zwar richtig hässlich, aber wenn mans brauch ist man trotzdem froh.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Walter T. #6442988
Lesenswert?
• ▲
▼ 
Nop schrieb:
> Das mache ich schon, wenn eine entsprechende Build-Option mitgegeben
> wurde. Das Bitgeschubse ist der Fallback, wenn nicht.

Semi-OT: Wie machst Du die Auswahl, welche Lösung verwendet wird? Bei 
mir sieht das oft unschön aus:

1
    static_inline uint8_t ctz(unsigned int x)

2
    {

3
        #if (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)

4
            return __builtin_ctz(x);

5
        #else

6
            /* Bitwise binary search */

7
            /* Quelle https://graphics.stanford.edu/~seander/bithacks.html */

8
            unsigned int c = 32; /* c will be the number of zero bits on the right */

9
            x &= -signed(x);

10
            if (x) c--;

11
            if (x & 0x0000FFFF) c -= 16;

12
            if (x & 0x00FF00FF) c -= 8;

13
            if (x & 0x0F0F0F0F) c -= 4;

14
            if (x & 0x33333333) c -= 2;

15
            if (x & 0x55555555) c -= 1;

16
            return c;

17
        #endif

18
    }
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Nop Gast #6443226
Lesenswert?
• ▲
▼ 
Walter T. schrieb:

> Semi-OT: Wie machst Du die Auswahl, welche Lösung verwendet wird?

Ich verwende die portable Lösung als Default, wenn kein entsprechendes 
define über die Buildchain gesetzt ist. Die Auto-Detection wie in Deinem 
Beispiel nehme ich nicht, weil ich das manuell kontrollieren will.

Das brauche ich z.B., wenn ich im Mockup auf dem Host teste, der popcnt 
unterstützt, aber die spätere embedded-Anwendung auf einer Plattform 
laufen soll, die das nicht tut. Zugleich bekomme ich eine Vorstellung, 
wieviel Geschwindigkeitsgewinn in der konkreten Anwendung denn über 
natives popcnt drin wäre.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren