4. Gesetzte Bits im Byte zählen

Gesetzte Bits im Byte zählen

  • M

    Hi all ...

    ich habe -bg-'s Vorschlag mal umgesetzt ...

    #include <time.h>
#include <stdio.h>

typedef unsigned int u32;

u32 countBitsTrue4(u32 x)//16 takte
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & 0x3f;
    return x;
}

int tab[0xFFFF];

u32 count_bits(u32 x)
{
    x = tab[x & 0xFFFF] + tab[x>>16];

    return x;
}

#define TEST_PATTERN   0x12345678

int main(void)
{
    int i;
    clock_t before;
    double elapsed;

    for (i = 0; i < 0xFFFF; i++)
        tab[i] = countBitsTrue4(i);

    printf("x = %d\n", count_bits(TEST_PATTERN));

    before = clock();
    for (i = 0; i < 100000000; i++)
        count_bits(TEST_PATTERN);
        // countBitsTrue4(TEST_PATTERN);

    elapsed = clock() - before;
    printf("Funktion benötigte %.3lf Sekunden\n", elapsed/CLOCKS_PER_SEC);

    return 0;
}

    Die Tabellen-Variante ist um einiges schneller ... dafür muss man halt zuerst die Tabelle initialisieren ...

    0
  • M

    hihi, der is mein schnellster, den ich anzubieten habe (ohne inlining!):

    __declspec(naked) unsigned __stdcall bitcntC(unsigned v) { __asm {
     mov eax, [ESP+4]
     mov edx, eax
     shr eax, 1
     and eax, 055555555h
     sub edx, eax
     mov eax, edx
     shr edx, 2
     and eax, 033333333h
     and edx, 033333333h
     add eax, edx
     mov edx, eax
     shr eax, 4
     add eax, edx
     and eax, 00F0F0F0Fh
    imul eax, 001010101h
     shr eax, 24
     ret 4
}}

    auf meinem Athlon XP 2000+ hübsche 40 Mio. Aufrufe in einer halben sekunde. 50 ms schneller als die nicht naked version *g*

    0
  • M

    @mady: beim tabellenerstellen könntest du _viel_ *g* zeit sparen.

    0
  • E

    @-bg-: geniale idee! wie beim base64 encode!

    ich glaub dieses verfahren könnte man durchaus öfters benutzen!

    0
  • M

    ich dachte meine antwort zum table lookup (ein programm generator war das) wär lustig genug...
    (das mit "ach ja:" beginnt)

    [ Dieser Beitrag wurde am 04.09.2002 um 15:31 Uhr von Mr. n editiert. ]

    0
  • E

    damit ich auch mal mit reden kann... hat jemand eine tabelle über die takte, die bestimmte assembler anweisungen verbrauchen? hatte mal gesucht, aber nix gefunden 😞

    0
  • M

    das kommt auf deine cpu an. aber in meinem tollen link steht da auch was zu drin. textseite 259, acro-seite 279

    0
  • P

    Hast du auch schon im Forum gesucht?
    Clock-Tabelle

    lg, phreaking

    0
  • E

    nope, nur google. und bin nicht auf den begriff Clocks gekommen. Danke 🙂

    0
  • M

    Original erstellt von Mr. n:
    @mady: beim tabellenerstellen könntest du _viel_ *g* zeit sparen.

    Naja ... mir ging's erstmal darum, ein Beispiel der Tab.Variante zu zeigen.

    Normalerweise startet eine solche Initialisierung am Anfang eines Programms und damit ist das nicht so schlim, wenn's ein paar sek. länger dauert. Aber trotzdem bin ich auf Deinen Vorschlag gespannt, wie man das schneller machen kann!

    0
  • P

    Ich denke, er meint damit, einfach die Tabelle fix in den Source hinein kompilieren, ich würde es nämlich auch so machen 😉

    lg, phreaking

    0
  • E

    dito. wird aber ein eklig langer maskierter string *g+

    0
  • P

    Die Tabelle aus einer Datei in den Speicher zu holen, wäre auch möglich, aber ob das schneller ist... 😕

    lg, phreaking

    0
  • M

    beim hardcoding wirds doch auch aus ner datei in 'n speicher geladen *g* - meistens zumindest

    0
  • ?

    Ich dachte aber eher an eine schnellere Methode, als die oben vorgestellte.... mir ist auch schon was eingefallen, wie man das besser machen kann ...

    Aber dazu brauch' ich nen Compiler zum testen, den ich grad nicht hab....

    0
  • E

    www.cygwin.com *g*

    void populate()
    {
    char *BitFeld; //nur definition, muss vorher generiert werden
    char *felda,*feldb; //nur definition, sollten vorher geladen werden
    short unterschiede=0; //char ist ein bit zu klein 😉
    char i; //reicht später für meine zwecke, schleife wird immer nur bis 64 gehen
    for (i=0; i < 64;i++)
    unterschiede += BitFeld[felda[i] ^ feldb[i]];
    }

    darf ich mal posten, was der GCC bei verschiedenen Optimierungsstufen draus gemacht hat? ich hab irgendwie das gefühl, das ab -O2 da nur noch mist rauskommt.

    0
  • M

    zeig her.

    0
  • E

    -O2

    populate:
        pushl %ebp
        movl %esp,%ebp
        movl $63,%ecx
        .p2align 4,,7
.L6:
        decl %ecx
        jns .L6
        movl %ebp,%esp
        popl %ebp
        ret

    hmm, so ohne XOR doch verdächtig *g*

    -O

    populate:
        pushl %ebp
        movl %esp,%ebp
        xorl %eax,%eax
        .p2align 4,,7
.L6:
        incl %eax
        cmpl $63,%eax
        jle .L6
        movl %ebp,%esp
        popl %ebp
        ret

    wenigstens mal ein XOR, aber irgendwie sieht der code total komisch aus... kann jemand was dazu sagen?

    0
  • M

    kannste des mal in menschenlesbaren Code verwandeln *g*?

    0
  • E

    wenn ich den verstehen würde, dann vielleicht. aber ich bin eher ein assembler anfänger 😞
    schon die % vor den registern stört mich irgendwie.

    0
Anmelden zum Antworten