erstes/letztes gesetztes Bit eines Integers

SG1

User1291 schrieb:

Äh ... bitte nicht falsch verstehen, aber liest du auch, was du zitierst?

In dem Fall wohl nein, shame on me. Wobei ja noch ein Unterschied zwischen "naiv invertieren" (für mich heisst das per Schleife) und dem, was in dem Link steht, besteht.

Aber ja, eine Lösung ohne den Umweg wäre besser.

pittbull

foolie schrieb:

invertieren?
die idee, ne schleife zu benutzen wurde ja schon von dirkb genannt, was spricht dagegen?

schleifen sind doch doof für sowas.

wieson das
das höchste gesetzte und das niedrigste gesetzte bit kann sonstwo sein, wie soll das ohne schleife gehen?

ich würd das iwie so mit nem schleifchen machen:

#define IS_BIT_SET(number, pos) ((number) & (1 << (pos)))

int main(void)
{	
	int number = 10;
	int a = -1, b = -1, i;

	for (i = 0; i < 32 && (a == -1||b == -1); i++) // statt der hartkodierten 32 könnte man auch sizeof(int) * CHAR_BIT schreiben
	{
		if(-1 == b && IS_BIT_SET(number, i))
			b = i;
		if(-1 == a && IS_BIT_SET(number, 31 - i)) // 31 := sizeof(int) * CHAR_BIT -1
			a = 31 - i; // 31 := dito
	}

	printf ("%d %d\n", a, b );
	return 0;
}

pittbull

foolie schrieb:

wieson das
das höchste gesetzte und das niedrigste gesetzte bit kann sonstwo sein, wie soll das ohne schleife gehen?

mit shifts und logikoperationen. such mal im netz danach. sind meistens schicke einzeiler.

foolie schrieb:

wie soll das ohne schleife gehen?

okay würde gehen, z.b. so

if(number == 0x80000001) // 10000000000000000000000000000001
    a = 31, b = 1;
else if (number == 0x40000001 ) // 1000000000000000000000000000001
    a = 30, b = 1;
... etc.

wäre wohl aber ein klein wenig zu aufwendig.

pittbull schrieb:

mit shifts und logikoperationen. such mal im netz danach. sind meistens schicke einzeiler.

hier gibts aber über 500 paarungsmöglichkeiten(528 hab ich ausgerechnet), plus 32 wenn man die zusammenfallenden positionen mitzählt(pos1=pos2).
das dürfte ohne schleife schwierig werden, noch schwerer mit nem einzeiler.

pittbull

hier zum beispiel n algo um das msb zu finden

unsigned int
msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}

quelle: http://aggregate.org/MAGIC/#Most Significant 1 Bit

SG1

Der Einzeiler für das niedrigste gesetzte Bit wurde doch schon gepostet. Und damit ist das Argument

foolie schrieb:

kann sonstwo sein, wie soll das ohne schleife gehen?

auch für das höchste Bit noch schwächer, als es eh schon ist.

SG1 schrieb:

Der Einzeiler für das niedrigste gesetzte Bit wurde doch schon gepostet. Und damit ist das Argument

foolie schrieb:

kann sonstwo sein, wie soll das ohne schleife gehen?

auch für das höchste Bit noch schwächer, als es eh schon ist.

pfffffffffffffffff

User1291

SG1 schrieb:

"naiv invertieren" (für mich heisst das per Schleife)

Ach so. 'tschuldige die Verwirrung.

pittbull schrieb:

hier zum beispiel n algo um das msb zu finden
unsigned int msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}
quelle: http://aggregate.org/MAGIC/#Most Significant 1 Bit

Eine tolle Seite, danke.

Hab mir den Algorithmus mal veranschaulicht, falls es sonst noch wer braucht:
einmal mit 0x00129100
einmal mit 0x80000000
Sehr elegante Lösung.

Wieso wird eigentlich Wert darauf gelegt, dass ein unsigned int zurückgegeben wird?

pittbull

User1291 schrieb:

Wieso wird eigentlich Wert darauf gelegt, dass ein unsigned int zurückgegeben wird?

bei rechts-shift mit negativen werten kommen einsen rein. das funzt dann nicht mehr.

pittbull schrieb:

bei rechts-shift mit negativen werten kommen einsen rein.

Nicht unbedingt. Bei signed Typen ist das Verhalten vom Standard nicht definiert. Es kann eine 0 oder das MSB eingeschoben werden.

User1291

pittbull schrieb:

bei rechts-shift mit negativen werten kommen einsen rein. das funzt dann nicht mehr.

Ist bekannt, danke.

Die Frage war aber

Wieso wird eigentlich Wert darauf gelegt, dass ein unsigned int zurückgegeben wird?

Sprich wieso reicht es nicht, x als unsigned zu deklarieren und die Maske als "gewöhnlicher" int zurückzugeben?

volkard

irrelevant für die Rückgabe, das war gerade gefragt.

Den Rückgabetyp mache ich da normalerweise auch unsigned, weil ich irgendwie im Kontext "Bitmanipulieren" bin und dort die Eingaben besser unsigned sind. Mit den Rückgabewerten will ich ja wieder was machen, gewöhnlich shiften, maskieren, zählen, naja, irgendwelchen bitweisen Krimskrams machen. Will da nicht darüber nachdenken müssen, ob es mit Typen Probleme gewben könnte, sondern bleibe im gesamten Spiel auf unsigned. Mit Nachdenken käme man drauf, daß hier char reichen würde und signed sogar auch ginge. Aber Nachdenken ist was, was ich gar nicht mag. Also nicht über so Pillepalle. Das lenkt nur vom Programmierproblem ab.