Autor |
Beitrag |
whiskey (whiskey)
Junior Mitglied Benutzername: whiskey
Nummer des Beitrags: 6 Registriert: 04-2002
| Veröffentlicht am Sonntag, den 02. Juni, 2002 - 00:48: |
|
hallo, ich möchte etwas programmieren und suche eine möglichkeit eine beliebige integer zahl darauf zu testen, ob sie der menge {2,4,8,16,32,64,...} also 2^n angehört. die möglichkeit einer while-schleife bei der einfach sooft durch 2 geteilt wird, bis eine 1 rauskommt oder eben nicht, schließe ich mal aus, weil das etwas unökonomisch ist bei großen zahlen. vielen dank whiskey |
Robert (emperor2002)
Mitglied Benutzername: emperor2002
Nummer des Beitrags: 38 Registriert: 04-2002
| Veröffentlicht am Sonntag, den 02. Juni, 2002 - 02:01: |
|
mmmh! Probier doch mal folgendes aus: Schau einfach ob 2log(Integer) ganzzahlig wird, oder einen Nachkommateil hat! MFG Robert Robert Klinzmann Schüler des EHGs mailto: Emperor2002@Web.de
|
murray (murray)
Fortgeschrittenes Mitglied Benutzername: murray
Nummer des Beitrags: 65 Registriert: 10-2001
| Veröffentlicht am Sonntag, den 02. Juni, 2002 - 09:22: |
|
Hallo, Robert, leider hat man selten einen Logarithmus zur Basis 2 in den Programmiersprachen, hier hilft der Trick log(x)/log(2), zudem ist dieser auch noch für Gleitpunktzahlen. Was man also machen muß ist seine Zahl in eine Gleitpunktzahl umwandeln (z.B. double) ... ich skiziere das mal in SourceCode: double test = log((double)zahl)/log(2); Dann muß man noch Testen ob es einen Rest gab oder nicht. Eine Idee dabei ist, die test-Zahl in einen integer zurückzuverwandeln (dabei werden Nachkommastellen abgeschnitten), dann wieder in einen double und das ergebnis mit dem original vergleichen. int testint = (integer) test; if (((double)testint) == test) ... dann ist alles in Butter Murray |
murray (murray)
Fortgeschrittenes Mitglied Benutzername: murray
Nummer des Beitrags: 66 Registriert: 10-2001
| Veröffentlicht am Sonntag, den 02. Juni, 2002 - 10:40: |
|
Hallo, es geht auch rein auf IntegerBasis, dazu muß man sich die Zahl binär vorstellen. Nochmal kurz zur Erinnerung 4 == 100 = 1*2^2 + 0*2^1 + 0*2^0. Zur Darstellung des Problems benutze ich mal eine 8-bit große Zahl (also 0 <= x <= 255), da man das Prinzip ohne Weiteres auf größere Zahlen übertragen kann (ich nehme mal an du benutzt 32-bit Integer). Angenommen ich wollte testen ob die 34 eine solche Zahl ist: 34 == 00100010 (2^8) 1. ist 34 <, > oder = 2^4 (16) ? - sie ist größer, ihre größte Potenz liegt also in den obenen 4 bit 2. ist 34 <, > oder = 2^(4+2) (64) ? - sie ist kleiner, ihre größte Potenz liegt also im 1. der obenen 4 bit 3. ist 34 <, > oder = 2^(4+2-1) (32) ? - sie ist größer - da ich aber nun im Letzten Schritt bin, ist die Zahl keine Potenz von 2 Deutlich wird das Verfahren, wenn man das mal binär aufschreibt: 0001 0010 - 1. Schritt - das größte Bit ist in der oberen Hälfte (erste Vierergruppe) 00 01 00 10 - 2. Schritt - das größte Bit ist in der zweiten Zweiergruppe (die untere Häfte der ersten Vierergruppe) Hier hast Du die Lösung nach 3 Schritten, bei 32 bit hast Du die Lösung nach 5 Schritten. Murray PS: Bei Bedarf erläutere ich das näher. PPS: Ich hatte mal von einem Verfahren gelesen, das rein mit logischen Operationen (and, or u.s.w.) zum Ziel kam, aber leider weis ich das nicht mehr.
|
whiskey (whiskey)
Junior Mitglied Benutzername: whiskey
Nummer des Beitrags: 8 Registriert: 04-2002
| Veröffentlicht am Sonntag, den 02. Juni, 2002 - 11:09: |
|
cool, vielen dank!! |
whiskey (whiskey)
Junior Mitglied Benutzername: whiskey
Nummer des Beitrags: 9 Registriert: 04-2002
| Veröffentlicht am Sonntag, den 02. Juni, 2002 - 11:14: |
|
also ich hab das jetzt mal folgendermaßen umgesetzt, das mit dem double- und integer umgewandle is nich so schön, daher: $test=($zahl==1||($zahl==(pow(2,(ceil(log($zahl)/log(2)))))))?1:0; $test enthält dann 1 oder 0 je nach $zahl (>0). dass mit dem binärverfahren klingt auch interessant. man könnte die zahl in einen binär-string umwandeln und darauf abfragen ob mehr als eine 1 enthalten ist. |
Schlaumeierchen
Unregistrierter Gast
| Veröffentlicht am Mittwoch, den 12. Juni, 2002 - 23:02: |
|
Hi, warum nicht einfach die logische Bitverknüpfung des "Exlusiven Oders" benutzen? XOR vergleicht einfach alle Bits und als Ergebnis werden die Bits gesetzt die ungleich sind. Also z.B. als Pascal-Code: If ((zahl XOR (zahl-1)) = 2*zahl-1) { ...Diese Zahl ist eine 2er-Potenz... } |
Schlaumeierchen
Unregistrierter Gast
| Veröffentlicht am Mittwoch, den 12. Juni, 2002 - 23:06: |
|
Andere Möglichkeiten: - logisches Und: If ((zahl AND (zahl-1)) = (zahl-1)) { ... } - logisches Oder: If ((zahl OR (zahl+1)) = (zahl+1)) { ... } |
murray (murray)
Fortgeschrittenes Mitglied Benutzername: murray
Nummer des Beitrags: 72 Registriert: 10-2001
| Veröffentlicht am Donnerstag, den 13. Juni, 2002 - 08:41: |
|
Hallo, das mit dem AND geht nicht, Gegenbeispiel: 5 AND 4 = 4 ... 5 ist nicht Vielfaches von 2 Aber das mit dem OR und XOR klingt interessant. Murray |
Schlaumeierchen
Unregistrierter Gast
| Veröffentlicht am Donnerstag, den 13. Juni, 2002 - 17:24: |
|
Deshalb steht bei AND auch +1 und nicht -1 |
murray (murray)
Fortgeschrittenes Mitglied Benutzername: murray
Nummer des Beitrags: 76 Registriert: 10-2001
| Veröffentlicht am Freitag, den 14. Juni, 2002 - 12:13: |
|
So richtig lesen kannst du nicht, oder? Zitat (kopiert aus Deinem Text): - logisches Und: If ((zahl AND (zahl-1)) = (zahl-1)) { ... } Und selbst wenn es hieße: - logisches Und: If ((zahl AND (zahl+1)) = (zahl+1)) { ... } Gegenbeispiel: 8 AND 9 = 8 ... 8 ist aber 2³ auch (zahl AND (zahl+1)) = zahl geht nicht 6 AND 7 = 6 ... 6 ist nicht 2^x Hey, aber das mit dem ODER ist genial und simpel. Murray (Beitrag nachträglich am 14., Juni. 2002 von murray editiert) |
Schlaumeierchen
Unregistrierter Gast
| Veröffentlicht am Freitag, den 14. Juni, 2002 - 13:53: |
|
Ja so wie mein erster Beitrag wars schon richtig, nur dass meine Logik nachgelassen hat beim AND *g* Also beim ODER +1 ist richtig und beim AND geht es folgendermassen! If ((zahl AND (zahl-1)) = 0) {}
|
Blondie
Unregistrierter Gast
| Veröffentlicht am Freitag, den 14. Juni, 2002 - 14:23: |
|
Hi, also mit If ((zahl OR (zahl+1)) = (zahl+1)) { ... } kannst du nur feststellen ob es eine gerade zahl ist, mehr nicht!
|
murray (murray)
Fortgeschrittenes Mitglied Benutzername: murray
Nummer des Beitrags: 77 Registriert: 10-2001
| Veröffentlicht am Freitag, den 14. Juni, 2002 - 14:24: |
|
Oha, mit dieser Aufabe haben wir ein schönes Bespiel für die unterschiedlichen Denkweisen eines: 1. Mathematikers - log() 2. Informatikers - Suche mit logarithmischem Aufwand 3. erfahrenen Programmiers: zahl AND (zahl-1) = 0 Ich finde letztere Lösung wirklich genial, weil ich eigentlich hätte selbst drauf kommen müssen, aber das beweist mir wieder mal das ich eben doch mehr Theroretiker bin ;-) Murray |