Bit Operationen

[AlexC]

Hallo zusammen,

ich versuche durch das Thema Bit-Operatoren zu steigen und stehe vor folgendem Problem:

Ich habe eine Zahl, die ich mir in Binärdarstellung ausgeben lasse. Das sieht dann so aus:

01010111010110100000100111111010

Jetzt verschiebe ich diese Bits um 2 Stellen nach rechts:

$foo = ($bar >> 2)

in $foo steht jetzt:

00010101110101101000001001111110

Sieht für mich alles richtig aus.

Das gleiche mache ich jetzt mit

10010010101111111111110111111010

Nach dem Verschieben der Bits erhalte ich aber:

11100100101011111111111101111110

Das sieht für mich nun wiederum nicht richtig aus. So wie ich es verstanden habe, müssten alle Bits um 2 Stellen nach rechts geschoben werden. Dann ist es ja eigentlich unmöglich, dass plötzlich Einsen auf der linken Seite erscheinen.

Kann mich da mal jemand aufklären?

Viele Grüße
Alex

[Don P]

Hallo,

So wie ich es verstanden habe, müssten alle Bits um 2 Stellen nach rechts geschoben werden. Dann ist es ja eigentlich unmöglich, dass plötzlich Einsen auf der linken Seite erscheinen.

Kann mich da mal jemand aufklären?

Mit der Binärdarstellung ist es nicht ganz so einfach. Die Verschiebung um 1 Stelle nach rechts entspricht einer Division durch 2, bei 2 Stellen einer Division durch 4. Wenn deine 32-Bit-Zahl ganz links eine 1 hat, hat diese 1 eine Sonderbedeutung, meines Wissens ist das das Vorzeichen-Flag und der Rest ist invertiert oder so ähnlich. Die Zahl ist also vermutlich negativ. Wenn man eine negative Zahl durch 4 dividiert, ist das Ergebnis wieder negativ, daher werden Einsen von links nachgeschoben.

Sorry, das Ist jetzt alles nur Halbwissen von mir, wie es sich genau verhält, musst du irgendwo nachschlagen. Bin mir aber ziemlich sicher, dass da der Hase im Pfeffer liegt.

Gruß, Don P

[seth_not@home]

gudn tach!

$foo = ($bar >> 2)
[...] Das gleiche mache ich jetzt mit

10010010101111111111110111111010

Nach dem Verschieben der Bits erhalte ich aber:

11100100101011111111111101111110

gib mal deinen genauen code an. bei mir klappt's naemlich. beispiel:

php -r '$a=bindec("10010010101111111111110111111010"); $b=$a>>2; printf("%032b\n%032b\n", $a, $b);'

10010010101111111111110111111010
00100100101011111111111101111110

prost
seth

[Christian Seiler]

Hallo seth,

php -r '$a=bindec("10010010101111111111110111111010"); $b=$a>>2; printf("%032b\n%032b\n", $a, $b);'

10010010101111111111110111111010
00100100101011111111111101111110

Du hast ein 64bit-System. Zählt nicht. ;-)

Viele Grüße,
Christian

[seth_not@home]

gudn tach!

Du hast ein 64bit-System. Zählt nicht. ;-)

ach, verflucht. hast ja recht, auch wenn das amd64-dualcore-ding leider nicht meins ist.

prost
seth

[Christian Seiler]

Hallo Alex,

10010010101111111111110111111010

Nach dem Verschieben der Bits erhalte ich aber:

11100100101011111111111101111110

Das sieht für mich nun wiederum nicht richtig aus. So wie ich es verstanden habe, müssten alle Bits um 2 Stellen nach rechts geschoben werden. Dann ist es ja eigentlich unmöglich, dass plötzlich Einsen auf der linken Seite erscheinen.

Doch - da es sich bei PHP immer um "signed integers" handelt (d.h. Ganzzahlen mit Vorzeichen), wird beim Rechts-Shift immer das höherwertigste Bit "reingeshiftet". Wenn das 0 ist, wird 0 reingeshiftet, wenn's 1 ist, 1.

Deine Zahl ist nun 32bit lang. Auf 32bit-Systemen ist bei PHP int so groß. Daher ist das höchste Bit bei Dir wirklich 1.

Seth hat ein 64bit-System, d.h. bei ihm sind nochmal 32bit 0en, die aber ausgelassen werden. Daher klappt es bei ihm scheinbar, bei Dir nicht.

Wenn Du willst, dass *immer* geshiftet wird, als wären es Zahlen ohne Vorzeichen, musst Du Dir das selbst programmieren:

// shifte $i um $n nach rechts, fülle mit 0 auf  
function ushr ($i, $n) {  
  // wenn höchstes bit gesetzt ist  
  if ($i & 0x80000000) {  
    // um 1 shiften  
    $i = $i >> 1;  
    // höchstes bit auf 0 setzen  
    $i = $i & 0x4FFFFFFF;  
    // um den rest shiften  
    return $i >> ($n - 1);  
  } else {  
    // klappt ohne probleme  
    return $i >> $n;  
  }  
}

Das funktioniert dann sowohl auf 32bit- als auch auf 64bit-Systemen, auf 64bit-Systemen ist halt der Zwischenschritt "höchstes bit auf 0 setzen" nicht erforderlich, schadet aber auch nicht.

Viele Grüße,
Christian

[Christian Seiler]

Hallo!

// höchstes bit auf 0 setzen
    $i = $i & 0x4FFFFFFF;

Ach, Mist, sowas blödes, muss natrülich heißen:

$i = $i & 0x7FFFFFFF;

(Alternativ auch $i = $i & ~0x80000000;)

Jetzt aber. :-)

Viele Grüße,
Christian

[seth_not@home]

gudn tach!

Wenn Du willst, dass *immer* geshiftet wird, als wären es Zahlen ohne Vorzeichen, musst Du Dir das selbst programmieren:

ui, in perl gibt es dafuer das modul Bit::Vector. gibt's sowas nicht auch in php?

prost
seth

[flowh]

Hallo seth.

http://php.net/gmp könnte dich vielleicht interessieren.

Servus,
Flo

[seth_not@home]

gudn tach!

http://php.net/gmp könnte dich vielleicht interessieren.

thx, das hatte ich sogar schon ueberflogen, aber nach vergeblicher suche nach "shift" nicht mehr weiter beachtet. eine fertige shift-funktion gibt's da nicht, oder? oder kann man auf den resource-datentyp einfach >> anwenden?
vermutlich muesste man aus gmp_pow oder sowas was basteln.

prost
seth

[Don P]

Hallo,

Doch - da es sich bei PHP immer um "signed integers" handelt (d.h. Ganzzahlen mit Vorzeichen), wird beim Rechts-Shift immer das höherwertigste Bit "reingeshiftet". Wenn das 0 ist, wird 0 reingeshiftet, wenn's 1 ist, 1.

Also hatte ich da recht. Das höchste Bit gehört nicht zur Zahl, sondern signalisiert das Vorzeichen.

Wenn Du willst, dass *immer* geshiftet wird, als wären es Zahlen ohne Vorzeichen, musst Du Dir das selbst programmieren: [...]

Das ergibt dann aber rein rechnerisch falsche Ergebnisse. Eine auf diese Art rechtsgeshiftete Binärzahl ergibt nicht mehr eine Division durch 2^^n (n=Anzahl Verschiebungen).

Wenn ich auf meinem Win32-System -1 in den Bordrechner eingebe, ist die DWord-Binärdarstellung:
11111111111111111111111111111111

Für -2 ist es:
11111111111111111111111111111110
usw.

Das heißt: Um den Betrag einer negativen int Zahl zu erhalten,
z.B. von -2:
11111111111111111111111111111110
muss man zuerst das Ganze invertieren:
00000000000000000000000000000001
und dann noch 1 addieren:
00000000000000000000000000000010

Somit ist klar, dass deine neue rechts-shift-Funktion zwar funktioniert, aber nicht mehr richtig rechnet. Aber das wusstst du ja.
Habe es hier nur der Vollständigkeit halber nochmal deutlich gemacht.

Gruß, Don P

[Der Martin]

Hallo,

Doch - da es sich bei PHP immer um "signed integers" handelt (d.h. Ganzzahlen mit Vorzeichen), wird beim Rechts-Shift immer das höherwertigste Bit "reingeshiftet". Wenn das 0 ist, wird 0 reingeshiftet, wenn's 1 ist, 1.

richtig, PHP geht immer von *Zahlenwerten* aus.

Wenn Du willst, dass *immer* geshiftet wird, als wären es Zahlen ohne Vorzeichen, musst Du Dir das selbst programmieren:

In manchen "niederen", also maschinennahen Sprachen -wie etwa Assembler auf vielen CPUs- unterscheidet man arithmetisches und logisches Schieben.

Was PHP hier macht, ist arithmetisches Schieben, d.h. die Bitfolge wird immer als vorzeichenbehafteter Zahlenwert betrachtet. Dann wird auch das Vorzeichenbit richtig berücksichtigt, und das Rachtsschieben erzeugt arithmetisch richtige Werte entsprechend der Division durch 2.

Im Gegensatz dazu wird beim logischen Schieben die Bitfolge nicht interpretiert, sondern wirklich nur als Kette von Bits angesehen. Beim Schieben werden von links (oder auch rechts) immer Nullen nachgezogen. Solche Operationen braucht man vor allem dann, wenn man hardwarenah programmiert, oder wenn man den Zahlenwert auf Deubelkommraus als vorzeichenlose Zahl interpretieren möchte.

Beim Linksschieben erzeugen logisches und arithmetisches Schieben übrigens identische Ergebnisse, hier kommt es also nicht auf die Betrachtungsweise an.

Schönen Abend noch,
 Martin

[Vinzenz Mai]

Hallo Martin,

Beim Linksschieben erzeugen logisches und arithmetisches Schieben übrigens identische Ergebnisse, hier kommt es also nicht auf die Betrachtungsweise an.

äh, doch. Bei vorzeichenbehafteten Zahlen kann man in diesem Fall das Schieben beim arithmetischen Schieben nicht als gesicherte Multiplikation mit zwei ansehen, oder irre ich mich da?

Freundliche Grüße

Vinzenz

[Der Martin]

Hallo Vinzenz,

Beim Linksschieben erzeugen logisches und arithmetisches Schieben übrigens identische Ergebnisse, hier kommt es also nicht auf die Betrachtungsweise an.
äh, doch. Bei vorzeichenbehafteten Zahlen kann man in diesem Fall das Schieben beim arithmetischen Schieben nicht als gesicherte Multiplikation mit zwei ansehen, oder irre ich mich da?

ja, du irrst dich nicht. ;-)

Dass man bei der Multiplikation irgendwann mit einem Überlauf des zur Verfügung stehenden Zahlenbereichs rechnen muss, ist irgendwie klar. Das unterscheidet aber nicht aritmetische von logischen Shift-Operationen.

PHP hat hier die (für mich unangenehme) Eigenheit, beim Überschreiten des Wertebereichs für Integerwerte automatisch in den Fließkommabereich zu wechseln. Eine Sprache mit fester Typisierung (zum Beispiel C) würde bei den Operationen

0x7FFFFFFF << 1

und

0x7FFFFFFF * 2

dasselbe Ergebnis erhalten, nämlich 0xFFFFFFFE = -2 (32bit-Wertebereich vorausgesetzt). Klarer Fall: Die Multiplikation liefert hier wegen des Überlaufs ein falsches Ergebnis. Aber als Shift-Operation ist das Ergebnis völlig korrekt.

Ciao,
 Martin