Blandade C++ frågor, nybörjarnivå

[sodjan]

Beror lite på plattform, en del processorer har instruktioner i hårdvaran för det.
Dock inte i mindre typ PIC/AVR så vitt jag vet...

[lillahuset]

Så här på raken kan jag inte komma på något "fiffigare" sätt än att loopa 16 gånger och i varje loop räkna upp en variabel om LSB är 1 och sedan skifta höger.

Det finns arkitekturer med stöd för sådant men det ingår inte i ANSI C. Så vitt jag vet. Och det verkar vara sodjans åsikt också.

Edit: I en AVR borde det väl inte handla om mer än knappt 100 cykler att få till det?

[Magnus_K]

Att loopa igenom den 16 ggr sitter jag och knåpar på nu, då det är det enda min fantasi kan erbjuda. Hade dock hoppats att man kunde nyttja AND/OR/bitshift eller annat, på något klyftigt sätt.
Usch, 100 cykler blir mycket för att få till det. Men så får det väl bli.

Kommer inte lösa det här ikväll och ska söka lite mer på nätet men hojta gärna till om ni får en snilleblixt.

EDIT: @sodjan: vad ska jag söka efter för att verifiera om ATmega328P har en sån funktion?

EDIT2: När jag tänker på det så kommer dom högsta bitarna oftast kommer vara 0 så kanske man ska nyttja Brian Kernighan’s Algoritm? Enligt kopierat exempel nedan.
På så sätt loopar den bara upp tills det är slut på satta bitar.. Spara ju alltid något...

Kod: Markera allt

int countSetBits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      n &= (n-1) ;
      count++;
    }
    return count;
}

[baron3d]

Om du skapar en tabell med antalet ettor i indexet, T.ex. a[0]=0, a[1]=1, a[1]=1, a[3]=2,,,, så kan du dela upp ditt tal i lämplig storlek och använda tabellen för att få antal ettor.

Kod: Markera allt

unsigned char a[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };

short x=0b0011001010010100;
short b;


b= a[x&15];
x>>=4
b+= a[x&15];
x>>=4
b+= a[x&15];
x>>=4
b+= a[x&15];

Använder du en tabell med 256 värden går beräkningen fortare.

Edit: Ändrat från 7 till 3

[lillahuset]

ATmega har ingen sådan funktion. Det lär du inte hitta i någon åttabittare om det inte är någon specialprocessor.

Kernighans metod var ny för mig. Väldigt smart om man vet att man har få ettor.

Baron3ds metod är den jag spontant skulle använda om jag hade bråttom, med en större array om jag hade plats. Men ändra sjuan till en trea.

Assembler? Nähä, inte så bråttom? Räknar du bittar så ofta att det verkligen spelar någon roll hur lång tid funktionen tar?

[sodjan]

> vad ska jag söka efter för att verifiera om ATmega328P har en sån funktion?

Instruktionsuppsättningen i databladet.

DEC Alpha har dessa:

Kod: Markera allt

CTLZ  Count leading zero
CTPOP Count population (räknar antal "1" i ett register)
CTTZ  Count trailing zero

Håller som de övriga på tabelluppslagning ifall det är bråttom...

[Magnus_K]

Kanske inte för att det är så bråttom, men vore kul att testa det här med tabelluppslagning. Mig veterligen aldrig provat det innan.
Förstår för övrigt inte någonting av baron3d kod men ska försöka hitta lite dokument om ämnet!

[lillahuset]

Kod: Markera allt

/* en array som innehåller antalet ettor en "nibble" 0..15 har */
unsigned char a[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };

/* talet du vill testa */
short x=0b0011001010010100;

/* resultatvariabeln */
short b;

/* först testar bu bit3..bit0, efter den operationen innehåller b 1 */
b= a[x&15];

/* sedan skiftar du talet 4 steg åt höger och gör samma sak, b blir 3 */
x>>=4
b+= a[x&15];

/* sedan skiftar du talet 4 steg åt höger och gör samma sak, b blir 4 */
x>>=4
b+= a[x&15];

/* sedan skiftar du talet 4 steg åt höger och gör samma sak, b blir 6 */
x>>=4
b+= a[x&15];

Nu då?
Jag misstänker att det är >>= och += som förvirrar men det blir självklarheter när man har programmerat C ett tag.
https://en.wikipedia.org/wiki/Operators ... nd_C%2B%2B
Lycka till!

[adent]

Kan också förklaras såhär (Vi låtsas att 0b finns och att t.ex. 0b0000 = 0x0, 0b0110 = 0x6, 0b1111 = 0xF ):

unsigned char a[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 }

a[0b0000] ger då 0. Det stämmer! 0000 innehåller 0st 1:or. (position 0 i arrayen innehåller 0).
a[0b0110] ger då 2. Det stämmer! 0110 innehåller 2st 1:or. (position 6 i arrayen innehåller 2).
a[0b1111] ger då 4. Det stämmer! 1111 innehåller 4st 1:or. (position 15 i arrayen innehåller 4).

Sedan shiftar man ner det 16-bitars-talet och kollar nästa 4 bitar. Annars hade arrayen blivit himlans stor!

MVH: Mikael

[baron3d]

adent + lillahuset

[Magnus_K]

Ni får sucka men jag förstår ändå inte

unsigned char a[16] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
Här skapas en array 'a' som innehåller 16 element. Samtliga tilldelas ett värde baserat på?

b= a[x&15];
Här tilldelas resultatvariabeln elementvärdet av element nummer "x&15", alltså värdet på testvariabeln and:as med 15 (1111).
Nej, hänger tyvärr inte med.

Skiftningen och += förstår jag i alla fall!

[adent]

Hehe

Läs mitt inlägg igen! Värdena i arrayen är antalet ettor i indexet (för ett fyrabitarstal)!

unsigned char a[16] = { 0,1,1,2 ...

index 0, 0b0000 -> 0 ettor
index 1, 0b0001 -> 1 etta
index 2, 0b0010 -> 1 etta
index 3, 0b0011 -> 2 ettor

Man använder arrayen som en uppslagstabell!

[lillahuset]

Ja lite suck blir det allt men det är OK.

Arrayen innehåller antalet ettor i alla värden mellan 0 och 15.

b= a[x&15];
Du har ett index till arrayen som är mellan 0 och 15 och får alltså veta hur många ettor din "nibble" alltså halvbyte eller vad man vill kalla den har.

Sedan kör man fyra gånger för att få veta hur många ettor som finns i ditt 16 bits ord.

OK?

[Magnus_K]

Nu hänger jag med

Vad roligt. Tack för tålamodet!

[Icecap]

Och kollar man lite löst på detta att stega int'en igenom och räkna '1' kontra maska ut en nibble åt gången, slå i tabell osv. lär de två metoder nog ta ung. lika lång tid.

Så i detta tillfälle ser jag ingen större vinst men tekniken kan användas i andra lägen där vinsten kan bli signifikant. För att få en kännbar tidsvinst i detta tillfälle ska tabellen vara stor (256 bytes).