erstes/letztes gesetztes Bit eines Integers

User1291

Gegeben einen (32bit) Integer x (im 2's complement) möchte ich die Position des erste und des letzten Bits in der binären Darstellung von x finden, welche 1 sind. (d.h. ich will einen 32bit string mit einsen an den Positionen, wo das niedrigste/höchste gesetzte Bit steht)

Für das niedrigste Bit hab ich einen relativ einfachen Befehl gefunden:

int lbp(int x){
	return x & (~x+1);
}

Das Problem ist nur, ich versteh ihn nicht und kann ihn also nicht zu einem umformen, welcher das höchste findet.

x & (~x + 1) löscht alle Bits (=setzt sie auf Null), welche bei einem Vorzeichenwechsel von x verändert werden... und das bringt mir was genau?

Mag mir wohl wer weiterhelfen?

Edit
Danke allen für die Hilfe.
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?

Da bringt dir nichts, da ja nur das niedrigste gesetzte Bit übrig bleibt. Damit hast du noch nicht die Position.

Versuch es mal mit den shift-operatoren (<< bzw. >>) und einer Schleife.

Anmerkung: bei signed integer ist es nicht vom Standard definiert ob beim rechts-shift das Vorzeichen oder eine 0 als High-Bit eingeschoben wird.

User1291

Tut mir leid, ich hatte die Frage falsch gestellt.
Ich möchte die Position der Bits im Integer bestimmen.
Soll heissen, ich möchte ein 32bit-String mit zwei Einsen an den Stellen, wo im Integer das niedrigste/höchste gesetzte Bit steht. (bzw. eine oder keine 1 falls die Positionen zusammenfallen oder es sich um die Null handelt).

Versuch es mal mit den shift-operatoren (<< bzw. >>) und einer Schleife.

Ich werd mir das aber merken, wenn ich mal einen Pointer brauch. Danke.

da ja nur das niedrigste gesetzte Bit übrig bleibt

Danke, hatte eine Blockade. Da sie per Konstruktion in x und (~x+1) verschieden sind, kann ja gar nicht sein, dass spätere (d.h. nach dem niedrigsten gesetzen) Bits nach der Verundung übrig bleiben. (Manchmal frag ich mich ... )

Das Problem bleibt aber: Wie geh ich sinnvoll mit dem höchsten gesetzen Bit um?
Kann ja nicht sein, dass ich die Bitreihenfolge des Integers erst invertieren, das "niedrigste" gesetze Bit bestimmen und die Bitreihenfolge im Resultat wieder invertieren muss, oder?

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