004
05.07.2004, 12:25 Uhr
ao
(Operator)
|
Am performantesten sind bei sowas im allgemeinen Tabellen-Lösungen. Ich hab hier einen Vorschlag; wer mag, kann ja mal den Performance-Vergleich mit Windalfs Lösung machen.
| C++: |
#include <stdio.h>
typedef struct _stLog2LookupEntry
{
unsigned int m_nNumber;
unsigned int m_nLog2;
} stLog2LookupEntry;
stLog2LookupEntry g_l2leLookupTable [] =
{
{ 1, 0 }
, { 2, 1 }
, { 4, 2 }
, { 8, 3 }
, { 16, 4 }
, { 32, 5 }
, { 64, 6 }
, { 128, 7 }
, { 256, 8 }
, { 512, 9 }
, { 1024, 10 }
, { 2048, 11 }
, { 4096, 12 }
, { 8192, 13 }
, { 16384, 14 }
, { 32768, 15 }
, { 65536, 16 }
, { 0, 32 }
};
unsigned int log2 (unsigned int x)
{
stLog2LookupEntry * pEntry = g_l2leLookupTable;
/* Durchsuche die Tabelle von oben nach unten,
bis du in der linken Spalte
auf einen Eintrag triffst, der größer oder gleich
deiner Zahl x ist. Der Eintrag in der rechten Spalte
ist der gesuchte Zweier-Logarithmus.
Die zweite Bedingung (m_nNumber > 0) testet auf das
Tabellen-Ende. */
while ((pEntry->m_nNumber < x) && (pEntry->m_nNumber > 0))
{
pEntry++;
}
return pEntry->m_nLog2;
}
int main (void)
{
unsigned int nNumber = 1;
unsigned int nLog2;
while (nNumber > 0)
{
scanf ("%d", &nNumber);
nLog2 = log2 (nNumber);
printf (" log2(%d) = %d\n", nNumber, nLog2);
}
return 0;
}
|
Das Beispiel geht in C und in C++.
Ich war zu faul, die ganzen Zweierpotenzen bis 2^31 einzutippen, drum hab ich bei 2^16 aufgehört.
Die main-Funktion holt einen Wert von der Tastatur ab, berechnet den Logarithmus und gibt beides aus (ohne irgendwelche Prüfungen, also mit Sorgfalt benutzen!). Bei Eingabe von 0 wird das Programm beendet.
Performance-testen sollte man natürlich nur den Aufruf von log2().
ao
Dieser Post wurde am 05.07.2004 um 12:26 Uhr von ao editiert. |
.
