fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdint.h>
  5.  
  6. static const int MultiplyDeBruijnBitPosition[32] = {
  7.     0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8.     8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  9. };
  10.  
  11. static const uint32_t PowersOf10[] = {
  12.     1, 10, 100, 1000, 10000, 100000,
  13.     1000000, 10000000, 100000000, 1000000000
  14. };
  15.  
  16. static const uint32_t MaxWithDigits[] = {
  17.     0, 9, 99, 999, 9999, 99999,
  18.     999999, 9999999, 99999999, 999999999
  19. };
  20.  
  21. static const uint32_t MinWithDigits[] = {
  22.     0, 0, 10, 100, 1000, 10000,
  23.     100000, 1000000, 10000000, 100000000
  24. };
  25.  
  26. typedef struct _stringlist {
  27.     char *v;
  28.     struct _stringlist *next;
  29. } stringlist;
  30.  
  31. inline int IntegerLogBase2(uint32_t v) {
  32.     v |= v >> 1;
  33.     v |= v >> 2;
  34.     v |= v >> 4;
  35.     v |= v >> 8;
  36.     v |= v >> 16;
  37.     return MultiplyDeBruijnBitPosition[(uint32_t) (v * 0x07C4ACDDU) >> 27];
  38. }
  39.  
  40. inline int IntegerLogBase10(uint32_t v) {
  41.     int t;
  42.     t = (IntegerLogBase2(v) + 1) * 1233 >> 12;
  43.     return t - (v < PowersOf10[t]);
  44. }
  45.  
  46. inline int IntegerDigitsBase10(uint32_t v) {
  47.     return (v == 0) ? 1 : IntegerLogBase10(v) + 1;
  48. }
  49.  
  50. inline int Itoa(uint32_t v, char *b) {
  51.     int i, l;
  52.     i = l = IntegerDigitsBase10(v);
  53.     b[i] = 0;
  54.     do {
  55.         i--;
  56.         b[i] = v % 10 + '0';
  57.         v /= 10;
  58.     } while (i != 0);
  59.     return l;
  60. }
  61.  
  62. inline int range_digits(uint32_t start, uint32_t end) {
  63.     int s = IntegerDigitsBase10(start);
  64.     int e = IntegerDigitsBase10(end);
  65.     int count = 0;
  66.     if (s == e) {
  67.         count += (end - start + 1) * s;
  68.     } else {
  69.         count += (MaxWithDigits[s] - start + 1) * s;
  70.         count += (end - MinWithDigits[e] + 1) * e;
  71.         s++;
  72.         while (s != e) {
  73.             count += (MaxWithDigits[s] - MinWithDigits[s] + 1) * s;
  74.             s++;
  75.         }
  76.     }
  77.     return count;
  78. }
  79.  
  80. stringlist *range_to_stringlist(uint32_t start, uint32_t end) {
  81.     size_t count = end - start + 1;
  82.     stringlist *all = malloc(sizeof(stringlist) * count);
  83.     char *chrbuf = malloc(range_digits(start, end) + count);
  84.     uint32_t i;
  85.     for (i = 0; start + i <= end; i++) {
  86.         all[i].v = chrbuf;
  87.         all[i].next = all + i + 1;
  88.         chrbuf += Itoa(start + i, chrbuf) + 1;
  89.     }
  90.     all[i - 1].next = 0;
  91.     return all;
  92. }
  93.  
  94. size_t stringlist_strlen(stringlist *s) {
  95.     size_t l = 0;
  96.     while (s != NULL) {
  97.         l += strlen(s->v);
  98.         s = s->next;
  99.     }
  100.     return l;
  101. }
  102.  
  103. void stringlist_to_str(stringlist *s, char *b) {
  104. 	size_t l;
  105.     while (s != NULL) {
  106.     	l = strlen(s->v);
  107.         memcpy(b, s->v, l);
  108.         b += l;
  109.         s = s->next;
  110.     }
  111.     *b = 0;
  112. }
  113.  
  114. int main() {
  115.     stringlist *s;
  116.     s = range_to_stringlist(0, 4999999);
  117.     char *c = malloc(stringlist_strlen(s) + 1);
  118.     stringlist_to_str(s, c);
  119.     printf("%d", strlen(c));
  120.     return 0;
  121. }
  122.  
Success #stdin #stdout 0.47s 112448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
33888890
https://ideone.com/3XxKa5
language:
C (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!