Anzahl der gesetzten Bits in einem int zählen

martin_b

Hallo zusammen,

in einem C++ Programm (BCB) sollte ich zu einem int-Wert wissen, wieviele Einser dessen Binärdarstellungen enthält - mit anderen Worten, wieviele Bits gesetzt sind. Da ich diese Information sehr häufig brauche, wollte ich aus Effizienzgründen eine Schleife vermeiden.

Kann man das mit Assembler effizient lösen?

Da ich noch nie was mit Assembler gemacht habe, wäre ich auch über ein C++ Codeschnipsel dankbar.

Viele Grüße

Martin

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive und ff

Hallo,

habe auch sogut wie noch nie asm gemacht. Aber folgender Code berechnet die Einser eines int.

unsigned int v = 255;
    asm {

        mov eax, v
        xor ebx, ebx
        jmp start
        weiter:
        shr eax, 1
        start:
        cmp eax, 0x0
        jbe fertig
        mov ecx, eax
        and ecx, 0x1
        jz weiter
        inc ebx
        jmp weiter
        fertig:
    }

In EBX steht dann die Anzahl der Einsen.
Optimierungsvorschläge sind willkommen

bye Saxony

Marc++us

Du kannst die Schleife auch aufrollen, das sollte nach Optimierung auch unter C++ ohne Assembler recht flott sein:

unsigned ones = 0;
ones += value & 0x01;
ones += (value & 0x02)>>1;
ones += (value & 0x04)>>2;
ones += (value & 0x08)>>3;
// usw. je nach Int-Breite

U.U. (mit Profiler prüfen) ist diese Variante schneller:

//...
ones += (value & 0x02) ? 1 : 0;
//...

Oder

//...
if (value & 0x02)
   ones++;
//...

Viel Spaß beim Probieren.

Du solltest Dir aber immer vor Augen halten, daß nicht die Schleife das Problem ist, sondern daß Du (z.B.) eben einfach 16 Operationen durchführen mußt - Du kannst die Anzahl nicht einsparen. Es läuft eben immer wieder auf

for (int i = 0, int bit = 1; i++; i < 16)
{
   ones += (value & bit)>>i;
   bit<<1;
}

raus. Wenn der Optimierer des Compilers - was bei so einer kurzen Schleife recht wahrscheinlich ist - ones, i und bit in Registern hält, bringt eine Aufrollung der Schleife möglicherweise kaum Vorteile (vielleicht macht er das sogar bei der Compilierung), da der Overhead minimal ist.

gargyle

unsigned int v = 255;
    asm {

        mov eax, v
        xor ebx,ebx
NochMal:
        shr eax,1        ;Bit 0 -> Carry
        jnc KeinBit
        inc ebx
KeinBit:
        or eax,eax
        jnz NochMal

    }

Hier werden alle Bits in eax gezählt.
Wenn nur die Bits in ax gefragt sind muss so geändert werden:

shr ax,1 ;Bit 0 -> Carry
or ax,ax

Termite

Hi

wenn speicher keine rolle spielt sag ich lookup tabel.

Was man dazu braucht.
1. eine liste mit 256 einträgen in denen drinsteht wieveile bits gesetzt sind \

/*             0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  ... */
lookup[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ... }

2. eine rotine die mit nem einfachen speicherzugriff den passenden wert aus der lookuptabel herausholt.

anzlah_bit = lookup[zahl];

Das Problem ist sicher der Speicherzugriff. der könnte ggf länger dauern als die paar rechenoperationen die für ne schleife notwendig sind.

gruss

TriPhoenix

http://en.wikipedia.org/wiki/Hamming_weight hat auch einiges dazu

hellihjb

@gargyle:
wenn der zustand des zu pruefenden bits schon im carry flag ist, dann mach's doch so:

asm {
        mov eax, v
        xor ebx,ebx
NochMal:
        shr eax,1
        adc ebx,0
        or eax,eax
        jnz NochMal
    }

mit etwas overhead kann man auch gleich den status des zero-flags vom shift als condition zum terminieren nutzen:

asm {
      mov eax, v
      xor ebx,ebx   // loescht gleichzeitig das carry flag
NochMal:
      adc ebx,0
      shr eax,1
      jnz NochMal
      adc ebx,0
    }

der erste durchlauf addiert dabei unnoetig 0, spart aber fuer jede iteration eine instruction.
theoretisch muesste die loop sogar in einem cycle ausgefuehrt werden koennen, weil addition mit carry des letzten durchlaufs und shift eines anderen registers pairable ist und die branch-prediction die schleife als nicht-terminiert annimmt.
muesste also fuer kleine zahlen (bis maximal 16bit) schneller sein als die bitjonglier-methoden von wikipedia, die in rund 20 schlecht pair-faehige instructions compilieren.

gargyle

Cool.
Muss ich mir merken