从整数类型“修剪”右零

如何从不使用字符串的整数中快速移除尾随零？从整数类型“修剪”右零

例如，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

从整数类型“修剪”右零

回答

相关问题