Lese av en og en bit i c?

[Misguided angel]

Jeg er nybegynner i c programmering og holder på med en oppgave. Oppgaven går ut på finne log2 til en "unsigned integer n" ved å bruke denne fremgangsmåten: "Find the most significant set bit in n and return the position of this bit. For example, if n is 17 (10001), the function should return 4.

 

Jeg tenker at for å løse denne oppgaven må jeg få lest av "bit'ene" en etter en fra venstre. Vet ikke om dette er riktig fremgangsmåte, men finnes det en måte å lese av ett og ett tall på?

 

Håper noen forstår spørsmålet mitt...

[Hårek]

Man leser et bit ved å bruke en maske og en AND operasjon. F.eks a = b & 0x01; vil gi deg LSB av b.

Så kan du bruke shift funksjonen >> i en loop for å lese av hvert bit for seg.

[Tapped]

For mest effektivitet, loop ikke igjennom. Du vet at det er en 32 unsigned integer, og da er det bedre å programmere linje for linje. Det ser ut som om funksjonen skal runde nedover fordi 4^2 != 17. Det du gjør da er å sjekke om tallet n er større enn 1 << x*2. << er left shift og x*2 er først 1. Her er koden for å regne log2 av en unsigned integer.

//Returner -1 hvis n er null.
int log2(unsigned int n)
{
int pos = 0;
if(n == 0)
	return -1;

if(n >= 0x10000)// n >= 1 << 16
{
	n >>= 16;// Flytt den største bit av n
	pos += 16;
}
if(n >= 0x100)// n >= 1 << 8
{
	n >>= 8;// Flytt den største biten av n
	pos += 8;
}
if(n >= 0x10)// n >= 1 << 4
{
	n >>= 4;// Flytt den største bit av n
	pos += 4;
}
if(n >= 0x4)// n >= 1 << 2
{
	n >>= 2;// Flytt den største bit av n
	pos += 2;
}
if(n >= 0x2)// n >= 1 << 1
{
	//n >>= 1; Trenger ikke å shifte den mer. 
	pos += 1;
}

       return pos;
}

Endret 23. september 2011 av Tapped

[GeirGrusom]

Mange kompilatorer vil rulle ut løkker som går i et bestemt antall ganger.

[TheMaister]

Tappeds eksempel er ikke bare unrolling. Metoden hans er O(log(n)) istedenfor O(n).

[Dinosauromann]

En unsigned int er faktisk ikke garantert å være 32-bit, så om en vil være veldig portabel er det bedre å bruke en loop. (eventuelt bruke uint32_t i stedet.)