Bitoperation // Zweierpotenz

[owntYA]

Hallo,

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

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

[Tyrar]

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

Also statt dem

return h;

machst du

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.

[owntYA]

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.

[Dr. Coxxy]

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:

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);
	}

[owntYA]

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:

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 :/

[Tyrar]

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

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;
}

[Dr. Coxxy]

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

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.

[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.

[Tasiro]

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

[Dr. Coxxy]

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.

[Tyrar]

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.

[Dr. Coxxy]

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

[nerdsupreme]

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.^^

[owntYA]

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!

[Tasiro]

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.