Wie kann man nachfolgende Nullen aus einer Ganzzahl, die keine Zeichenketten verwendet, schnell entfernen?"Trimmen" rechte Nullen vom ganzzahligen Typ
Zum Beispiel muss 10001 werden, 6789000 muss 6789 werden.
Einfache Lösung wiederholt wird Modulo-Division durch 10^max_exponent nehmen, ..., 10000, 1000, 100, 10 (oder in umgekehrter Reihenfolge), und so weiter und es 0 zu vergleichen.
Aber kann es jemand schneller machen?
Im Wesentlichen ist diese binäre Suche durch Leistung von 10:
if N mod 100000000 = 0
N = N div 100000000;
if N mod 10000 = 0
N = N div 10000;
if N mod 10000 = 0
N = N div 10000;
if N mod 100 = 0
N = N div 100;
if N mod 10 = 0
N = N div 10;
Ist diese Lösung nicht die gleiche wie die in der Frage, die Lösung, die das OP zu verbessern hofft? –
@ גגעד בבקן Er verwendet alle zehn Mächte der Reihe nach, 19 Operationen, aber es gibt genug, um Log2 (19) = 5 Operationen zu machen – MBo
Ist die 'zweite N mod 10000' nicht redundant? – erickson
Wenn Sie Log 10 der Zahl nehmen können Sie herausfinden, wie viele Stellen hat. Mit dieser Information können Sie Ihren Divisionsprozess mit der kleinsten Zehnerpotenz beginnen, die gerade größer ist als Ihre Zahl. Du kannst dann einige deiner Mod-Tests und Divisionen eliminieren. Sie könnten eine Schleife erstellen, um den Code zu vereinfachen.
Pseudocode:
digit_count = log10(num) + 1
pow = 10^digit_count
for (int i = 0; i < digit_count; i++) {
if (num mod pow == 0) {
num /= pow
}
pow /= 10
}
return num
Pre-Machen Sie eine Tabelle, die alle Zahlen auf ihre Werte mit den Hinter entfernt Nullen. Also 'Tabelle [1000] => 1',' Tabelle [1001] => 1001', 'Tabelle [1010] => 101',' Tabelle [6789000] => 6789', 'Tabelle [6789001] => 6789001' . Für jede Zahl N gebe einfach den N-ten Eintrag aus der Tabelle zurück. Sehr schnell. – HostileFork
@HostileFork was ist, wenn max_number vom Typ int64_t ist, also ~ 9 * 10^18? :) – vladon
@vladon - um fair zu sein, sein Weg ist schnell, was Sie gefragt haben. – Sean