0

如何以高效快捷的方式为号码添加前缀并删除？（数字可以有任意位数，数字没有限制）我有数字，例如 122121，我想在开头添加数字 9 为 9122121，之后我需要删除数字中的第一个数字。我已拆分为向量，推前数字（在本例中为 9）和从数字创建数字（迭代乘以 10）。有没有更有效的方法？

4

6 回答 6

3

如果您想要效率，请不要使用除数字、向量、字符串等之外的任何其他内容。在您的情况下：

#include <iostream>

unsigned long long add_prefix( unsigned long long number, unsigned prefix )
{
    // if you want the example marked (X) below to print "9", add this line:
    if( number == 0 ) return prefix;

    // without the above, the result of (X) would be "90"

    unsigned long long tmp = ( number >= 100000 ) ? 1000000 : 10;
    while( number >= tmp ) tmp *= 10;
    return number + prefix * tmp;
}

int main()
{
    std::cout << add_prefix( 122121, 9 ) << std::endl; // prints 9122121
    std::cout << add_prefix( 122121, 987 ) << std::endl; // prints 987122121
    std::cout << add_prefix( 1, 9 ) << std::endl; // prints 91
    std::cout << add_prefix( 0, 9 ) << std::endl; // (X) prints 9 or 90
}

但要注意溢出。如果没有溢出，上述内容甚至适用于多位前缀。我希望你能找出反向算法来删除前缀。

已编辑：正如 Andy Prowl 指出的那样，可以将 0 解释为“无数字”，因此前缀不应后跟数字 0。但我想这取决于 OPs 用例，因此我相应地编辑了代码。

于 2013-03-28T20:25:23.123 回答
2

您可以使用 floor(log10(number)) + 1 计算位数。因此代码如下所示：

int number = 122121;
int noDigits = floor(log10(number)) + 1;
//Add 9 in front
number += 9*pow(10,noDigits);
//Now strip the 9
number %= pow(10,noDigits);

我希望我做对了一切；）

于 2013-03-28T20:24:22.797 回答
2

我将提供一个使用二分搜索的答案和迄今为止提供的答案的一个小基准。

二进制搜索

以下函数使用二进制搜索来查找所需数字的位数并将所需数字附加到其前面。

int addPrefix(int N, int digit) {
    int multiplier = 0;
    // [1, 5]
    if(N <= 100000) {
        // [1, 3]
        if(N <= 1000) {
            //[1, 2]
            if(N <= 100) {
                //[1, 1]
                if(N <= 10) {
                    multiplier = 10;
                //[2, 2]
                } else {
                    multiplier = 100;
                }
            //[3, 3]
            } else {
                multiplier = 1000;
            }
        //[4, 4]
        } else if(N <= 10000) {
            multiplier = 10000;
        //[5, 5]
        } else {
            multiplier = 100000;
        }
    //[6, 7]
    } else if(N <= 10000000) {
        //[6, 6]
        if(N <= 1000000) {
            multiplier = 1000000;
        //[7, 7]
        } else {
            multiplier = 10000000;
        }
    //[8, 9]
    } else {
        //[8, 8]
        if(N <= 100000000) {
            multiplier = 100000000;
        //[9, 9]
        } else {
            multiplier = 1000000000;
        }
    }
    return N + digit * multiplier;
}

它比较冗长。int但是，它会在最多 4 次比较的范围内找到数字的位数。

基准

我创建了一个小型基准测试，针对 4.5 亿次迭代运行每个提供的算法，每个确定的位数进行 5000 万次迭代。

int main(void) {
    int i, j, N = 2, k;
    for(i = 1; i < 9; ++i, N *= 10) {
        for(j = 1; j < 50000000; ++j) {
            k = addPrefix(N, 9);
        }
    }
    return 0;
}

结果：

+-----+-----------+-------------+----------+---------+
| run | Alexander | Daniel Frey | kkuryllo | W.B.    |
+-----+-----------+-------------+----------+---------+
| 1st |    2.204s |      3.983s |   5.145s | 23.216s |
+-----+-----------+-------------+----------+---------+
| 2nd |    2.189s |      4.044s |   5.081s | 23.484s |
+-----+-----------+-------------+----------+---------+
| 3rd |    2.197s |      4.232s |   5.043s | 23.378s |
+-----+-----------+-------------+----------+---------+
| AVG |    2.197s |      4.086s |   5.090s | 23.359s |
+-----+-----------+-------------+----------+---------+

您可以在此处找到本要点中使用的来源。

于 2013-03-28T22:03:40.150 回答
1

使用 boost 中的词法转换怎么样？这样你就不用自己做迭代了。

http://www.boost.org/doc/libs/1_53_0/doc/html/boost_lexical_cast.html

于 2013-03-28T20:20:39.887 回答
1

%首先找到比你的数字大 10 的最大幂。然后乘以那个加法并添加到您的号码

例如：

int x;
int addition;
int y = 1;
while (y <= x)
{
    y *= 10;
}

x += addition * y;

我没有测试此代码，因此仅作为示例...我也不太了解您的其他说明，您需要澄清一下。

编辑好吧我想我明白你也想在某个时候删除第一个数字。您可以使用类似的方法来执行此操作。

int x;
int y = 1;
while (y <= x*10)
{
    y *= 10;
}

x %= y;
于 2013-03-28T20:27:52.547 回答
1

您可以将数字放在 std::string 中并使用 insert 和 delete 但这可能有点矫枉过正

于 2013-03-28T20:29:32.893 回答