Umwandlung Integer -> Gray-Bit-Darstellung

[tatra-bennl]

Hallo,

ich bräuchte mal wieder Hilfe in Sachen Java-Implementierung. Und zwar soll ich eine Funktion public static int toGray(int n) implementieren, die für eine positive natürliche Zahl n < 2^31 die zugehörige Gray-Bit-Darstellung berechnet.

d.h. z.B. für n = 5 ist der Graycode 0111 und somit das Ergebnis 7.

Ich habe mir überlegt, den eingegebenen Wert n (Integer) zunächst über die Funktion Integer.toBinaryString(...) in den entsprechenden Binärcode umzuwandeln, um diesen dann in den Graycode umzuwandeln, dann die Gray-Bit-Darstellung zu berechnen. (ist vielleicht etwas zu umständlich, aber das war zumindest erstmal mein Ansatz...)

Bisher sieht das so aus:

public class Gray {

	static int N;
	
	public static void main (String[] args)
	{
		N = Integer.parseInt(args[0]);
		
	    toGray(N);
		
	}
	
	public static int toGray(int n)
	{
		String x = Integer.toBinaryString(N);
		
		
		
		//Ansatz Graycode-Berechnung:
                //hier Teilstring an einer bestimmten Stelle (Index) auslesen und vergleichen, d.h.
                //wenn die Ziffer gleich ihrer Vorgängerziffer ist -> 0, sonst -> 1
                //dann alle ermittelten Zahlen zusammen => Graycode 
                //dann diese Darstellung wieder in eine Dezimalzahl (int) umwandeln und zurückgeben
	    
		
	    return n;
	}
	
}

An der besagten Stelle komme ich nicht weiter. Es gibt ja die Funktion IndexOf(...), die mir den Index eines gesuchten Teilstrings angibt. Jedoch bräuchte ich ja hier eine Umkehrfunktion dazu, d.h. eine Funktion, die den Wert des Teilstrings ausliest an einem bestimmten Index.

Ich freue mich über Antworten

MfG
Benjamin

 

[Thallius]

versuch es doch einfach mit substr();

Gruß

Claus

 

[tatra-bennl]

Danke! So jetzt habe ich das eingebaut und nun muss ja noch prüfen, ob die entsprechende Ziffer am Index i jeweils gleich ihrer Vorgängerziffer ist oder nicht. Wenn ja, dann 0 ausgeben. Wenn nein, dann 1 ausgeben.
Doch da hängt's noch bei mir...

public static int toGray(int n)
	{
		String x = Integer.toBinaryString(N);	//Binärcode der Zahl N
		
		
		int i = 0;
		int a = Integer.parseInt(x.substring(i));			
                //(i+1).Ziffer des Binärcodes

		while (i<x.length())
			i++;

NACHTRAG:

Bin nun doch schon einen Schritt weiter (dachte ich zumindest), aber so ganz richtig kann das noch nicht sein, weil die Werte, die als Graycode herauskommen, falsch sind.
Ich hatte mir das so überlegt:

public static int toGray(int n)
	{
		String x = Integer.toBinaryString(N);	//Binärcode der Zahl N
		
		
		int i = 0;
		int a = Integer.parseInt(x.substring(i));			//(i+1).Ziffer des Binärcodes
		
		while (i<x.length()) {
			i++;
		
		if (x.substring(i) == x.substring(i-1))
			System.out.print(0);
		else System.out.print(1);
		}

 

[stg]

Warum so kompliziert und nicht einfach ausrechnen? Ist ja kein Hexenwerk..

  public static void main(String[] args) {
    for(int i=0; i<16; i++) {
    	System.out.println("gray("+i+")="+gray(i));
    }
  }
  
  public static int gray(int i) {
  	return i^(i>>1);
  }

Ausgabe:

gray(0)=0
gray(1)=1
gray(2)=3
gray(3)=2
gray(4)=6
gray(5)=7
gray(6)=5
gray(7)=4
gray(8)=12
gray(9)=13
gray(10)=15
gray(11)=14
gray(12)=10
gray(13)=11
gray(14)=9
gray(15)=8

 

[tatra-bennl]

Ah ok, wusste nicht, dass das so einfach geht. Aber meine Methode war dann völlig falsch oder hätte man es auch so machen können? (rein theoretisch)

 

[Thallius]

Stg war schneller

 

[Gucky]

Ich weiß nicht, ob ich durch deinen Code ganz durchsteige aber ich glaube, der hätte noch weiterer Anpassungen bedürft, da substring einen Bereich zurückgibt. Und 10 in ein int geparsed ist 10 und nicht 2.
charAt hätte es wohl eher getan aber stgs Möglichkeit ist noch besser.

 

[tatra-bennl]

Also danke euch beiden erstmal bis hierher!

Hätte noch eine Frage:

um nun eine Umkehrfunktion fromGray zu implementieren, die aus einem eingegebenen Gray-Bit-Wert die zugehörige natürliche Dezimalzahl x liefert, müsste man doch eine Art "Umkehrung" von "entweder oder" finden, oder?
Also man müsste über die Binärdarstellung gehen oder geht das auch so "simpel" wie in der toGray-Funktion?

D.h. ich habe eine Zahl g in Gray-Bit-Darstellung. Dann gilt doch folgendes (wenn ich das richtig auffasse )
- die 1. Stelle der Binärdarstellung von g entspricht der 1. Stelle der Binärdarstellung von x
- eine 1 in g bedeutet immer, dass die nächste Stelle von x von ihrer Vorgängerstelle verschieden ist

Also muss man eine Zahl - ich nenne sie mal m - finden, so dass g^m=x gilt...

Das Problem ist, dass ich ja mit Integern rechne und dann am Ende auf einen Boolschen Wert käme, was ja nicht wirklich geht.

Ist mein Ansatz überhaupt richtig oder habe ich mir schon wieder zu komplizierte Gedanken gemacht?

 

[stg]

Es geht fast so einfach wie zuvor. Was müssen wir denn z.B. machen, um aus dem Gray(bit)Code 1011 den passenden Decimalcode zu bestimmen? Schauen wir uns die Zahl von links nach rechts an:
Erste Ziffer ist eine eins, also liegt die gesuchte Zahl zwischen 8 und 15
Zweite Ziffer ist eine Null, als ist die gesuchte Zahl zwischen 12 und 15
Dann kommt eine eins, also kommt nur 14 oder 15 in Frage.
Zuletzt wieder eine eins, also war die gesuchte zahl die 14.

Verallgemeinern wir das vorgehen in Java Code, so kommen wir zu

public static int toInt(int j) {
  for (int i = j >> 1; i != 0; i = i >> 1){
        j = j ^ i;
    }
    return j;
  }

gray(0)=0 -- toInt(0)=0
gray(1)=1 -- toInt(1)=1
gray(2)=3 -- toInt(3)=2
gray(3)=2 -- toInt(2)=3
gray(4)=6 -- toInt(6)=4
gray(5)=7 -- toInt(7)=5
gray(6)=5 -- toInt(5)=6
gray(7)=4 -- toInt(4)=7
gray(8)=12 -- toInt(12)=8
gray(9)=13 -- toInt(13)=9
gray(10)=15 -- toInt(15)=10
gray(11)=14 -- toInt(14)=11
gray(12)=10 -- toInt(10)=12
gray(13)=11 -- toInt(11)=13
gray(14)=9 -- toInt(9)=14
gray(15)=8 -- toInt(8)=15

 

[tatra-bennl]

Gut, die Bestimmung des Dezimalcodes aus dem Graycode heraus (z.B. 1011) ist mir klar.

Aber irgendwie erkenne ich nicht den Zusammenhang zu deinem Code und der Bestimmung aus der Gray-Bit-Darstellung (14)... Dein Code funktioniert richtig, aber den Zusammenhang krieg ich irgendwie nicht so ganz drauf...

Aber danke schön und frohe Weihnachten!