Bitblock untersuchen

[tizian]

Hallo,

Ich habe ein Problem mit einem Programm, das ich gerade in C schreibe. Dabei will ich bei einer Bit-Zahl (ein integer, wird mit 32 Bits dargestellt) zählen, wie viele "Blöcke" vorkommen. Blöcke sind zusammenhängende Ketten von Nullen oder Einsen. Die Zahl '01110000' besteht z.B. aus den Blöcken '0', '0000' und '111'.

Ob ein Block aus Nullen oder Einsen besteht ist mir egal, hier hätte ich einfach einen Block der Länge 1, einen der Länge 3etc. gezählt.

Ich habe ein Programm geschrieben, das dieses Leistet, aber irgendwie ist da ein Fehler drin den ich nicht finde. Weiß hier jemand mehr als ich?

Danke im vorraus,

Tizian

--------------------------------------------------------------------------

--------------------------------------------------------------------------

Hier der Code der entscheidenden Programmstruktur, Soll die Blöcke mit Einsen zählen:

--------------------------------------------------------------------------

// Untersuchung nach Bloecken

			// Zaehle Bloecke mit Einsen


				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 1) {

					cp++;				

					}

					else{

						if(cp != 0){

							blockliste[cp]++;

							cp = 0;

						}

					}

				}


                        // Zaehle Bloecke mit Einsen


				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 0) {

					cp++;				

					}

					else{

						if(cp != 0){

							blockliste[cp]++;

							cp = 0;

						}

					}

				}

------------------------------------------------------------------------- ------------------------------------------------------------------------- Und hier das ganze Programm: -------------------------------------------------------------------------

#include<stdlib.h>

#include<stdio.h>



int main(void){


int n, k, i, cp, cm;

char ch;

int  blockliste[31];


		for(i=0;i<31;i++)

			blockliste[i]=0;




do{

printf("Welche Zahl soll untersucht werden?( n, hexadezimal)\n");

scanf("%x", &n);







	// Kontrollausgabe der eingegebenen Zahl binaer


		printf("\n\n");

		printf("Kontrollausgabe binaer:\n\n");


			for(i = 31; i >= 0; i--){

				if(n >> i & 1)

					printf("1");

				else printf("0");

			}

			printf("\n\n");


	// Untersuchung nach Bloecken

			// Zaehle Bloecke mit Einsen


				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 1) {

					cp++;				

					}

					else{

						if(cp != 0){

							blockliste[cp]++;

							cp = 0;

						}

					}

				}



				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 0) {

					cp++;				

					}

					else{

						if(cp != 0){

							blockliste[cp]++;

							cp = 0;

						}

					}

				}









	// Ausgabe der Bloecke


			for(i=1; i<32; i++){

				if(blockliste[i] > 1){

					printf("Laenge %d: %d Bloecke\n", i, blockliste[i] );

				}

				if(blockliste[i] == 1){

					printf("Laenge %d: %d Block\n", i, blockliste[i] );

				}

			}


		for(i=0;i<31;i++)

			printf("laenge %d: %d \t", i, blockliste[i]);







		printf("Nochmal? (J/N)");

		scanf("\n%c", &ch);


}

while(ch == 'J' | ch == 'j');


		system("pause");

		return 0;



}

[Klotzkopp]

irgendwie ist da ein Fehler drin den ich nicht finde.

Das ist eine Fehlerbeschreibung, die bei der Fehlersuche leider nicht im Geringsten weiterhilft. Viel hilfreicher wäre hier gewesen, wie sich dieser Fehler auswirkt.

Dass du ihn nicht findest, versteht sich von selbst, sonst würdest du hier ja nicht nachfragen.

Aber hier mal ein paar Tipps:

• Es wäre wohl besser, den Inhalt von blockliste innerhalb der do-Schleife zurückzusetzen.
  
• Die erste Ausgabeschleife (warum hast du überhaupt zwei davon?) ist falsch: i ist um 1 zu groß.
  
• Dein Test, ob ein Bit nicht gesetzt ist, ist falsch.
  
• Den letzten Block zählst du grundsätzlich nicht mit.
  
• Dein Programm kann Blöcke der Länge 0 zählen, welche gar nicht auftreten können. Dafür kann es nicht mit Blöcke der Länge 32 umgehen.
  

[tizian]

Hallo,

Der Fehler ist, das die Blöcke nicht korrekt gezählt werden ;-).

Genauer, in dem Probebeispiel, mit dem ich getestet habe, wurde ein Block der Länge 1 nicht mitgezählt. Bei einer anderen Zahl waren glaube ich sogar noch mehr Fehler dabei, das habe ich jetzt nicht mehr im Kopf.

Zu deinen weiteren Anmerkungen:

Ich habe zwei Ausgabeschleifen, weil ich vergessen habe eine zu löschen. :-) Bei meiner Fehlersuche hatte ich den Verdacht, es würde vielleicht nur die ausgabe nicht funktionieren.

Das i in der Ausgabeschleife ist um eins zu groß, weil Blöcke der Länge Null nicht ausgegeben werden sollen.

Der Fehler scheint also in der Routine mit der Bitabfrage zu liegen. Den Teil werde ich mir morgen nochmal genauer ansehen.

Danke & Ciao

Tizian

[Klotzkopp]

Der Fehler ist, das die Blöcke nicht korrekt gezählt werden ;-).

Das ist ja schon mal etwas, womit man auch etwas anfangen kann. Es hätte ja auch ein Compilefehler sein können

Bei einer anderen Zahl waren glaube ich sogar noch mehr Fehler dabei, das habe ich jetzt nicht mehr im Kopf.

Das wäre aber für die Helfer ziemlich wichtig.

Das i in der Ausgabeschleife ist um eins zu groß, weil Blöcke der Länge Null nicht ausgegeben werden sollen.

Dein blockliste-Array hat nur 31 Elemente. Du darfst als Index also nur 0 bis 30 (!) benutzen. blockliste[31] darfst du nicht verwenden, blockliste[32] schon gar nicht.

Der Fehler scheint also in der Routine mit der Bitabfrage zu liegen.

Wie gesagt, da sind mehrere Fehler drin.

[tizian]

Hallo,

Das ist ja schon mal etwas, womit man auch etwas anfangen kann. Es hätte ja auch ein Compilefehler sein können

Das wäre aber für die Helfer ziemlich wichtig.

Da habe ich mich ungenau ausgedrückt. Bei meiner ursprünglichen Testzahl (0xD2F32FED) wird nur ein Block der Länge 1 nicht mitgezählt. Bei verschiedenen anderen Zahlen sind aber mehr nicht gezählte Blöcke aufgetreten.

Dein blockliste-Array hat nur 31 Elemente. Du darfst als Index also nur 0 bis 30 (!) benutzen. blockliste[31] darfst du nicht verwenden, blockliste[32] schon gar nicht.

Das hab ich mal korrigiert.

Wie gesagt, da sind mehrere Fehler drin.

Ich hab mir den Bereich jetzt nochmal genauer angesehen und keinen (falsch - einen) Fehler gefunden. Meine Gedanken dazu:

Meine Methode, den Bitblock auszulesen funktioniert, denn die Schleife, mit der ich die binäre Kontrollausgabe generiere, funktioniert. Das variieren mit den Grenzen der Schleife bringt kein ebenfalls funktionierendes Ergebnis. Einen Zufallstreffer schließe ich hier mal aus.

Dann zur Schleife, die die Blöcke zählt:

				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 1)

Erstmal wird die Hilfsvariable cp initialisiert. In der for-Schleife laufe ich das Bit (32 Stellen) durch. Für die Position des Bits , an der sich eine '1' befindet, wird die if-Bedingung 'true'. Die Position der '1' wird durch den Wert von 'i' in der for-Schleife bezeichnet. Die if-Bedingung:

	if(n >> i & 1) {

			cp++;				

	        }

Wenn an der Stelle i im Bitblock eine '1' kommt, dann wird der Counter cp um 1 erhöht. Hat der 'Parser' (korrekter Begriff?) z.B. eine Reihe von drei Einsen durchlaufen, hat cp den Wert 3. Was passiert, wenn der einser-Block zuende ist, also im Bitblock eine 0 erscheint? Dann liefert die if-Bedingung den Wert 'false' und wird nicht ausgeführt. Dann kommt die else-Bedingung zum Zug.

	else{

		if(cp != 0){

			blockliste[cp]++;

			cp = 0;

		}

Erst wird mit einer weiteren if-Bedingung geprüft, ob es die erste Null ist. Das ist der Fall, wenn cp nicht den Wert Null hat. In diesem Fall wird der Wert blockliste[cp] um eins erhöht. Denn es wurde soeben ein Block der Länge cp gefunden. cp wird dann wieder auf Null gestzt, um einen weiteren Block zu zählen. Beim schreiben dieses Textes fällt mir auf, das ich einen Fall übersehen habe: Der Bitblock endet. Dann wird nicht weitergelesen, und der letzte Block nicht gezählt. Also füge ich einen weiteren Block ein:

	if((i == 0) && (cp != 0)){

		blockliste[cp]++;

		cp = 0;

		}

Mit meiner Prüfzahl funktioniert das Programm jetzt (besser gesagt: liefert das richtige Ergebnis), aber bei anderen Zahlen scheinen die 0-Blöcke nicht gezählt zu werden. Die Prozedur ist analog geschrieben. So, das war jetzt ein langer Text, ich hoffe er war verständlich. Vielleicht kann mir jetzt jemand meinen (Denk)fehler aufzeigen. Im Anschluss nochmal der komplette Code der Prüfprozedur. Danke & Ciao Tizian -------------------------------------------------------------------------- --------------------------------------------------------------------------

	// Untersuchung nach Bloecken

			// Zaehle Bloecke mit Einsen


				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 1) {

					cp++;				

					}

					else{

						if(cp != 0){

							blockliste[cp]++;

							cp = 0;

						}

					}

					if((i == 0) && (cp != 0)){

						blockliste[cp]++;

						cp = 0;

					}

				}




			// Zaehle Bloecke mit Nullen


				cp=0;

				for(i=31; i >= 0; i--){

					if(n >> i & 0) {

					cp++;				

					}

					else{

						if(cp != 0){

							blockliste[cp]++;

							cp = 0;

						}

					}

					if((i == 0) && (cp != 0)){

						blockliste[cp]++;

						cp = 0;

					}

				}

[Klotzkopp]

Diese Bedingung hier

n >> i & 0

ist einfach totaler Blödsinn. Damit kannst du nicht prüfen, ob das Bit an Stelle i nicht gesetzt ist. Dieser Ausdruck ist nämlich niemals wahr. Du verknüpfst da einen Wert binär-und mit 0, das Ergebnis ist immer 0, also false.

Das meinte ich mit "Dein Test, ob ein Bit nicht gesetzt ist, ist falsch."

[tizian]

Hallo,

Ach ja, manchmal sieht man den Wald vor lauter Bäumen nicht. Hätte mir besser nochmal die binären Verknüpfungen angeschaut, die hatte ich anscheinend falsch im Kopf.

Danke für deine Hilfe!

Ciao

Tizian

[Jan Jansen]

Wie wäre folgender Lösungvorschlag:

Wenn die Ziffer der aktuellen Stelle gleich der Ziffer der vorherigen Stelle ist, dann fängt keine neue Gruppe an,

sonst erhöhe die Anzahl der Gruppen

Du musst beim Durchlauf durch deine Zahl nur immer die letzte Ziffer für einen Vergleich aufheben (und etwas Sonderbehandlung für die erste Ziffer einbauen)