[C] macht-van-twee

[Verwijderd]

Ik heb een random getal en die wil ik (indien nodig) ophogen totdat het een macht van twee is. Ik dacht dus aan het volgende:

code:

#include <stdio.h>

unsigned int
power_of_two (unsigned int num)
{
  unsigned int bits = 0;

  num--; /* 2^n nums have one extra bit set */
  while(num)
  {
    num >>= 1;
    bits++;
  }
  return 1<<bits;
}

Hierbij gooi ik dus whichever positief getal erin en krijg ik een 2^n terug (als ik 31 erin gooi krijg ik 32 terug). Maar... Heeft C hier niet een simpele(re) functie voor? Ik vind een loop nou niet echt de meest elegante manier hiervoor...

[Sponz]

ja, met recursie ipv een loop.

[Grum]

Sponz: je hebt een beetje foute ondertitel/sig

[Janoz]

mwah .. Ik vind een loop meestal wat netter dan recursie..

^{Grum: Dit is eigenlijk niet echt de plek voor het opmerkingen maken over ondertitels, daar hebben we een speciaal forum voor...}

[Verwijderd]

Op woensdag 13 maart 2002 14:01 schreef Sponz het volgende:
ja, met recursie ipv een loop.

mjah, dan zit je nog steeds met de herhaling

Wat ik dus bedoel, is: is er niet een functie die automatisch kan tellen welke de hoogste actieve bit is?

[Sjaaky]

Als je het niet erg vindt om log() te gebruiken:

code:

#include <stdio.h>
#include <math.h>
unsigned int
power_of_two (unsigned int num)
{
  double bits = log(num)/log(2);
  return 1 << 1+(int)bits;
}

Waarschijnlijk wil je je distributie behouden, maar anders kan je ook "1 << random" doen.

[Verwijderd]

[evil]

benchmarkje doen

[/evil]

ziet er wel stukken beter uit zo... Ff proberen zo

[edit]
Die van mij is drie keer zo snel

[RickN]

Op woensdag 13 maart 2002 15:55 schreef beelzebubu het volgende:
Die van mij is drie keer zo snel

O, als het je ook om snelheid gaat voer dan tenminste de volgende optimalisatie door:

code:

#include <stdio.h>

unsigned int power_of_two (unsigned int num)
{
  unsigned int result = 1;

  num--; /* 2^n nums have one extra bit set */
  while(num)
  {
    num >>= 1;
    result <<= 1;
  }
  return result;
}

Al doet de compiler dat misschien wel voor je....

[Sjaaky]

Waarschijnlijk heeft intel ook bedacht dat dit wel eens makkelijk zou kunnen zijn, vanaf de 386 werkt het volgende ook

code:

unsigned int
power_of_two (unsigned int num)
{
  int bits = 0;
  asm("bsr %1,%0" : "=r" (bits): "rm" (num), "0" (bits));
  return 1 << bits+1;
}

[.oisyn]

AT&T syntax == vies
en ja dat is een niet onderbouwde flame

maar idd, zonder asm is er geen andere manier om dat te doen zonder alle bits te controleren

[RickN]

Op woensdag 13 maart 2002 17:51 schreef Sjaaky het volgende:
Waarschijnlijk heeft intel ook bedacht dat dit wel eens makkelijk zou kunnen zijn, vanaf de 386 werkt het volgende ook

code:

unsigned int
power_of_two (unsigned int num)
{
  int bits = 0;
  asm("bsr %1,%0" : "=r" (bits): "rm" (num), "0" (bits));
  return 1 << bits+1;
}

Leg es uit. Hoe ziet dit eruit in asm? Wordt er hier een speciale instructie gebruikt?

[Sjaaky]

in normaal asm zou het er ongeveer zo uit zien:

code:

  mov eax, [num]
  mov ecx, 2
  bsr ebx, eax
  shl ecx, ebx
  mov [output], ecx

Mijn asm wordt alweer een beetje roestig.
Bsr is inderdaad een speciale instructie.

ps. (1 << bits+1) == (2 << bits) dus heb ik nu ook maar meteen mov ecx, 2 gedaan.

[.oisyn]

A.10 BSF, BSR: Bit Scan

code:

BSF reg16,r/m16        ; o16 0F BC /r      [386] 
BSF reg32,r/m32        ; o32 0F BC /r      [386]


BSR reg16,r/m16        ; o16 0F BD /r      [386] 
BSR reg32,r/m32        ; o32 0F BD /r      [386]

BSF searches for a set bit in its source (second) operand, starting from the bottom, and if it finds one, stores the index in its destination (first) operand. If no set bit is found, the contents of the destination operand are undefined.

BSR performs the same function, but searches from the top instead, so it finds the most significant set bit.

Bit indices are from 0 (least significant) to 15 or 31 (most significant).

(uit de NASM docs)

[Sjaaky]

If no set bit is found, the contents of the destination operand are undefined.

Maar in dat geval wordt ZF op 0 gezet. Als er wel bits op 1 staan, wordt ZF op 1 gezet.

Bovenstaande stukje was mijn eerste instructie inline asm in gcc (en ook mijn eerste instructie in AT&T asm).

[Verwijderd]

Op woensdag 13 maart 2002 18:09 schreef OiSyN het volgende:
maar idd, zonder asm is er geen andere manier om dat te doen zonder alle bits te controleren

Nouja, dat moet dan maar... 't moet vrees ik toch echt C zijn, 't is de bedoeling dat 't op meerdere platformen werkt

Toch bedankt voor de ASM code

[.oisyn]

Op woensdag 13 maart 2002 18:52 schreef Sjaaky het volgende:

[..]

Maar in dat geval wordt ZF op 0 gezet. Als er wel bits op 1 staan, wordt ZF op 1 gezet.

waar haal je dat vandaan?

niet dat ik je niet geloof ofzo hoor, of dat ik zeg dat je ongelijk hebt... _{maar je hebt ongelijk en ik geloof je niet}
maar misschien is het meer een undocumented feature (maw, misschien werkt het op jouw cpu, maar niet op een andere van een andere fabrikant bijv.)

[Sjaaky]

Ok ik had GEEN gelijk. Het is namelijk precies andersom _{wat mij ook al logischer leek}.
Mijn eerste foutieve bron http://www.penguin.cz/~literakl/intel/b.html#BSR.

Om mijn gelijk te halen heb ik ftp://download.intel.com/design/pro/MANUALS/24319101.PDF even gedownload, waar ik op pagina 57 het volgende vind:

BSR - Bit Scan Reverse
...
Flags Affected
The ZF flag is set to 1 if all the source operand is 0; otherwise, the ZF flag is cleared. The CF, OF, SF, AF, and PF, flags are undefined.

_{Er zijn best een heleboel instructies die ZF op 1 zetten als de source-operand of result 0 is. [edit] Oeps dat valt een beetje tegen, maar instructies zoals inc, dec, sub, add, and, or, xor iig wel[/edit]}