從整數類型「修剪」右零

如何從不使用字符串的整數中快速移除尾隨零？從整數類型「修剪」右零

例如，1000必須成爲1,6789000必須成爲6789。

簡單的解決方案是通過10^max_exponent多次服用分裂的模，...，10000，1000，100，10（或以相反的順序）等，並將其與0。

但有人能做得更快嗎？

2016-04-15 vladon

預做一個表映射除去了尾隨零的所有數字的值。所以'table [1000] => 1'，'table [1001] => 1001'，'table [1010] => 101'，'table [6789000] => 6789'，'table [6789001] => 6789001' 。對於任何數字N，只需將第N個條目返回表格外。非常快。 – HostileFork

@HostileFork如果max_number的類型爲int64_t，即〜9 * 10^18，該怎麼辦？ :) – vladon

@vladon - 公平，他的方式很快，這就是你要求的。 – Sean

本質上講，這是由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;

來源

2016-04-15 16:41:12 MBo

這個解決方案是否與問題中的解決方案相同，OP希望改進的解決方案？ –

@גלעדברקן他按順序使用全部十個權力，19個操作，但是足夠使Log2（19）= 5個操作 – MBo

是不是第二個N mod 10000冗餘？ – erickson

如果你把一些LOG10你能弄清楚有多少位了。使用這個信息，你可以開始你的分裂過程，以最小的十次冪，只是比你的號碼大。然後你可以消除你的一些模態測試和分區。你可以做一個循環來簡化代碼。

僞代碼：

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

來源

2016-04-15 18:14:42 Barry

從整數類型「修剪」右零

回答

相關問題