快速整型转字符实现

eric2013

https://jk-jeon.github.io/posts/2022/02/jeaiii-algorithm/

一般都用sprintf，itoa或者手动计算：

1. char* itoa_naive(std::uint32_t n, char* buffer) {
   
2.   char temp[10];
   
3.   char* ptr = temp + sizeof(temp) - 1;
   
4.   while (n >= 10) {
   
5.     *ptr = char('0' + (n % 10));
   
6.     n /= 10;
   
7.     --ptr;
   
8.   }
   
9.   *ptr = char('0' + n);
   
10.   auto length = temp + sizeof(temp) - ptr;
    
11.   std::memcpy(buffer, ptr, length);
    
12.   return buffer + length;
    
13. }

复制代码

新实现：

1. #include <cstdint>
   
2. #include <cstring>
   
3. #include <type_traits>
   
4. 
   
5. static constexpr char radix_100_table[] = {
   
6.     '0', '0', '0', '1', '0', '2', '0', '3', '0', '4',
   
7.     '0', '5', '0', '6', '0', '7', '0', '8', '0', '9',
   
8.     '1', '0', '1', '1', '1', '2', '1', '3', '1', '4',
   
9.     '1', '5', '1', '6', '1', '7', '1', '8', '1', '9',
   
10.     '2', '0', '2', '1', '2', '2', '2', '3', '2', '4',
    
11.     '2', '5', '2', '6', '2', '7', '2', '8', '2', '9',
    
12.     '3', '0', '3', '1', '3', '2', '3', '3', '3', '4',
    
13.     '3', '5', '3', '6', '3', '7', '3', '8', '3', '9',
    
14.     '4', '0', '4', '1', '4', '2', '4', '3', '4', '4',
    
15.     '4', '5', '4', '6', '4', '7', '4', '8', '4', '9',
    
16.     '5', '0', '5', '1', '5', '2', '5', '3', '5', '4',
    
17.     '5', '5', '5', '6', '5', '7', '5', '8', '5', '9',
    
18.     '6', '0', '6', '1', '6', '2', '6', '3', '6', '4',
    
19.     '6', '5', '6', '6', '6', '7', '6', '8', '6', '9',
    
20.     '7', '0', '7', '1', '7', '2', '7', '3', '7', '4',
    
21.     '7', '5', '7', '6', '7', '7', '7', '8', '7', '9',
    
22.     '8', '0', '8', '1', '8', '2', '8', '3', '8', '4',
    
23.     '8', '5', '8', '6', '8', '7', '8', '8', '8', '9',
    
24.     '9', '0', '9', '1', '9', '2', '9', '3', '9', '4',
    
25.     '9', '5', '9', '6', '9', '7', '9', '8', '9', '9'
    
26. };
    
27. 
    
28. //      /\____________
    
29. //     /  \______     \______
    
30. //    /\   \     \     \     \
    
31. //   0  1  /\    /\    /\    /\
    
32. //        2  3  4  5  6  7  8  9
    
33. char* itoa_better_y(std::uint32_t n, char* buffer) {
    
34.   std::uint64_t prod;
    
35. 
    
36.   auto get_next_two_digits = [&]() {
    
37.     prod = std::uint32_t(prod) * std::uint64_t(100);
    
38.     return int(prod >> 32);
    
39.   };
    
40.   auto print_1 = [&](int digit) {
    
41.     buffer[0] = char(digit + '0');
    
42.     buffer += 1;
    
43.   };
    
44.   auto print_2 = [&] (int two_digits) {
    
45.     std::memcpy(buffer, radix_100_table + two_digits * 2, 2);
    
46.     buffer += 2;
    
47.   };
    
48.   auto print = [&](std::uint64_t magic_number, int extra_shift, auto remaining_count) {
    
49.     prod = n * magic_number;
    
50.     prod >>= extra_shift;
    
51.     auto two_digits = int(prod >> 32);
    
52. 
    
53.     if (two_digits < 10) {
    
54.       print_1(two_digits);
    
55.       for (int i = 0; i < remaining_count; ++i) {
    
56.         print_2(get_next_two_digits());
    
57.       }
    
58.     }
    
59.     else {
    
60.       print_2(two_digits);
    
61.       for (int i = 0; i < remaining_count; ++i) {
    
62.         print_2(get_next_two_digits());
    
63.       }
    
64.     }
    
65.   };
    
66. 
    
67.   if (n < 100) {
    
68.     if (n < 10) {
    
69.       // 1 digit.
    
70.       print_1(n);
    
71.     }
    
72.     else {
    
73.       // 2 digit.
    
74.       print_2(n);
    
75.     }
    
76.   }
    
77.   else {
    
78.     if (n < 100'0000) {
    
79.       if (n < 1'0000) {
    
80.         // 3 or 4 digits.
    
81.         // 42949673 = ceil(2^32 / 10^2)
    
82.         print(42949673, 0, std::integral_constant<int, 1>{});
    
83.       }
    
84.       else {
    
85.         // 5 or 6 digits.
    
86.         // 429497 = ceil(2^32 / 10^4)
    
87.         print(429497, 0, std::integral_constant<int, 2>{});
    
88.       }
    
89.     }
    
90.     else {
    
91.       if (n < 1'0000'0000) {
    
92.         // 7 or 8 digits.
    
93.         // 281474978 = ceil(2^48 / 10^6) + 1
    
94.         print(281474978, 16, std::integral_constant<int, 3>{});
    
95.       }
    
96.       else {
    
97.         if (n < 10'0000'0000) {
    
98.           // 9 digits.
    
99.           // 1441151882 = ceil(2^57 / 10^8) + 1
    
100.           prod = n * std::uint64_t(1441151882);
     
101.           prod >>= 25;
     
102.           print_1(int(prod >> 32));
     
103.           print_2(get_next_two_digits());
     
104.           print_2(get_next_two_digits());
     
105.           print_2(get_next_two_digits());
     
106.           print_2(get_next_two_digits());
     
107.         }
     
108.         else {
     
109.           // 10 digits.
     
110.           // 1441151881 = ceil(2^57 / 10^8)
     
111.           prod = n * std::uint64_t(1441151881);
     
112.           prod >>= 25;
     
113.           print_2(int(prod >> 32));
     
114.           print_2(get_next_two_digits());
     
115.           print_2(get_next_two_digits());
     
116.           print_2(get_next_two_digits());
     
117.           print_2(get_next_two_digits());
     
118.         }
     
119.       }
     
120.     }
     
121.   }
     
122.   return buffer;
     
123. }
     
124. 
     
125. #include <iostream>
     
126. 
     
127. int main() {
     
128.     char buffer[11];
     
129.     *itoa_better_y(1, buffer) = '\0';
     
130.     std::cout << buffer << "\n";
     
131.     *itoa_better_y(12, buffer) = '\0';
     
132.     std::cout << buffer << "\n";
     
133.     *itoa_better_y(123, buffer) = '\0';
     
134.     std::cout << buffer << "\n";
     
135.     *itoa_better_y(1234, buffer) = '\0';
     
136.     std::cout << buffer << "\n";
     
137.     *itoa_better_y(12345, buffer) = '\0';
     
138.     std::cout << buffer << "\n";
     
139.     *itoa_better_y(123456, buffer) = '\0';
     
140.     std::cout << buffer << "\n";
     
141.     *itoa_better_y(1234567, buffer) = '\0';
     
142.     std::cout << buffer << "\n";
     
143.     *itoa_better_y(12345678, buffer) = '\0';
     
144.     std::cout << buffer << "\n";
     
145.     *itoa_better_y(123456789, buffer) = '\0';
     
146.     std::cout << buffer << "\n";
     
147.     *itoa_better_y(1234567890, buffer) = '\0';
     
148.     std::cout << buffer << "\n";
     
149. }

复制代码

eric2013

jeaiii/itoa: Fast integer to ascii / integer to string conversion (github.com)