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