Darstellung negativer Integer

Objektorientierte Programmiersprache auf Basis einer virtuellen Maschine (https://www.oracle.com/java/)
Antworten
Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Darstellung negativer Integer

Beitrag von Dirty Oerti » Do Nov 11, 2010 11:31 pm

Tag zusammen :)

Ich schreibe einen RadixSort für die Uni (das schnellste Sortierverfahren gewinnt einen Preis ;) ) und erweitere diesen nun auf negative Zahlen.
Das ist soweit kein Problem (das MSB muss einfach nur genau andersherum betrachtet werden, ich kann den Code ja bei Gelegenheit , also nach Abgabetermin, offenlegen)
Zumindest, wenn die Darstellung negativer Integer bei Java einheitlich ist.

Zuerst stellt sich noch die andere Frage: Sind "int" bei Java IMMER 32 Bit lang?
Dann die Frage an euch:

Ergibt der folgende Code die gleiche Ausgabe - egal auf welcher Maschine/Betriebssystem/JavaVM ?

Code: Alles auswählen

public static void printBinary(int n)
  {
    System.out.print("" + n + " = 0b");
    for(int i = 31; i >= 0; i--)
    {
      System.out.print("" + ( ((n&(1<<i)) == 0) ? "0" : "1")   );
    }
    System.out.println("");
  }

Code: Alles auswählen

    printBinary(0x7FFFFFFF);
    printBinary(2);
    printBinary(1);
    printBinary(0);
    printBinary(-1);
    printBinary(-2);
    printBinary(0x80000000);

2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
Wäre cool, wenn das jemand wüsste.
Oder auch, wenn ihr es bei euch testen könntet (mit Angabe des Betriebssystems, der JavaVM, 32/64Bit, Prozessorarchitektur)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

MoonGuy
Beiträge: 231
Registriert: Fr Okt 08, 2010 2:49 pm

Re: Darstellung negativer Integer

Beitrag von MoonGuy » Fr Nov 12, 2010 3:19 pm

Dirty Oerti hat geschrieben:Zuerst stellt sich noch die andere Frage: Sind "int" bei Java IMMER 32 Bit lang?
Mein Java Buch sagt ja. Bin mir aber selbst nicht sicher. Denke das hängt bei Java ausschließlich von der VM ab.
Dirty Oerti hat geschrieben: Dann die Frage an euch:

Ergibt der folgende Code die gleiche Ausgabe - egal auf welcher Maschine/Betriebssystem/JavaVM ?
Maschine und Betriebssystem: Ja, müsste.
JavaVM: Ich nicht wissen. Tut mir Leid.
Dirty Oerti hat geschrieben:Oder auch, wenn ihr es bei euch testen könntet (mit Angabe des Betriebssystems, der JavaVM, 32/64Bit, Prozessorarchitektur)

Code: Alles auswählen

2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
Windows 7,Version 6 Update 22 VM, 64Bit, Duo Core mit 2,66 GHz und 2,67 GHz Intel powered.

Hoffe das hilft dir.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Darstellung negativer Integer

Beitrag von Xin » So Nov 14, 2010 2:14 pm

Habe mal eben nachgeguckt und int ist in Java wohl grundsätzlich 32 Bit.

Ich habe das ganze mal in Quelltext gegossen, weil es irgendwo auch blöd ist, wenn sich das jeder selbst zusammenfrickeln muss.

Code: Alles auswählen

class DirtyOerti
{
  public static void printBinary(int n)
  {
    System.out.print("" + n + " = 0b");
    for(int i = 31; i >= 0; i--)
    {
      System.out.print("" + ( ((n&(1<<i)) == 0) ? "0" : "1")   );
    }
    System.out.println("");
  }

  public static void main( String [] bla )
  {
    printBinary(0x7FFFFFFF);
    printBinary(2);
    printBinary(1);
    printBinary(0);
    printBinary(-1);
    printBinary(-2);
    printBinary(0x80000000);
  }
}
Debian 64 Bit auf Intel i7, OpenJDK
Dann:

Code: Alles auswählen

xin@trinity:~/Documents$ java -version
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.2) (6b18-1.8.2-4)
OpenJDK 64-Bit Server VM (build 16.0-b13, mixed mode)
xin@trinity:~/Documents$ javac -version
javac 1.6.0_18
xin@trinity:~/Documents$ javac dirtyoerti.java
xin@trinity:~/Documents$ java DirtyOerti
2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
xin@trinity:~/Documents$ uname -a
Linux trinity 2.6.35.3 #1 SMP Sun Aug 22 12:36:51 CEST 2010 x86_64 GNU/Linux
Ubuntu 10.04 32 Bit auf Sempron 2400, OpenJDK

Code: Alles auswählen

xin@faculty:~$ javac -version
javac 1.6.0_18
xin@faculty:~$ javac dirtyoerti.java 
xin@faculty:~$ java DirtyOerti
2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
xin@faculty:~$ uname -a
Linux faculty 2.6.32-25-generic #45-Ubuntu SMP Sat Oct 16 19:48:22 UTC 2010 i686 GNU/Linux
MacOS 10.6 Core2Duo, Java
Der Mac läuft - wenn ich das richtig sehe - im 32 Bit Modus.

Code: Alles auswählen

Neo:~ xin$ java -version
java version "1.6.0_22"
Java(TM) SE Runtime Environment (build 1.6.0_22-b04-307-10M3261)
Java HotSpot(TM) 64-Bit Server VM (build 17.1-b03-307, mixed mode)
Neo:~ xin$ javac -version
javac 1.6.0_22
Neo:~ xin$ javac dirtyoerti.java 
Neo:~ xin$ java DirtyOerti
2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
Neo:~ xin$ uname -a
Darwin Neo.local 10.4.0 Darwin Kernel Version 10.4.0: Fri Apr 23 18:28:53 PDT 2010; root:xnu-1504.7.4~1/RELEASE_I386 i386
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Darstellung negativer Integer

Beitrag von Dirty Oerti » So Nov 14, 2010 3:08 pm

Gut, danke euch zweien :)
Daraus schließe ich mal, dass die Darstellung wohl zu einer großen Wahrscheinlichkeit einheitlich ist.

(Code folgt am 1.12. Sollte ich es vergessen, dann schreibt mich an. Ist nämlich ein super linearer Algorithmus zum Sortieren beliebiger Zahlen. Derweil mal der Link mit Informationen dazu: http://codercorner.com/RadixSortRevisited.htm)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Darstellung negativer Integer

Beitrag von Dirty Oerti » Do Dez 09, 2010 10:49 pm

Tag :)

Also der Code hat gewonnen.
^^
Allerdings hab ich den Code stark vereinfacht abgegeben. Die Aufgabe war es, 10 Mio positive Integer zu sortieren.
Der Algorithmus kann aber auch leicht erweitert werden, um so z.B. auch floats etc zu sortieren.
Mit Hilfe einer Liste geschieht das ganze sogar ohne zusätzlichen Speicheraufwand, dafür natürlich etwas langsamer.
In einer Liste kann man auch Objekte speichern, die dann nach best. Attributen sortiert werden.
Da der Algorithmus stabil ist, kann man so auch durch mehrmaliges Sortieren eine Permutation erzeugen, die auf erster Ebene nach einem, auf niedrigerer Ebene nach einem anderen Attribut sortiert ist.

Code: Alles auswählen

public static void radixBasic(int [] a)
  {
    int[] counter = new int[256];
    int[] buffer = new int[a.length];
    for(char pass = 0; pass < 4; pass++)
    {
      for(int it = 0; it < 256; it++)
      {
        counter[it] = 0;
      }
      for (int it = 0; it < a.length; it++)
      {
        counter[(  (a[it]>>(pass<<3))&(0xFF)  )]++;
      }
      for (int it = 0; it < 255; it++)
      {
       counter[it+1] += counter[it];
      }
      for (int it = (a.length-1); it >= 0; it--)
      {
        buffer[--counter[(a[it]>>(pass<<3))&(0xFF)]] = a[it];
      }
      for (int it = 0; it < a.length; it++)
      {
        a[it] = buffer[it];
      }
    }
  }
Außerdem sind 3 (anstatt von hier 4) Passes wohl noch ein Stück optimaler.
Richtig zum Tragen kommt das aber erst, wenn auch negative Werte betrachtet werden, da dann der letzte Fall ein Sonderfall ist und dann sowieso getrennt betrachtet werden muss.

*Edit*
Hier eine Version, die auch negative Zahlen berücksichtigt. Auf deren Basis habe ich angefangen.
Mit floats funktioniert das im Übrigen genauso.

Code: Alles auswählen

public static void FIRSTradixSort(int[] A)
  {
    int feldlaenge = A.length;
    int[] zero = new int[feldlaenge];
    int[] one = new int[feldlaenge];
    int z,o,i,z_it,o_it;
    // Standard RadixSort
    for( int b = 0; b < 31; b++)
    {
      z = 0;
      o = 0;
      for( i = 0; i < feldlaenge; i++)
      {
        if( (A[i] & (1<<b)) == 0 )
        {
          zero[z] = A[i];
          z++;
        }
        else
        {
          one[o] = A[i];
          o++;
        }
      }
      i = 0;
      for( z_it = 0; z_it < z; z_it++,i++)
      {
        A[i]=zero[z_it];
      }
      for( o_it = 0; o_it < o; o_it++,i++)
      {
        A[i]=one[o_it];
      }
    }
    // MSB gibt Vorzeichen an, 1 -> negativ, damit kleiner, also umgekehrt zu
    // oben verfahren. Da Leadbits bei negativen Zahlen 1 und nicht 0 sind, 
    // werden groessere Absolutwerte automatisch zu kleineren negativen Werten.
    z = 0;
    o = 0;
    for ( i = 0; i < feldlaenge; i++)
    {
      if( (A[i] & (0x80000000)) == 0 )
      {
        zero[z] = A[i];
        z++;
      }
      else
      {
        one[o] = A[i];
        o++;
      }
    }
    i = 0;
    for( o_it = 0; o_it < o; o_it++,i++)
    {
      A[i]=one[o_it];
    }
    for( z_it = 0; z_it < z; z_it++,i++)
    {
      A[i]=zero[z_it];
    }
  }
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Antworten