获取 base10 整数的位数

Question

std::to_string

不允许自定义分配器让我很烦，所以我正在编写自己的实现。为此，事先知道我需要为其分配字符串空间的位数是有益的。我可以通过多种方式做到这一点：

使用像演示的for循环：

int length = 1;
int x = 234567545;
while (x /= 10)
   length++;

使用以 10 为底的对数 + 1:

uint32_t x{234567};
double ds = std::log10(static_cast<double>(x)) + 1;
int digits = static_cast<int>(ds);

..也许其他解决方案。

这是我的代码：

演示

#include <concepts>
#include <cstdio>
#include <string>
#include <memory_resource>
#include <cinttypes>

using allocator_t = std::pmr::polymorphic_allocator<std::byte>;

template <std::integral T>
inline auto to_string(T number, allocator_t allocator = {}) -> std::pmr::string {
    // const std::size_t size = ???
    std::pmr::string str{ size, '\0', allocator };
    if constexpr(std::same_as<T, uint32_t>) {
        std::snprintf(&str.front(), size, "%" PRIu32, number);
    } else if constexpr (std::same_as<T, uint16_t>) {
        std::snprintf(&str.front(), size, "%" PRIu16, number);
    } else if constexpr (std::same_as<T, uint8_t>) {
        std::snprintf(&str.front(), size, "%" PRIu8, number);
    }
    // ...
    return str;
}

int main()
{
    uint32_t x = 256;
    printf("My number = %s\n", to_string(x).data());
}

问题是：对于这个用例，获取整数位数的最有效和最可靠的方法是什么？

Answer 1

我尝试了几个选项。计算以 10 为底的对数慢得离谱（30000 多个周期）。您发布的第一个简单循环（while (x /= 10)）很难被击败，但这里有一个选项，对于具有多个输入的输入来说似乎更快一些，而对于只有几个的输入，性能相似。它背后的想法是减法/比较应该比除法快得多。

static inline uint8_t uint32digits(const uint32_t input) {
  uint8_t length = 1;
  length += (input >= 1000000000);
  length += (input >= 100000000);
  length += (input >= 10000000);
  length += (input >= 1000000);
  length += (input >= 100000);
  length += (input >= 10000);
  length += (input >= 1000);
  length += (input >= 100);
  length += (input >= 10);
  return length;
}

我计算了机器周期，我知道这不是一个很好的基准测试方法，但它很简单并且不会落入测量过度优化代码的陷阱。对于单个数字，我得到 104 对 72 个周期，对于 5 位数字，我得到 96 对 176 个周期，对于 10 位数字，我得到 96 对 240 个周期。正如预期的那样，我的函数的成本完全独立于输入。

编辑： 其实这样好像还是快了点。。。

static inline uint8_t mynumdigits(const uint32_t input) {
  return 1 + (input >= 1000000000) + (input >= 100000000) + (input >= 10000000) + (input >= 1000000) + (input >= 100000) + (input >= 10000) + (input >= 1000) + (input >= 100) + (input >= 10);
}

Answer 2

经过一些修补，我想出了以下解决方案：

演示

#include <concepts>
#include <cstdio>
#include <string>
#include <memory_resource>
#include <limits>

using allocator_t = std::pmr::polymorphic_allocator<std::byte>;

template <std::integral T>
constexpr std::size_t get_max_digits()
{
    T val = std::numeric_limits<T>::max();
    std::size_t cnt=1;
    while (val /= 10) {
        ++cnt;
    }
    if constexpr (std::unsigned_integral<T>) {
        return cnt;
    } else {
        return cnt+1;
    }
}

template <typename T> struct PRI{};
template<> struct PRI<signed char> { static constexpr const char* value = "%hhd"; };
template<> struct PRI<unsigned char> { static constexpr const char* value = "%hhu"; };
template<> struct PRI<short> { static constexpr const char* value = "%hd"; };
template<> struct PRI<unsigned short> { static constexpr const char* value = "%hu"; };
template<> struct PRI<int> { static constexpr const char* value = "%d"; };
template<> struct PRI<unsigned int> { static constexpr const char* value = "%u"; };
template<> struct PRI<long> { static constexpr const char* value = "%ld"; };
template<> struct PRI<unsigned long> { static constexpr const char* value = "%lu"; };
template<> struct PRI<long long> { static constexpr const char* value = "%lld"; };
template<> struct PRI<unsigned long long> { static constexpr const char* value = "%llu"; };

template <typename T>
inline constexpr const char* PRI_v = PRI<T>::value;

template <std::integral T>
inline auto to_string(T number, allocator_t allocator = {}) -> std::pmr::string {
    constexpr std::size_t size = get_max_digits<T>();
    std::pmr::string str{ size, '\0', allocator };
    const std::size_t written_s = std::snprintf(&str.front(), size+1, PRI_v<T>, number);
    str.resize(written_s);
    return str;
}

int main()
{
    int x = -256325651;
    printf("Integer as string = %s\n", to_string(x).data());
}

输出：

Integer as string = -256325651

这适用于所有主要平台（在 x86、RISC-V 和 ARM 上测试）和所有常见的整数类型。我决定分配最大位数，然后缩小到实际使用的位数。这将只给我一个分配系统调用和一个对 snprintf 的调用，而 maxdigits 计算可以在编译时完成。它应该相当快。