Einzelne Bits ansprechen/Länge von Zahl

P

PeasantKing

0
Wie kann ich in C an die einzelnen bits eines Integers herankommen? Ich will damit überprüfen, ob diese gesetzt sind oder nicht. Ich benötige das z.B. beim modularen Potenzieren (fragt nicht warum *gg). Wenn man dem int a z.B. 13 zuweist, weiß ich, durch
Code: 
int a=13;
oder so, dann müssten doch die bits des integers folgendermaßen gesetzt sein:
Code: 
0000 0000 0000 1101
Und wie kann man jetzt die einzelnen bits auslesen, z.B. überprüfen, ob bit x eine 1 ist oder nicht?

Meine zweite Frage knüpft an diese an:
Wie ist es möglich, die "Bitlänge" der Zahl zu bestimmten? Könnte man eventuell eine Fkt schreiben, die die Bits auf gesetzt oder nicht überprüft und sich jedes mal die höchste Stelle, wo eine 1 vorkam, merkt? oder gehts auch einfacher? Irgendwelche Tricks? Bei der obrigen Zahl wäre es ja die Länge 4 (Bit 0-3), da das 3. Bit das letzte is, welches gesetzt ist. Die Funktion "sizeof(a)" gibt ja nur die belegten bytes an, oder?
 
hi,

1. wenn du eine zahl durch 2^n teilst, und der rest ist 1, ist das bit gesetzt, bei 0 ist es nicht gesetzt. um den rest zu ermitteln, kannst du den modulo operator nutzen (z.B. % in c/c++) [und natürlich immer wieder abziehen]

2. wenn du erstmal eine funktion hast, die dir die bitbelegung an n-ter stelle zurückgibt (also zB getbit(i,n) ) kannst du mit Hilfe einer einfachen Schleife überprüfen, wo das letzte bit steht: dazu nimmst du dir einfach eine hilfsvariable (zB m) und setzt sie auf einen wert, der nicht vorkommen kann, (zB -1), dann gehst du mit einer schleife einfach alle möglichen positionen durch (beim int also von 0 bis 15) und wenn du mit getbit(i,n) eine 1 erhältst, überschreibst du m mit n. nach durchlauf der schleife hat m dann die stelle des letzten 1er bits (oder -1, wenn keine 1er bits vorkamen).

in c sieht das dann so aus:

//ntes bit von i:
byte getbit(int i, byte n)
{
int i2 = i;
for {int m = 0; m < n; m++} i2 = i2 - int(pow(2,m);
return(i2 % pow(2,n) );
}

//bitlänge
int bitlength(int i)
{
int m = -1;
for (byte n = 0;n < 16; n++)
if (getbit(i,n) == 1) m = n;

return(m);
}


ich hoffe das hat dir geholfen!


gruß

blueflash aka flashblue aka greenflash


[jetzt sollte es gehen]
 
das ganze kannst du über den binären UND operator machen
jede einzelen stelle wird mit 1 UND-verknüpft
ist das ergebnis 0 ist das bit nicht gesetzt, sonst ist es gesetzt
die zahl mit der du deine ausgangszahl jeweils UND-verknüfpst, erreichts jeweils dadurch dass du die zahl 1 um x stellen links-shiftest
hier mal n kleines beispiel programm

Code: 
#include <stdio.h>

int binSizeOfInt(int zahl) {
	int length=0;
	for(int i=0; i<32; i++) {
		if( zahl & (1 << i))	{
			length = i+1;
		}
	}
	return length;
}

void main() {
	int zahl = 3;
	printf("%d\n", binSizeOfInt(zahl));
}
also veranschaulicht passiert folgendes (von hinten nach vorne)
0000000000001101 // zahl 13
0000000000000001 // 1 (0 mal linksgeshiftet)
UND verknüpft (&)
ergebnis 0000000000000001 -> bit gesetzt

nächster schleifendurchlauf
0000000000001101
0000000000000010 // 1 (1 mal linksgeshiftet)
UND verknüpft (&)
ergebnis 0000000000000000 -> bit nicht gesetzt

usw...

wenn das bit gesetzt ist, jeweils die aktuelle position i+1 als länge speichern
 
@ blueflash: Nicht ich will wissen, wie man eine Zahl in das Binärsystem umwandelt. Ich wollte auch nicht, dass das das (scheiß das ;) ) C-Programm für mich macht, da ich die bits direkt in einer Schleife kontrollieren wollte auf gesetzt oder nicht, ähnlich deiner unten. Allerdings scheint das nicht so wirklich zu funktionieren. Kann es sein, dass das irgendetwas spezielles aus C++ ist? Weil beim Wörtchen byte nörgelt mein Compiler, und bei i modulo pow(2,n) nörgelt er auch...

@ivegotmail: Deine Lösung kommt mir als C-Anfänger wirklich einfacher vor. Die Vorschläge von blueflash sind ganz schön heftig für mich am Anfang gewesen. Auch dir dickes Danke daher! btw, schönen (und passenden) avatar *gg
 
tja, schön, dass wir helfen konnten:

zur einfacheit: mein ansatz ist der mathematische und ohne probleme zB auch in funktionalen sprachen anwendbar.

ivegotmail hat den ansatz der logischen programmierung gewählt. ist schneller, keine frage, aber nicht unbedingt portierbar.

mach halt, was dir besser liegt!
 
Ja stimmt, das habe ich ja auch mehr oder weniger zum Ausdruck gebracht, allerdings gibt es mit dem Code Probleme. Ich weiß es nicht, aber ich denke mal "byte" kommt aus C++, oder? Weil mein Compiler (DJGPP) kennt das nicht als Datentyp, ist mir allerdings von Pascal/Delphi her bekannt, ähnlich meckert er auch bei i modulo pow(.... rum. Habe byte spontan einfach mal mit short ersetzt -> Problem der Kenntnis behoben. Das behebt allerdings nicht das Problem mit der modulo-Operation: "invalid oparands to binary %" spuckt der gute gcc aus :) i%pow(2,n) bedeutet ja nichts anderes als das, was du oben gesagt hast, Zahl mod 2 hoch n, wobei n die bitstelle angibt. pow(a,b) liefert doch a^b, oder? *gg.
Ich werde mal noch ein wenig rumprobieren, wollte eigentlich schon um 10 die Luken schließen und noch englisches HDR lesen :)
Ich denk mir das so:
zahl : 2 = zahl2, rest 1 --> 1
zahl2:2= zahl3, rest 1--> 0
...
zahln:2 = zahln+1, r 1 --> 1

die zahl ist ja dann 10....1 binär geschrieben.
daher ist i%pow(2,n) nur die halbe wahrheit, oder?
 
na gut, das mit byte kann sein, short ist ANSIC++, den muss ich mir an meinen hut stecken. sry.

es kann sein, dass es du pow mit int() erst noch typecasten musst, da es einen float zurückgibt!
 
pow ist also nicht potenzieren für ganze zahlen wie ich vermutete => selber "hochfunktion" schreiben? ...hm, dann muss ich mir jetzt das "typecasten" reinziehen. gibts da sowas wie trunc() in pascal ? *g. Omg!!! Ich koch' mir erstmal einen ordentlichen Pott Kaffe!

Ich denk mir das so:
zahl : 2 = zahl2, rest 1 --> 1
zahl2:2= zahl3, rest 1--> 0
...
zahln:2 = zahln+1, r 1 --> 1

die zahl ist ja dann 10....1 binär geschrieben.
daher ist i%pow(2,n) nur die halbe wahrheit, oder?

zahl:2 = zahl2, rest 1 ist klar, geht mit i%pow(2,n)
Wie sieht die Zahl denn aus, wenn man eine Bitverschiebung nach rechts macht? ist z.B. 13 dann nicht 6, da 13:2 = 6, rest 1? Holla ich klopp hier heute mehr in meine Birne als in 3 Jahren Infounterricht im "Leistungskurs" :)
 
gaaaanz ruhig, is ganz einfach: schreib einfach int(pow(a,b)) das sollte funktionieren.
das nennt sich explizite typkonvertierung, die parameter werden implizit vom compiler umgewandelt.
 
ok danke, allerdings siehe vorheriger post *gg, tricks wie die möglichkeit der implizieten Typenkonvertierung ist genau das, was mir in Pascal immer gefehlt hat (oder ich wusste nicht davon, wie jetzt, vermute aber ersteres)
brauch unbedingt die Stellenzahl von einer Zahl als binär, also z.B. 4 bei 13 :)

int bitmuster(int i)
{
int m = -1;
for (byte n = 0;n < 16; n++)
if (getbit(i,n) == 1) m = n;

return(m);
}

Geht aber glaub ich nicht damit, oder?? als zahl (int) kommt meinetwegen 13 angeflattert.
für n= 0 bis 15 dann alle n-ten bits durchackern is mir klar, allerdings liegt der Fehler glaube ich in getbit, denn diese liefert meines erachtens nicht den wert des n-ten bits, oder?
angenommen n ist 2, dann gibt getbit bei 13 mod (2^2) eine 1 zurück (13/4=3 rest 1), bei 2^3 allerdings 5, oder ? (13 / 8 = 1, rest 5 )
 
Vielen dank (zum tausendsten mal, aber ich mach es auch noch ein tausend und einstes mal für deine hilfe ;) ).
PS: Im Post mit den ganzen zahl:zahl=.., rest und so steht auch etwas von Bitverschiebung. Ob das nützlich wäre, weiß ich, wenn man das nach der Masche aufbaut...Wenn nicht, wie sieht denn eine DIV-Operation in c aus, wie es sie auch in Pascal gibt? DIV bedeutet doch Division ohne Rest, d.h. 13 div 2 = 6. durch mod erhält man dann 13 mod 2 = 1 => folglich muss man mit 5 weitermachen: 5 div 2 = 2, 5 mod 2 = 1, dann mit 2: 2/2 = 1, 2 mod 2 = 0; mit 1 dann: 1:2 = 0, 1 mod 2 = 1

=> man hat die zahl 1101 raus. Klar, die Länge kriegt man über's mitzählen in der "Div und mod"- schleife oder so. Toll. Jetzt bin ich eventuell schon nahe an der Lösung des Problems dran. Keine Ahnung. Wie ist das mit DIV in C? Gibt's da neinen Operanden? Oder hat C wenn's geht noch so'n cooles Feature, das es bei 13 / 2 auf 6 abrundet, wenn 13 und 2 jeweilst integer sind *gg (Würde zumindest logisch sein nach der Bitverschiebung nach rechts, oder **Fragezeichen... Lol is die Bitverschiebung nicht div..? Scheiße, ich brauch noch n Kaffe)
 
Original von PeasantKing
brauch unbedingt die Stellenzahl von einer Zahl als binär, also z.B. 4 bei 13 :)
Zum Vergrößern anklicken....
nochmal kurz ne anmerkung falls du es nicht bemerkt hast
die funktion die ich oben gepostet habe (binSizeOfInt) gibt diese binärstellenanzahl der integer zahl wieder
macht also genau das was du wolltest
 
@ivegotmail: nicht ganz, denn ich benötige für meine funktion zum modularen potenzieren jedes einzelne bit. denn ich möchte eine Fallunterscheidung reinbaun, die z.B. die eine Anweisung ausführt, wenn bit3 gesetzt oder die andere wenn nicht. Die Stellenzahl ist dank der letzten Überlegung sogar überflüssig geworden, leider :)
Trotzdem auch dir nochmal danke (langsam ist die luft raus!!!)

@blueflash: Hmpf, hat sich bestätigt, 13/2 =6 und 13/3 = 4... er lässt die Kommastellen weg, entspricht also div...
 
afaik kannst du div in c verwenden, den operator müsste es geben! ansonsten:

int div(int n, int m) // n div m
{
int r = 0;

while (n - (m * r) > m)
r++;

return(r);

}
 
Wie heist's so schhön: Viele Wege führen nach Rom. Bei mir sind sie blos alle kreuz und quer im Kopf und ohne Ampeln und Schilder. Ich glaube ich sollte mal dem kleinen Männchen da oben drin bescheid sagen, das er eben diese aufstellen soll ;) . Die Lösung kriegt man mit ein wenig Logik auf dem mathematischen Wege gut hin. Den Rest werde ich dann wohl allein gebacken kriegen. Danke nochmals ( -.-' ) für eure Hilfe, und gn8!

EDIT:

Meine Lösung für das Problem (ich denke, das die soweit richtig ist, wenn nicht, werde ich morgen ketchup für'n besen kaufen):

Code: 
char mod_potenz(unsigned short m, int e, int n)
{
	short i,l;
	int c;
	
	c=m;
	
	for(i=1;i=length(n);i++) {
		m=(m*m)%n;
		if (getbit(i,n)) {
			m=(m*c)%n; }
		}
		
	return m;
}

short getbit(int i, int n)
{
	int v,w;
	
	for(v=20-i;v=1;v--) {
		w=n%2;
		n>>=1; }
	
	return w;		
}

short length(int n)
{
	int h,m=0;
	
	while(n!=0) {
		n>>=1;
		m++; }
	
	return m;
}
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben