Advanced   Java   Services

Shiftoperatoren

Der folgende Auszug aus der Operatorentabelle zeigt die Präzedenz der Shiftoperatoren im Zusammenhang mit den benachbarten Operatoren. + und - binden also stärker als die Shiftoperstoren. Die relationalen Operatoren demnach schwächer als die Shiftoperatoren.

Java wartet gleich mit drei shift-Operatoren auf und mit teilweise überraschenden Eigenschaften derselben.

Linksshift   <<

Bei einem Linksshift wird die Bitfolge der Zahl um eine Bitstelle nach links geschoben. Für das links wegfallende bit wird rechts ein Nullbit nachgezogen. In den "meisten" Fällen entspricht dies einer Multiplikation mit 2. Wir beschränken uns zunächst auf den Datentyp int.

int x =  11162880;
// x = 00000000 10101010 01010101 00000000

int y = x<<2 ;
// y = 44651520
// y = 00000010 10101001 01010100 00000000

Da das most significant bit ein Vorzeichenbit darstellt ( 0 bedeutet plus und 1 bedeutet minus ) kann das Ergebnis eines Linksshift allerdings auch negativ sein.

int x =  1073741824;
// x = 01000000 00000000 00000000 00000000 = 2^30

int y = x<<1 ;
// y = -2147483648
// y = 10000000 00000000 00000000 00000000 = -2^31

int x =  2147483647;
// x = 01111111 11111111 11111111 11111111 = 2^31 - 1

int y = x<<1 ;
// y = -2
// y = 11111111 11111111 11111111 11111110 = -2

oder umgekehrt aus einer negativen Zahl eine positive oder auch 0 werden.

int x =  -2147483648;
// x = 10000000 00000000 00000000 00000000 = -2^31

int y = x<<1 ;
// y = 0
// y = 00000000 00000000 00000000 00000000

Ungewohnt ist auch das folgende Verhalten des Shiftoperators.

int x =  1;
// x = 00000000 00000000 00000000 00000001

int y = x<<30 ;
// y = 01000000 00000000 00000000 00000000 = 2^30

int z = x<<31 ;
// z = 10000000 00000000 00000000 00000000 = -2^31

int u = x<<32 ;
// u = 00000000 00000000 00000000 00000001 = 1

int v = x<<33 ;
// v = 00000000 00000000 00000000 00000010 = 2

x<<32 gibt also nicht 0, wie man erwarten möchte, sondern entspricht x<<0, die Ausgangszahl bleibt also unverändert. x<<33 hat den selben Effekt wie x<<1. Eine genauere Untersuchung ermittelt die folgende Regel :

• x<<y  bedeutet   x<<(y%32)  für y>=0
  
  
• x<<y  bedeutet   x<<(y%32+32)  für y<0

Für die zweite Regel noch ein Beispiel

int x   = 16777215
// x = 00000000 11111111 11111111 11111111 = 2^24 - 1
int y = x<<-3  ;
// y = -536870912

int z = x<<29  ;
// z = -536870912

// -536870912  = 11100000 00000000 00000000 00000000

// um 8 linksshiften
// 11111111 11111111 11111111 00000000

// nochmal um 8 linksshiften
// 11111111 11111111 00000000 00000000

// und nochmal um 8 linksshiften
// 11111111 00000000 00000000 00000000

//und jetzt noch 5 mal linksshiften
// 11100000 00000000 00000000 00000000

Rechtsshift ( sign fill )    >>

Beim shiften nach rechts werden zwei Fälle unterschieden. man kann entweder nur Nullbits nachziehen (zero fill) oder das Vorzeichenbit nachziehen (sign fill). Hierfür gibt es in Java zwei unterschiedliche Rechtsshiftoperatoren: >> bedeutet sign fill, >>> bedeutet zero fill. Wir behandeln zunächst den sign fill Rechtsshiftoperator.

sign fill Rechtsshift einer positiven Zahl

int x = 23;
//  x = 0000 0000  0000 0000  0000 0000  0001 0111 = 23
int y = x>>1  ;
//  y = 0000 0000  0000 0000  0000 0000  0000 1011 = 11
    y = x>>2  ;
//  y = 0000 0000  0000 0000  0000 0000  0000 0101 = 5
    y = x>>3  ;
//  y = 0000 0000  0000 0000  0000 0000  0000 0010 = 2
    y = x>>4  ;
//  y = 0000 0000  0000 0000  0000 0000  0000 0001 = 1
    y = x>>5  ;
//  y = 0000 0000  0000 0000  0000 0000  0000 0001 = 0
    y = x>>6  ;
//  y = 0000 0000  0000 0000  0000 0000  0000 0001 = 0

Man sieht: In diesem Fall entspricht ein Rechtsshift um eine Stelle einer Ganzzahldivision durch 2. Jeder weitere Rechtsshift bedeutet wieder eine Ganzzahldivision durch 2. Das geht solange bis sich 0 als Ergebnis einstellt.

sign fill Rechtsshift einer negativen Zahl

In diesem Fall wird immer eine 1 nachgezogen, die Zahl bleibt also immer negativ.

int x = -23;
//  -23 =  1111 1111  1111 1111  1111 1111  1110 1001
int y   =  x>>1  ;
//  y   =  1111 1111  1111 1111  1111 1111  1111 0100 = -12
int y   =  x>>2  ;
//  y   =  1111 1111  1111 1111  1111 1111  1111 1010 = -6
int y   =  x>>3  ;
//  y   =  1111 1111  1111 1111  1111 1111  1111 1101 = -3
int y   =  x>>4  ;
//  y   =  1111 1111  1111 1111  1111 1111  1111 1110 = -2
int y   =  x>>5  ;
//  y   =  1111 1111  1111 1111  1111 1111  1111 1111 = -1
int y   =  x>>6  ;
//  y   =  1111 1111  1111 1111  1111 1111  1111 1111 = -1

Man sieht: Auch in diesem Fall entspricht ein Rechtsshift um eine Stelle einer Ganzzahldivision durch 2. Jeder weitere Rechtsshift bedeutet wieder eine Ganzzahldivision durch 2. Das geht solange bis sich -1 als Ergebnis einstellt.

Man beachte: Die Ganzzahldivision ist immer eine Division mit abrunden :

23/2  =  11

-23/2 = -12

Rechtsshift ( zero fill )    >>>

zero fill Rechtsshift einer positiven Zahl

Dieser Fall ist nicht neues. Für positive Zahlen gibt es keinen Unterschied zu sign fill, da ja eine 0 nachgezogen wird. Es gilt also wieder die Regel, Halbieren mit abrunden, bis sich 0 einstellt.

zero fill Rechtsshift einer negativen Zahl

Da nun eine 0 nachgezogen wird, wird die Zahl nach einem Shift positiv. Jeder weitere Rechtsshift halbiert dann wieder die positive gewordene Zahl, bis sich wieder die 0 einstellt. neu ist also lediglich der erste Schritt. Diesen betrachten wir näher.

int x = -23 ;
//  -23     =  1111 1111  1111 1111  1111 1111  1110 1001      // 2-komplement
int y = -23>>>1 ;
// -23>>>1  =  0111 1111  1111 1111  1111 1111  1111 0100      // 2 147 483 636

Obwohl man hier zwischen -23 und 2 147 483 636 zunächst keinen Zusammenhang erkennen kann, findet man doch mit ein wenig Geduld einen solchen :

 -1>>>1 = 2^31 - 1 = 2 147 483 647
 -2>>>1 = 2^31 - 1

 -3>>>1 = 2^31 - 2 = 2 147 483 646
 -4>>>1 = 2^31 - 2

 -5>>>1 = 2^31 - 3 = 2 147 483 645
 -6>>>1 = 2^31 - 3

 -7>>>1 = 2^31 - 4 = 2 147 483 644
 -8>>>1 = 2^31 - 4

 -9>>>1 = 2^31 - 5 = 2 147 483 643
-10>>>1 = 2^31 - 5

u.sw.

Mit einem kleinen Javaprogramm können sie dieses Verhalten bestätigen. Wir formulieren die folgende Regel:

•  x>>>1  =  2^31 - (1-x)/2

Für x = -23 ergibt sich damit 2^31 - 12 = 2 147 483 636 .

Promotion

byte b=1, x=2;

b<<x  // bedeutet  (int)b<<x

Analog für alle anderen Datentypen kleiner als int. Der Ausdruck muß also (mindestens) einer int-Variabeln zugewiesen werden. Die Typumwandlung findet vor dem shift statt !

byte b;

int x = b<<2  // bedeutet  (int)b<<2

Bei den zusammengesetzten Zuweisungsoperatoren ist noch ein zusätztlicher cast versteckt

b<<=x  bedeutet   b = (byte)(b<<x)

zusammen mit der Promotion dann also noch genauer

b = (byte)( (int)b<<x )