erstes/letztes gesetztes Bit eines Integers

Youka

Stackoverflow: "How do you set, clear and toggle a single bit in C?"

SeppJ

Für solche Fragen sehr gut geeignete Seite:
http://graphics.stanford.edu/~seander/bithacks.html

Das ist an einer Beispielrechnung gut zu sehen. Ich beschränke mich mal auf 8 bit.

x           = 10110100
                    vvv-+
~x           = 01001011 |
~x + 1       = 01001100 |
                    ^^^-+-- wichtig!
x & (~x + 1) = 00000100

Der Trick ist, dass durch + 1 das unterste, nicht gesetzte Bit einer Zahl gesetzt wird (während alle darunter 0 werden). In ~x entspricht das der Stelle, an der das unterste gesetzte Bit in x ist (weil in ~x alle Bits geflippt sind). Da sowohl in x als auch ~x + 1 alle Bits unterhalb dieser Stelle Null und alle Bits oberhalb verschieden sind (sie sind in ~x und ~x + 1 gleich), liefert x & (~x + 1) dann genau dieses Bit.

Im Sonderfall x == 0 (wo es kein gesetztes Bit gibt), kommt 0 heraus, weil ~x == -1, ~x + 1 == 0 und 0 & 0 == 0.

knivil

Sonderfall 0? Also 0 & irgendwas ist immer Null, da bedarf es keiner weiteren Analyse.

User1291

Danke euch für die Hilfe.
Insbesondere an "Seander" werd ich noch eine ganze Weile zu kauen haben.

Bringe ich das Äquivalent fürs höchste gesetzte Bit auch intelligenter hin, als naiv die Bitreihenfolge des Integers zu invertieren, durch obigen code zu jagen und die Bitreihenfolge des Resultats wieder zu invertieren?

"x & (~x + 1)" nutzt ja die Tatsache, dass der Übertrag nach links "wandert" (mir fällt grad kein gescheiteres Wort ein), da ist's mit 'nem simplen Ersetzen von "1" durch "(1 << 31)" nicht getan.

SG1

knivil schrieb:

Sonderfall 0? Also 0 & irgendwas ist immer Null, da bedarf es keiner weiteren Analyse.

Nicht Sonderfall in der Implementierung, sondern Sonderfall in der Aufgabenstellung.

SG1

User1291 schrieb:

Bringe ich das Äquivalent fürs höchste gesetzte Bit auch intelligenter hin, als naiv die Bitreihenfolge des Integers zu invertieren, durch obigen code zu jagen und die Bitreihenfolge des Resultats wieder zu invertieren?

In SeppJ's Link ist auch (IIRC, mindestens) eine Methode enthalten, die die Bits eines Integers umdreht (also von vorne nach hinten und umgekehrt). Die könntest Du einmal vorher und einmal nachher anwenden.

User1291

SG1 schrieb:

User1291 schrieb:

Bringe ich das Äquivalent fürs höchste gesetzte Bit auch intelligenter hin, als naiv die Bitreihenfolge des Integers zu invertieren, durch obigen code zu jagen und die Bitreihenfolge des Resultats wieder zu invertieren?

In SeppJ's Link ist auch (IIRC, mindestens) eine Methode enthalten, die die Bits eines Integers umdreht (also von vorne nach hinten und umgekehrt). Die könntest Du einmal vorher und einmal nachher anwenden.

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

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

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.