Gesetzte Bits im Byte zählen



  • Hallöchen!

    Ich hab da etwas,das mich brennend interessiert. Es geht darum, wie kann man am effektivsten (in Takten) herausfinden wieviele Bits in einem Byte oder Word gesetzt sind. Das naheliegendste wäre natürlich eine Schleife, aber die verbraucht ja auch eine Menge Takte *g* Hat die CPU (x86) dafür einen Befehl, oder gibt´s da einen netten (mathematischen) Trick dafür?

    Das ist nix was ich irgendwie anwenden möchte (Portierbarkeit vermutlich == 0), aber es würde mich interessieren. Vielleicht kann ein Crack hier mal zeigen, wie man sowas macht.

    Danke im Voraus 🙂



  • http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/22007.pdf
    Chapter 8 / Efficient Implementation of Population Count Function



  • Danke für die Antwort! 🙂

    Wie bist du auf das Dokument gekommen? Im Kopf gehabt? Oder über eine Suchmaschine?

    Ich hab mir einen Wolf gesucht, und nix gefunden 😞



  • Ich hatte des Dokument schon mal "benutzt" und wusste halt noch, dass das drinne war.



  • gib doch einfach ein 300-seitiges dokument an und verrate die seitennummer nicht.



  • wenn du's ausdruckst: 136
    im reader: 156
    - aber links ist doch die Kapitelliste... !?



  • jo, ging mit der kapitelübersicht recht schnell.

    da könnte man ja doch auf die idee kommen,per #ifdef für x86er die version zu benutzen, auch wenn ich die noch nicht so 100% verstanden habe.



  • für den MSVC:

    __inline unsigned bitcnt(unsigned v) { unsigned r; __asm {
        mov eax, [v]
        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
        mov r,   eax
       }
       return r;
    }
    

    [ Dieser Beitrag wurde am 27.08.2002 um 15:06 Uhr von Mr. n editiert. ]



  • gebaut vom MSVC:

    8:    u32 countBitsTrue(u32 x)
    9:    {//http://www.df.lth.se/~john_e/gems/gem002d.html
    00401000   mov         eax,ecx
    00401002   shr         eax,1
    00401004   and         eax,55555555h
    00401009   sub         ecx,eax
    10:       x = x - ((x >> 1) & 0x55555555);
    11:       x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    0040100B   mov         eax,ecx
    0040100D   and         ecx,33333333h
    00401013   shr         eax,2
    00401016   and         eax,33333333h
    0040101B   add         eax,ecx
    12:       x = (x + (x >> 4)) & 0x0F0F0F0F;
    0040101D   mov         ecx,eax
    0040101F   shr         ecx,4
    00401022   add         ecx,eax
    00401024   and         ecx,0F0F0F0Fh
    13:       x *= 0x001010101;
    0040102A   mov         eax,ecx
    0040102C   shl         eax,8
    0040102F   add         eax,ecx
    00401031   shl         eax,8
    00401034   add         eax,ecx
    00401036   shl         eax,8
    00401039   add         eax,ecx
    14:       x >>= 24;
    0040103B   shr         eax,18h
    15:       return x;
    16:   }
    0040103E   ret
    

    Irgendwie hat der Weichling sich nicht getraut, IMUL zu verwenden.



  • es stimmt zwar, dass man DirectP vorziehen sollte, aber so... *g*



  • Original erstellt von Mr. n:
    es stimmt zwar, dass man DirectP vorziehen sollte, aber so... *g*

    DirectP?



  • DirectPath : Chapter 4 / Select DirectPath over VectorPath Instructions; Reader S. 70; Textseite 50



  • und in welchem dokument? 🙂



  • welches dokument wohl? was ist der link oben wohl?



  • Hi!
    Ich habe mir dazu auch etwas überlegt, das ist wahrscheinlich aber nur schneller, wenn gar keine Bits gesetzt sind 😉

    mov eax, [var]  ; die zu testende Zahl
    xor bh, bh  ; die Anzahl der gesetzten Bits
    next:
    bsf eax, bl  ; nach gesetztem Bit suchen
    jz end       ; 
    inc bl
    inc bh       ; ein weiteres gesetztes Bit gefunden
    shr bl       ; bereits getestete Bits rausschieben
    jmp next
    end:         ; eax=0, bh=Anz. der gesetzten Bits in var
    

    Ich hoffe, der Code ist zumindest etwas effizienter, als jedes Bit einzeln zu testen... 😞

    so long, phreaking



  • vielleicht hast du ja erkannt, dass die anderen codes _keine_ schleife benötigen und sogar in _konstanter_ (wenn der prozessor so gut ist) Zeit ablaufen... bei "meinem" code tippe ich auf < 20 Instruktionen. das ist _gut_. nichtsdestotrotz natürlich gut, dass du dir gedanken gemacht hast...



  • Ich hab auch ne Schleife.

    6:    u32 countBitsTrue(u32 data)
    7:    {
    00401000   xor         eax,eax
    8:        u32 result=0;
    9:        while(data)
    00401002   test        ecx,ecx
    00401004   je          countBitsTrue+0Eh (0040100e)
    10:       {
    11:           ++result;
    12:           data&=data-1;
    00401006   lea         edx,[ecx-1]
    00401009   inc         eax
    0040100A   and         ecx,edx
    0040100C   jne         countBitsTrue+6 (00401006)
    13:       }
    14:       return result;
    15:   };
    0040100E   ret
    

    Über die fantasievolle Verwendung von lea freue ich mich immer wieder.



  • hilfe, hier sind ja alle noch bekloppter als ich *g*

    was man bei den funktionen aber nicht vergessen sollte ist, das ja auch der funktionsaufruf in anweisungen umgesetzt werden. der stack wird ja gesichert und so ....

    aber das noch keiner eine GCC version gepostet hat... ihr enttäuscht mich 😉



  • Original erstellt von Evil Azrael:
    aber das noch keiner eine GCC version gepostet hat... ihr enttäuscht mich 😉

    Ich hab C++ gepostet. Jag das einfach mal durch den GCC und wir gucken uns seinen Code an.



  • @volkard: irgendwie kommt mir dein (c++-)code bekannt vor...


Log in to reply