代码之家 › 专栏 › 技术社区 › Alex

有没有更好的方法来获得数字的位数?(C++)

c++

Alex · 技术社区 · 15 年前

我知道你可以用模和除法得到一个数的位数。以下是我过去的做法:(psuedocode,以便让学生阅读它。) 一些做作业):

int pointer getDigits(int number) 
    initialize int pointer to array of some size
    initialize int i to zero
    while number is greater than zero
       store result of number mod 10 in array at index i
       divide number by 10 and store result in number
       increment i
    return int pointer

不管怎样,我想知道是否有更好、更有效的方法来完成这项任务?如果没有,有吗任何此任务的替代方法,是否避免使用字符串?C型还是其他?

谢谢。我问是因为我想在我的个人项目中做这个,我想尽可能高效地做。

非常感谢您的帮助和/或洞察力。

7 回复 | 直到 13 年前

James McNellis 15 年前

提取数字所需的时间将与动态分配数组所需的时间相减。考虑在结构中返回结果:

struct extracted_digits
{
    int number_of_digits;
    char digits[12];
};

您需要为最大位数选择合适的值( 12 这里,这就足够一个32位整数了)。或者,您可以返回 std::array<char, 12> 并使用无效值对终端进行编码(因此,在最后一个值之后,存储一个 10 或者其他不是数字的东西)。

根据是否要处理负值,还必须决定如何报告一元减号( - )

cdhowie 15 年前

除非你想用2的幂的基数表示数字,否则这是唯一的方法。

Tony Delroy 15 年前

有点过早的优化。如果分析证明它是重要的,那么请确保将你的ALGO与ITOA进行比较。在内部,它可以使用一些CPU指令,这些指令没有从C++中显式访问,并且编译器的优化器可能不太聪明地使用(例如,AAM,它在保存mod结果时进行div)。自己对汇编程序进行实验(和基准测试)。您可能会四处寻找ITOA的组装实现(这与您所要求的不完全相同,但可能会建议使用最佳的CPU指令)。

paxdiablo 15 年前

通过“避免使用字符串”,我假设您这样做是因为如果您想要一个整数值,那么只使用字符串表示的效率非常低。

为此,我建议采取一种稍微非正统的方法可以要合适。不要以一种形式存储它们,将它们存储在 二者都 . 下面的代码是C-它将工作在C++中,但是你可能想考虑使用C++等价物——但是它背后的思想并没有改变。

通过“存储这两个表单”,我的意思是您可以具有如下结构:

typedef struct {
    int ival;
    char sval[sizeof("-2147483648")]; // enough for 32-bits
    int dirtyS;
} tIntStr;

并传递此结构(或其地址),而不是整数本身。

通过使用宏或内联函数,如:

inline void intstrSetI (tIntStr *is, int ival) {
    is->ival = i;
    is->dirtyS = 1;
}
inline char *intstrGetS (tIntStr *is) {
    if (is->dirtyS) {
        sprintf (is->sval, "%d", is->ival);
        is->dirtyS = 0;
    }
    return is->sval;
}

然后,要设置该值,您将使用:

tIntStr is;
intstrSetI (&is, 42);

当你想要字符串表示的时候:

printf ("%s\n" intstrGetS(&is));
fprintf (logFile, "%s\n" intstrGetS(&is));

这有一个优点,即只在需要时计算字符串表示形式(即 fprintf 上面不必重新计算字符串表示形式和 printf 只有当它脏的时候)。

这与我在SQL中使用预计算列和触发器时使用的技巧类似。这里的想法是,您只在需要时执行计算。因此,一个额外的列来保存索引的低位姓氏以及一个用于计算它的插入/更新触发器,通常比 select lower(non_lowercased_last_name) . 这是因为它将计算成本(在写入时完成)分摊到所有读取中。

从这个意义上说,如果您的代码配置文件是 set-int/use-string/set-int/use-string... . 但是,如果是的话 set-int/use-string/use-string/use-string/use-string... ,您将获得性能提升。

当然,这是有代价的,只需要最少的额外存储空间,但大多数性能问题归结为空间/时间的权衡。

如果你 真的? 为了避免字符串,您仍然可以使用相同的方法(仅在需要时才计算),只是计算(和结构)会有所不同。

作为旁白: 您很可能希望使用库函数来完成这项工作,而不是手工编写自己的代码。库函数通常会进行大量的优化,可能比编译器从代码中获得的优化还要多(当然,这并不能保证)。

也可能是 itoa 如果你有,可能会跑赢 sprintf("%d") 同时,考虑到其有限的用例。不过,你应该, 测量,而不是猜测! 不仅是在库函数方面,还包括整个解决方案(以及其他解决方案)。

MSalters 15 年前

使用“数字”也可以看到一个Base-100解决方案也可以工作,这是非常简单的。 00 - 99 . 在每一次迭代中,您将 %100 产生这样一个数字对,从而使步数减半。权衡的是,您的数字表现在是200字节而不是10字节。不过,它很容易放在一级缓存中(很明显,这只适用于转换大量数字的情况,但无论如何效率都不高)。另外,您可能会以前导零结束,如“0128”。

facetus 15 年前

是的,有一种更有效的方法,但不是便携式的。英特尔的FPU有一个特殊的BCD格式数字。所以,您所要做的只是调用相应的汇编程序指令,将ST(0)转换为BCD格式并将结果存储在内存中。指令名称为 FBSTP 。

Emilio Garavaglia 13 年前

从数学上讲,整数的小数位数是 1+int(log10(abs(a)+1))+(a<0); 。

您将不使用字符串,而是遍历浮点和日志函数。如果你的平台有任何类型的FP加速器(每台PC或类似的PC都有),那就不会有什么大不了的,并且会击败任何“基于sting的”算法(这不仅仅是一个迭代除以10和count)。