Benötigen Sie Hilfe beim Verständnis der Methode “getbits()” in Kapitel 2 von K&R C

Lesezeit: 5 Minuten

Benutzer-Avatar
John Rudi

In Kapitel 2, dem Abschnitt über bitweise Operatoren (Abschnitt 2.9), habe ich Schwierigkeiten zu verstehen, wie eine der Beispielmethoden funktioniert.

Hier ist die bereitgestellte Methode:

unsigned int getbits(unsigned int x, int p, int n) {
    return (x >> (p + 1 - n)) & ~(~0 << n);
}

Die Idee ist, dass für die angegebene Anzahl xes wird die zurückgegeben n Bits ab Position p, von rechts gezählt (wobei das Bit ganz rechts die Position 0 ist). Angesichts der folgenden main() Methode:

int main(void) {
    int x = 0xF994, p = 4, n = 3;
    int z = getbits(x, p, n);
    printf("getbits(%u (%x), %d, %d) = %u (%X)\n", x, x, p, n, z, z);

    return 0;
}

Die Ausgabe ist:

getbits(63892 (f994), 4, 3) = 5 (5)

Ich bekomme Teile davon, aber ich habe Probleme mit dem “großen Bild”, hauptsächlich wegen der Teile (kein Wortspiel beabsichtigt), die ich nicht verstehe.

Der Teil, mit dem ich speziell Probleme habe, ist das Ergänzungsstück: ~(~0 << n). Ich glaube, ich bekomme den ersten Teil, den Umgang mit x; Es ist dieser Teil (und dann die Maske), mit dem ich zu kämpfen habe – und wie alles zusammenkommt, um diese Teile tatsächlich abzurufen. (Was ich verifiziert habe, sowohl mit Code als auch mit der Überprüfung meiner Ergebnisse mit calc.exe – Gott sei Dank hat es eine binäre Ansicht!)

Irgendeine Hilfe?

Benutzer-Avatar
paxdiablo

Nehmen wir für unser Beispiel 16 Bit. In diesem Fall, ~0 ist gleich

1111111111111111

Wenn wir das nach links verschieben n Bits (3 in Ihrem Fall) erhalten wir:

1111111111111000

weil die 1s auf der linken Seite werden verworfen und 0s werden rechts eingespeist. Eine erneute Ergänzung ergibt dann:

0000000000000111

es ist also nur ein cleverer Weg, um es zu bekommen n 1-Bits im niederwertigsten Teil der Zahl.

Das von Ihnen beschriebene “x-Bit” hat die angegebene Zahl verschoben (f994 = 1111 1001 1001 0100) weit genug, damit die niederwertigsten 3 Bits die gewünschten sind. In diesem Beispiel sind die gewünschten Eingangsbits vorhanden, alle anderen Eingangsbits sind markiert . da sie für das Endergebnis nicht wichtig sind:

ff94             ...........101..  # original number
>> p+1-n     [2] .............101  # shift desired bits to right
& ~(~0 << n) [7] 0000000000000101  # clear all the other (left) bits

Wie Sie sehen können, haben Sie jetzt die relevanten Bits an den Bitpositionen ganz rechts.

  • Ich wollte vorschlagen, nach rechts zu schalten, um eine Anweisung zu sparen, aber ich denke, ~(~0 << n) lässt Sie elegant die Wortgröße ignorieren, mit der Sie arbeiten …

    – Unsinn

    1. Dezember 2013 um 8:58 Uhr

  • Ich verstehe etwas nicht, wo mache ich einen Fehler? Ganzzahl a = 0; also printf(“%d”, a) gibt 0. Nun, a = ~a also printf(“%d”, a) gibt -1, warum?

    – Anatoly

    8. November 2014 um 11:12 Uhr


  • @Anatoly: Es ist weil ~ invertiert alle Bits auf 1 und bei Zweierkomplement-Codierung ist das -1.

    – paxdiablo

    9. November 2014 um 2:46 Uhr

  • Gute Antwort. Endlich verstehe ich dieses Beispiel! 🙂

    – Kyrol

    12. September 2018 um 8:09 Uhr

  • Danke für diese tolle Antwort @paxdiablo. Um jedoch jeden Schritt auf dem Weg vollständig erfassen zu können, möchte ich jeden Schritt isolieren können. Wenn ich versuche zu drucken printf("try: %d\n", ~0 << 1);bekomme ich eine Fehlermeldung: printf("try: %d\n", ~0 << 1); ~~ ^ 1 warning generated. Undefined symbols for architecture x86_64: "_printnozero", referenced from: _main in getbits-923932.o ld: symbol(s) not found for architecture x86_64. Gibt es eine andere Möglichkeit es auszudrucken. Wenn nicht, warum kann ich es nicht ausdrucken?

    – ecjb

    1. Februar um 8:35 Uhr


Benutzer-Avatar
Keiner

Ich würde sagen, das Beste, was man tun kann, ist, ein Problem von Hand zu lösen, damit man versteht, wie es funktioniert.

Hier ist, was ich mit einem 8-Bit unsigned int gemacht habe.

  1. Unsere Zahl ist 75, wir wollen die 4 Bits ab Position 6. Der Aufruf für die Funktion wäre getbits (75,6,4);

  2. 75 ist binär 0100 1011

  3. Wir erstellen also eine Maske, die 4 Bit lang ist, beginnend mit dem Bit der niedrigsten Ordnung. Dies wird als solches durchgeführt.

~0 = 1111 1111
<<4 = 1111 0000
~ = 0000 1111

Okay, wir haben unsere Maske.

  1. Jetzt schieben wir die Bits, die wir wollen, aus der Zahl in die niedrigstwertigen Bits, sodass wir binär 75 um 6+1-4=3 verschieben.

0100 1011 >>3 0000 1001

Jetzt haben wir eine Maske mit der richtigen Anzahl von Bits in niedriger Ordnung und die Bits, die wir aus der ursprünglichen Anzahl in niedriger Ordnung haben wollen.

  1. also wir & sie
  0000 1001 
& 0000 1111 ============ 0000 1001

Die Antwort ist also dezimal 9.

Notiz: Das Nibble höherer Ordnung besteht zufällig nur aus Nullen, was die Maskierung in diesem Fall überflüssig macht, aber es hätte alles sein können, abhängig vom Wert der Zahl, mit der wir begonnen haben.

Benutzer-Avatar
David Grant

~(~0 << n) erstellt eine Maske, die die haben wird n Bits ganz rechts eingeschaltet.

0
   0000000000000000
~0
   1111111111111111
~0 << 4
   1111111111110000
~(~0 << 4)
   0000000000001111

Das AND-Verknüpfen des Ergebnisses mit etwas anderem gibt zurück, was in diesen ist n Bits.

Bearbeiten: Ich wollte auf den Taschenrechner dieses Programmierers hinweisen, den ich schon immer benutze: AnalogX PCalc.

Niemand hat es bisher erwähnt, aber in ANSI C ~0 << n verursacht undefiniertes Verhalten.

Das ist weil ~0 ist eine negative Zahl, und negative Zahlen mit Linksverschiebung sind undefiniert.

Referenz: C11 6.5.7/4 (frühere Versionen hatten ähnlichen Text)

Das Ergebnis von E1 << E2 ist E1 links verschoben E2 Bitpositionen; frei gewordene Bits werden mit Nullen aufgefüllt. […] Wenn E1 einen vorzeichenbehafteten Typ und einen nicht negativen Wert hat, und E1 × 2E2 im Ergebnistyp darstellbar ist, dann ist das der Ergebniswert; andernfalls ist das Verhalten undefiniert.

In K&R C hätte sich dieser Code auf die bestimmte Systemklasse verlassen, auf der K&R entwickelt hat, und sich naiv verschoben 1 Bits links weg, wenn eine vorzeichenbehaftete Zahl nach links verschoben wird (und dieser Code basiert auch auf der Zweierkomplementdarstellung), aber einige andere Systeme teilen diese Eigenschaften nicht, sodass der C-Standardisierungsprozess dieses Verhalten nicht definiert hat.

Dieses Beispiel ist also wirklich nur als historische Kuriosität interessant, es sollte seit 1989 (wenn nicht früher) in keinem echten Code mehr verwendet werden.

Am Beispiel: int x = 0xF994, p = 4, n = 3; int z = getbits (x, p, n);

und Konzentration auf diese Reihe von Operationen ~(~0 << n)

Für jeden Bitsatz (10010011 usw.) möchten Sie eine “Maske” generieren, die nur die Bits zieht, die Sie sehen möchten. Also 10010011 oder 0x03, ich interessiere mich für xxxxx011. Was ist die Maske, die diesen Satz extrahiert? 00000111 Jetzt möchte ich sizeof int unabhängig sein, ich lasse die Maschine die Arbeit erledigen, dh beginne mit 0 für eine Bytemaschine, es ist 0x00, für eine Wortmaschine ist es 0x0000 usw. Eine 64-Bit-Maschine würde durch 64 Bits oder 0x00000000000000000 dargestellt

Wenden Sie nun “not” (~0) an und erhalten Sie 11111111
Verschiebe nach rechts (<<) um n und erhalte 11111000
und “nicht” das und erhalte 00000111

also 10010011 & 00000111 = 00000011

Erinnern Sie sich, wie boolesche Operationen funktionieren?

  • @jim: Hey, ich klopfe nicht an die Genauigkeit deines Beitrags. Inhaltlich hat mehr zu tun als die beiden anderen, es wäre gut, Codeblöcke zu verwenden und Änderungen auszurichten. Die Posts verwenden Wiki-Markup, und eine Tute-Seite verlinkt vom “?” über dem Antwortfeld. Ich musste es zweimal lesen, um es überprüfen zu können.

    – Ande Turner

    13. Oktober 2008 um 14:20 Uhr

Im ANSI C ~0 >> n verursacht undefiniertes Verhalten

// Der Beitrag über die Linksverschiebung, die ein Problem verursacht, ist falsch.

unsigned char m,l;

m = ~0 >> 4; produziert 255 und ist gleich ~ 0, aber,

m = ~0; l = m >> 4; erzeugt den korrekten Wert 15 wie:

m = 255 >> 4;

es gibt kein Problem mit Linksverschiebung negativ ~0 << was auch immer

  • @jim: Hey, ich klopfe nicht an die Genauigkeit deines Beitrags. Inhaltlich hat mehr zu tun als die beiden anderen, es wäre gut, Codeblöcke zu verwenden und Änderungen auszurichten. Die Posts verwenden Wiki-Markup, und eine Tute-Seite verlinkt vom “?” über dem Antwortfeld. Ich musste es zweimal lesen, um es überprüfen zu können.

    – Ande Turner

    13. Oktober 2008 um 14:20 Uhr

1383380cookie-checkBenötigen Sie Hilfe beim Verständnis der Methode “getbits()” in Kapitel 2 von K&R C

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy