4. Gesetzte Bits im Byte zählen

Gesetzte Bits im Byte zählen

  • E

    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 🙂

    0
  • M

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

    0
  • E

    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 😞

    0
  • M

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

    0
  • V

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

    0
  • M

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

    0
  • E

    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.

    0
  • M

    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. ]

    0
  • V

    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.

    0
  • M

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

    0
  • V

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

    DirectP?

    0
  • M

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

    0
  • ?

    und in welchem dokument? 🙂

    0
  • M

    welches dokument wohl? was ist der link oben wohl?

    0
  • P

    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

    0
  • M

    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...

    0
  • V

    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.

    0
  • E

    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 😉

    0
  • V

    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.

    0
  • M

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

    0
Anmelden zum Antworten