Was ist der schnellste Weg, um die höchste Dezimalstelle einer ganzen Zahl zu erhalten?

Question

Was ist der schnellste Weg,

template <typename T> 
unsigned highest_decimal_digit(T x); 

(die beispielsweise 3 für 356431, 7 für 71 und 9 für 9 zurückkehrt) zu implementieren?

Das Beste, was ich denken kann ist:

• constexpr-Berechnung die „mittlere Größe“ Leistung von 10, die in T. paßt
• eine binäre Suche durchführt (über die Befugnisse von 10, möglicherweise Verwenden einer consExpr-konstruierten Nachschlagetabelle, um p zu finden, die höchste Potenz von 10 niedriger als x.
• return x von p
geteilt

... aber vielleicht gibt es einen anderen Ansatz.

Hinweise:

• drückte ich die Frage und meinen Ansatz in C++ 14ish Bedingungen, und eine Lösung im Code wäre schön, aber eine abstrakte Lösung (oder sogar eine Lösung in x86_64 Montage) wäre in Ordnung. Ich möchte jedoch etwas, das für alle (unsigned) Integer-Typen funktioniert.
• Sie können signierte Integraltypen ignorieren.
• Ich habe nicht angegeben, was "schnell" ist, aber bitte Hardware-bewusst sein.

Answer 1

Optionen, die mir vorkommen;

Brute Kraft: halten Sie die ganze Zahl durch 10, bis Sie Null erhalten; das sagt Ihnen, welche Reihenfolge der Nummer Sie betrachten (zB 860 dauert 3 Schichten (86, 8, 0) also ist es ein 10^3) dann Rückkehr n/(10^Reihenfolge)

binäre Suche: wie Sie sagen, suchen Sie über 10er-Potenzen, aber es erfordert zusätzliche Variablen und Zuordnungen und die Sorge wäre, zahlt sich diese zusätzliche Tracking-Info für sich auf die Arten von Zahlen, die Sie interessieren? Zum Beispiel, wenn die meisten Ihrer Zahlen klein sind, kann Brute-Force einfach schneller sein.

Bitshift-Optimierung: zählen, wie oft Sie x >> 1 tun müssen, bis Sie zu Null kommen; Dies legt den Bereich für Ihre Suche fest. Zum Beispiel, 94 braucht 7 Schichten, um die Nummer zu löschen. Daher ist es < 128. Daher starten Brute-Force-Suche bei 10^3. Sie benötigen eine Suche nach Bits => Reihenfolge.

Answer 2

Neuere x86-Chips unterstützen eine lzcnt-Anweisung, die Ihnen die Anzahl der freien Bits am Anfang einer Ganzzahl angibt. Sie können es eingebaute Compiler Funktionen zuzugreifen unter Verwendung von wie die folgenden (aus GCC):

unsigned short __builtin_ia32_lzcnt_16(unsigned short); 
unsigned int __builtin_ia32_lzcnt_u32(unsigned int); 
unsigned long long __builtin_ia32_lzcnt_u64 (unsigned long long); 

Sie dies mit jeder Ziffer beginnen, die untere und obere Grenze der ganzen Zahlen mit einer Verweistabelle von 640 Werten kombinieren könnten angeben, von 0-9, die mit der entsprechenden Anzahl von freien Bits beginnen. Tatsächlich könnten Sie Platz sparen, indem Sie den lzcnt Wert um 3 Stellen nach rechts verschieben; die Übereinstimmung mit den ersten Dezimalziffern ist immer noch eindeutig.

Answer 3

Mit einer lzcnt Anweisung können Sie eine Tabelle von Divisoren für jede Anzahl führender Null-Bits erstellen. Zum Beispiel für nicht signierte 64-Bit-Zahlen:

lz | range | div 
---+---------+---- 
64 | 0  | 1 
63 | 1  | 1 
62 | 2-3 | 1 
61 | 4-7 | 1 
60 | 8-15 | 1 
59 | 16-31 | 10 
58 | 32-63 | 10 
57 | 64-127 | 10 
56 | 128-255 | 100 
... 
0 | 9223372036854775808-18446744073709551615 | 1000000000000000000 

Dann wird die Berechnung:

leading_zero_bits = lzcnt(x); 
leading_digit = x/divisor_table[leading_zero_bits]; 
if (leading_digit >= 10) leading_digit = 1; 

Das Ergebnis der Division wird immer weniger als 20, so dass nur eine einfache Prüfung für Quotienten benötigt wird zwischen 10 und 19. Die Division durch eine Konstante kann ebenfalls optimiert werden.

Answer 4

Die beste Option scheint durch vorberechnete Leistung von 10. Also, in Pseudo-Code zu kombinieren CLZ Ansatz und dividieren zu sein:

powers10=[1,1,1,1,10,10,10,10,100,100...]; // contains powers of 10 map to CLZ values 
int firstDigit(unsigned INT_TYPE a) { 
    if (a<10) return a; // one digit, screw it 
    int j=typesize(a)-clz(a); 
    if (j==3) return 1; // 10-16 hit this, return 1 
    int k=a/powers10[j]; 
    if (k>9) return 1; else return k; 
} 

typesize() Renditen 64 für long long, 32 für int und 16 für short int.