Bitoperation // Zweierpotenz

Page 1 of 2

03/21/2014 13:15 owntYA#1

Hallo,

ich moechte in C eine simple funktion generieren mit Bitshiftoperationen, die die h�chste Zweierpotenz zurueck gibt, durch die eine Zahl teilbar ist.

Code:

int bitcheck(unsigned int z)
{
	int i, h = 0;
	int x;
	for(i = 1; i<32; i++)
	{
		if(z&(1<<0))
		{
			return 0;
			break;
		}
	
		if(z&(1<<i))
		{
			h = i;
		}
	}
	return h;
}

void main()
{
	int check;
	unsigned int zahl;
	printf("Zahl: ");
	scanf("%d", &zahl);
	check = bitcheck(zahl);

	if(check == 0)
		printf("Ihre Zahl ist ungerade und somit nicht durch eine Zweierpotenz teilbar!\n");
	else
	{
		printf("Ihre Zahl ist durch die Zweierpotenz '2^%d' teilbar!\n", check);
	}
	system("pause");
}

Problem ist, ja das Programm gibt mir die h�chste Zweierpotenz korrekt aus.

Bei einer Zehn bekomme ich den Wert 2^3 zurueck (=8), aber korrekt teilbar ist das nicht. Ich m�chte das lediglich Zahlen wie 2, 4, 8, 16, 32, 64 usw. mir zurueckgegeben werden und nicht bei Modulo die h�chste ausgegeben wird.

Sprich eigentlich muesst ich ja bei dem UND-weisen bitshiften die Stellen 3,6,9,12,15,18,21... checken ob NUR dort eine 1 gesetzt ist.

Hope wer kann mir helfen,

vielen Dank!

Greetings.

Erg�nzung: OHNE MODULO-OPERATOR UND POTENZFUNKTION! REINE BITOPERATIONEN :)

03/21/2014 13:43 Tyrar#2

Ich verstehe die Frage zwar nicht ganz klar, aber ich versuche mal mein Gl�ck.

Also statt dem

Code:

return h;

machst du

Code:

return z & ~(1 << h) == 0 ? h : 0;

Damit w�rdest du vor dem return noch die restlichen Bits �berpr�fen, wenn 1 davon gesetzt ist (also z & ~(1 << h) != 0) w�rde deine Funktion 0 zur�ck geben. Ansonsten w�rde h zur�ck gegeben werden.

03/21/2014 13:51 owntYA#3

Danke fuer deine Antwort Tyrar.

Funzt leider nicht. Kannst du mir sagen wofuer "~" steht?

Um das ggfs nochmal zu konkretisieren.
Das Prog funktioniert soweit, nennt die bei egal welcher Zahl (falls ungerade, keine 2er-Potenz -- falls gerade die h�chste Zweierpotenz).

Gewollt ist aber, dass bei beispielsweiser einer 10 zur�ck kommt "keine Zweierpotenz" und nur bei werten wie 2/4/16/32/64/128 usw die 2er potenzen zurueckgegeben werden.

:)

03/21/2014 14:04 Dr. Coxxy#4

versteh ich das richtig, dass die funktion testen soll, ob die �bergebene zahl eine zweierpotenz ist und wenn ja welche?
wenn ja, z�hl doch einfach ob die anzahl der gesetzten bits == 1 ist, bzw. ob der wert &= ~found == 0 ist.

ps:
~ ist der invertierungsoperator.
pps:
da schenk ich dir:

Code:

bool IsPowerOfTwo(unsigned int Value, unsigned int* Power)
{
	unsigned int FoundBits = 0;
	*Power = 0;
	if (Value == 1)
	{
		return true;
	}
	for (unsigned int i = 0; i < 32; i++)
	{
		if ((Value & (1<<(31-i))) != 0)
		{
			if (FoundBits == 0)
			{
				*Power = 31-i;
			}
			else
			{
				return false;
			}
			FoundBits++;
		}
	}
	return (FoundBits == 1);
}

// Example:

	unsigned int Value = 32;

	unsigned int HighestPower;
	if (IsPowerOfTwo(Value, &HighestPower))
	{
		printf("%u ist eine Zweierpotenz: 2^%u\n", Value, HighestPower);
	}
	else
	{
		printf("%u ist KEINE Zweierpotenz, hoechste gefundene: 2^%u\n", Value, HighestPower);
	}

03/21/2014 15:14 owntYA#5

Danke Dr. Coxxy.

Ich schau mir das erstmal nicht an, mags selbst rausfinden.

Hab noch mal bissel was geandert.

Ich weiss dass der Ansatz passt, aber ich habe ein Problem mit der Schleifensteuerung:

Code:

int bitcheck(unsigned int z)
{
	int i, h = 0;
	int x;
	if(z&(1<<0)) // Wenn LSB 1; gib Wert 0 zur�ck!
	{
		return 0;
	}
	else		// Ansonsten...
	{
		for(i = 1; i<32; i++)
		{
			if(z&(1<<i))	// Wenn Zahl an Stelle i == 1, setze hoechste Stelle als Exponent auf h!
				h=i;
		}
		for(i=h-1; i >=0; i--)	// Hoechste Stelle - 1
		{
			if(z&(0>>i))		// Wenn alle Stellen nach der MSB 1 == 0 gesetzt sind ...
			{
				continue;		//check weiter...
			}
			else				// falls doch eine weitere 1 auftaucht...
			{
				return 0;		// gib 0 zur�ck
			}
			return h;			// gib Wert H zur�ck
		}
	}
}


void main()
{
	unsigned int check;
	unsigned int zahl;
	printf("Zahl: ");
	scanf("%d", &zahl);
	check = bitcheck(zahl);

	if(check == 0)
		printf("Ihre Zahl ist ungerade und somit nicht durch eine Zweierpotenz teilbar!\n");
	else
	{
		printf("Ihre Zahl ist durch die Zweierpotenz '2^%d' teilbar!\n", check);
	}
	system("pause");
}

Die Funktion gibt naemlich IMMER Null zurueck :/

03/21/2014 15:40 Tyrar#6

Entschuldige hatte da einen kleinen Fehler gemacht.
~ ist wie Coxxy schon sagt der Invertierungs operator, auch genannt NOT.

Bei meinem Ansatz sollte ein Bit an stelle h geschoben werden, invertiert und dann mit der AND operation �berpr�ft, ob alle Bits ausgenommen diesem 0 w�ren.
Wenn das der Fall w�re sollte h zur�ck gegeben werden und wenn nicht 0.

Coxxy's Ansatz ist allerdings auch nicht schlecht.

Ich hab mir meins nochmal angeschaut und die klammern vergessen.
Ich habe mir au�erdem mal die Freiheit genommen die Funktion ein wenig zu optimieren :p

[Only registered and activated users can see links. Click Here To Register...]

Code:

int bitcheck(unsigned int z)
{
int i, h = 0;
//int x; // x wird nicht verwendet
 
if(z & 1) // muss nicht in der schleife gemacht werden, ein einziges mal �berpr�fen reicht :p
{
return 0;
}
 
for(i = 31; i>0; --i) // direkt mit dem h�chsten bit anfangen ist hier lohnenswert
{
if(z&(1<<i))
{
h = i;
break;
}
}
 
return (z & ~(1 << h)) == 0 ? h : 0;
}

03/21/2014 15:42 Dr. Coxxy#7

ne, der ansatz ist net so dolle, �berleg dir erstmal einen ordentlichen in gedanken und schreib dann den code dazu:

1. filtere 0 aus (return FAIL)
2. filtere 1 aus (return 0)
3. durchsuche den int von links nach rechts nach gesetzten bits - sobald du eins findest ist dies das h�chste gesetzte bit
4. findest du mehr als ein bit ist es keine zweierpotenz mehr
5. MehrAlsZweiGesetzteBits ? return FAIL : return HoechsteGesetzteBit

dann wirst du auf �hnlichen code kommen wie ich oben, au�er das 0 ausfiltern und bitcnt brauchste dann auch net mehr, ist also noch etwas sauberer.

edit:
und da hat tyrar auch eine ordentliche l�sung gepostet.
problem bei nur einem r�ckgabetypen ist allerdings, dass 0 im prinzip eine g�ltige l�sung f�r value == 1 ist, k�nnte z.b. -1 bei nicht 2erpotenz zur�ckgeben.
d�rfte auch schneller sein, da der invertierungsvergleich vermutlich schneller ist als die schleife zuende bzw. bis zum n�chsten bit zu f�hren, wie bei mir, allerdings finde ich meine l�sung lesbarer/intuitiver.
am schnellsten d�rfte wohl sein einfach gegen eine tabelle aller m�glichen 2erpotenzen zu pr�fen, bzw. gibts afaik auf amd extensions assembleranweisungen wie bitcnt die das ganze verschnellern sollten.

edit2:
und das hier

Code:

if(z & 1) // muss nicht in der schleife gemacht werden, ein einziges mal �berpr�fen reicht :p
{
return 0;
}

ist falsch.
genauso wie die begr�ndung in dem printf.

03/21/2014 16:01 Tyrar#8

Wo ist denn z & 1 falsch? Ich bitte um eine Erkl�rung.
Damit wird direkt das 1 Bit raus gefiltert das nicht 1 sein darf.

03/21/2014 16:09 Tasiro#9

Mit x&(-x) l�sst sich das niedrigse gesetzte Bit (nicht dessen Position) berechnen.

03/21/2014 16:14 Dr. Coxxy#10

Quote:

Originally Posted by Tyrar

Wo ist denn z & 1 falsch? Ich bitte um eine Erkl�rung.
Damit wird direkt das 1 Bit raus gefiltert das nicht 1 sein darf.

doch, darf es, n�mlich bei dem wert 1 der der 2erpotenz 2^0 entspricht.

03/21/2014 16:29 Tyrar#11

Quote:

Originally Posted by Dr. Coxxy

doch, darf es, n�mlich bei dem wert 1 der der 2erpotenz 2^0 entspricht.

So wie ich das verstanden habe wollte der TE auch diese M�glichkeit ausschlie�en.
Ansonsten hast du nat�rlich recht, ja.

03/21/2014 16:36 Dr. Coxxy#12

Quote:

Originally Posted by Tyrar

So wie ich das verstanden habe wollte der TE auch diese M�glichkeit ausschlie�en.
Ansonsten hast du nat�rlich recht, ja.

glaub eher TE wei� net, dass 1 eine 2erpotenz ist :P

03/21/2014 17:15 nerdsupreme#13

Ich verstehe die Frage nicht ganz.

Meinst du dass du nur Ergebnisse willst wie z.B.:

Zahl = 16, Ergebnis: 2^4 ? Also quasi w�re die Zahl 10 nicht teilbar wegen weil modulo nicht zul�ssig?^^

EDIT: und falls dem so ist: ich traue mich nicht diese einfache l�sung zu posten.^^

03/21/2014 18:00 owntYA#14

Ich merk schon, ich bin ein wenig �berfordert.
Solch l�cherliche Aufgabe, die dennoch zu viel von mir verlangt :-D

Aufgabenstellung ist:
"Erstellen Sie eine Funktion, die eine vorzeichenlose ganze Zagl �bergeben bekommt und die gr��te Zweierpotenz zur�ckgibt, durch die die Zahl teilbar ist.

Verwenden Sie in der Funktion nur Bitoperationen. Verwenden Sie insbesondere keine Potenzfunktion und auch keinen Modulo-Operator."

F�r mich gilt ganz klar:
1. Check nach dem MSB an dem 1 gesetzt ist und speicher diese Position (zB. in der Variable h).
2. Check ob alle niedrigeren Bits mit 0 gesetzt sind - falls ja return h, um den Exponent zur Zwei zur�ckzugeben!

Bei 2^0 bin ich mir nicht sicher. Ist zwar Zweierpotenz, aber auch die Zahl drei hat eine 1 beim LSB stehen.

Greetings.

Sorry f�r die Verwirrung, danke an euch!

03/21/2014 18:16 Tasiro#15

Quote:

Originally Posted by owntYA

"Erstellen Sie eine Funktion, die eine vorzeichenlose ganze Zagl �bergeben bekommt und die gr��te Zweierpotenz zur�ckgibt, durch die die Zahl teilbar ist. [...]"

1 ist eine Zweierpotenz, damit ist 1 laut Aufgabenstellung auch als solche zu ber�cksichtigen.

Page 1 of 2