接着上面的例子来，比如给定字符串”    10522545459″，除去空格有11位，而MAX_INT，即2147483647是10位数，当扫描到最后一个字符‘9’的时候，程序会比较 9 和 2147483647 - 1052254545*10的大小。

也就是说，对于字符串”10522545459″, 当扫描到最后一个字符‘9’时，根据上文第1小节的字符串转换成整数的思路：“每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字”，为了得到最终的整数，我们得如此计算：

1052254545*10 + 4，

然实际上当程序计算到1052254545*10时，

1052254545*10 >

2147483647

此时已经溢出了,若再执意计算，则程序逻辑将出错，故此后也就不能再判断字串的最后一位4是否大于2147483647%10了（耐不得烦想尽快看到最终正确代码的读者可以直接跳到下文第8节）。

但很遗憾的是，上述atoi标准代码依然返回的是long：

再者，下面这里定义成long的total与10相乘，即total*10很容易溢出：

1. simple_strtol，把一个字符串转换为一个有符号长整数；
2. simple_strtoll，把一个字符串转换为一个有符号长长整数；
3. simple_strtoul，把一个字符串转换为一个无符号长整数；
4. simple_strtoull，把一个字符串转换为一个无符号长长整数

然后，上面的strtol调下面的strtoul：

接着，上面的strtoul调下面的strtoull：

最后，strtoull调_parse_integer_fixup_radix和_parse_integer来处理相关逻辑：

重头戏来了。接下来，我们来看上面strtoull函数中的parse_integer_fixup_radix和_parse_integer两段代码。如鲨鱼所说

• “真正的处理逻辑主要是在_parse_integer里面，关于溢出的处理，_parse_integer处理的很优美，
• 而_parse_integer_fixup_radix是用来自动根据字符串判断进制的”。

1. 上头出现了个unlikely，其实unlikely和likely经常出现在linux相关内核源码中
   1. if(likely(value)){
   2.     //等价于if(likely(value)) == if(value)
   3. }
   4. else{
   5. }

   likely表示value为真的可能性更大，而unlikely表示value为假的可能性更大，这两个宏被定义成：

   1. //include/linux/compiler.h
   2. # ifndef likely
   3. #  define likely(x) (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 1))
   4. # endif
   5. # ifndef unlikely
   6. #  define unlikely(x)   (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 0))
   7. # endif
2. 呈现下div_u64的代码：
   1. //include/linux/math64.h
   2. //div_u64
   3. static inline u64 div_u64(u64 dividend, u32 divisor)
   4. {
   5.     u32 remainder;
   6.     return div_u64_rem(dividend, divisor, &remainder);
   7. }
   9. //div_u64_rem
   10. static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
   11. {
   12.     *remainder = dividend % divisor;
   13.     return dividend / divisor;
   14. }

2147483647 : 2147483647
2147483648 : -2147483648
10522545459 : 1932610867
-2147483648 : -2147483648
-2147483649 : -2147483647
-10522545459 : 1932610867

   8、根据我们第1小节达成一致的字符串转换成整数的思路：“每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字”，相信读者已经觉察到，在扫描到最后一个字符的时候，如果之前得到的数比较大，此时若再让其扩大10倍，相对来说是比较容易溢出的。

输入            输出
10522545459  : 2147483647
-10522545459 : -2147483648
2147483648   : 2147483647
-2147483648  : -2147483648

1. 00077 #include <compiler.h>
2. 00078 #include <stdlib.h>
3. 00079
4. 00084
5. 00092 int atoi(CONST char *str)
6. 00093 {
7. 00094     return ((int) strtol(str, (char **) NULL, 10));
8. 00095 }

1. #include <errno.h>
2. #include <stdio.h>
3. #include <ctype.h>
4. #include <limits.h>
6. #define CONST      const
8. long mstrtol(CONST char *nptr, char **endptr, int base)
9. {
10.     register CONST char *s;
11.     register long acc, cutoff;
12.     register int c;
13.     register int neg, any, cutlim;
15.     /*
16.      * Skip white space and pick up leading +/- sign if any.
17.      * If base is 0, allow 0x for hex and 0 for octal, else
18.      * assume decimal; if base is already 16, allow 0x.
19.      */
20.     s = nptr;
21.     do {
22.         c = (unsigned char) *s++;
23.     } while (isspace(c));
24.     if (c == ’-') {
25.         neg = 1;
26.         c = *s++;
27.     } else {
28.         neg = 0;
29.         if (c == ’+')
30.             c = *s++;
31.     }
32.     if ((base == 0 || base == 16) && c == ’0′ && (*s == ’x' || *s == ’X')) {
33.         c = s[1];
34.         s += 2;
35.         base = 16;
36.     }
37.     if (base == 0)
38.         base = c == ’0′ ? 8 : 10;
40.     /*
41.      * Compute the cutoff value between legal numbers and illegal
42.      * numbers.  That is the largest legal value, divided by the
43.      * base.  An input number that is greater than this value, if
44.      * followed by a legal input character, is too big.  One that
45.      * is equal to this value may be valid or not; the limit
46.      * between valid and invalid numbers is then based on the last
47.      * digit.  For instance, if the range for longs is
48.      * [-2147483648..2147483647] and the input base is 10,
49.      * cutoff will be set to 214748364 and cutlim to either
50.      * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated
51.      * a value > 214748364, or equal but the next digit is > 7 (or 8),
52.      * the number is too big, and we will return a range error.
53.      *
54.      * Set any if any `digits’ consumed; make it negative to indicate
55.      * overflow.
56.      */
57.     cutoff = neg ? LONG_MIN : LONG_MAX;
58.     cutlim = cutoff % base;
59.     cutoff /= base;
60.     if (neg) {
61.         if (cutlim > 0) {
62.             cutlim -= base;
63.             cutoff += 1;
64.         }
65.         cutlim = -cutlim;
66.     }
67.     for (acc = 0, any = 0;; c = (unsigned char) *s++) {
68.         if (isdigit(c))
69.             c -= ’0′;
70.         else if (isalpha(c))
71.             c -= isupper(c) ? ’A' - 10 : ’a' - 10;
72.         else
73.             break;
74.         if (c >= base)
75.             break;
76.         if (any < 0)
77.             continue;
78.         if (neg) {
79.             if ((acc < cutoff || acc == cutoff) && c > cutlim) {
80.                 any = -1;
81.                 acc = LONG_MIN;
82.                 errno = ERANGE;
83.             } else {
84.                 any = 1;
85.                 acc *= base;
86.                 acc -= c;
87.             }
88.         } else {
89.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {
90.                 any = -1;
91.                 acc = LONG_MAX;
92.                 errno = ERANGE;
93.             } else {
94.                 any = 1;
95.                 acc *= base;
96.                 acc += c;
97.             }
98.         }
99.     }
100.     if (endptr != 0)
101.         *endptr = (char *) (any ? s - 1 : nptr);
102.     return (acc);
103. }
105. int matoi2(CONST char *str)
106. {
107.     return ((int) mstrtol(str, (char **) NULL, 10));
108. }
110. int mgetline(char* buf, size_t n) {
111.   size_t idx = 0;
112.   int c;
114.   while (–n > 0 && (c = getchar()) != EOF && c != ’\n’) {
115.     buf[idx++] = c;
116.   }
117.   buf[idx] = ’\0′;
118.   return idx;
119. }
121. #define MAX_LINE 200
123. int main() {
124.     char buf[MAX_LINE];
125.     while (mgetline(buf, MAX_LINE) >= 0) {
126.         if (strcmp(buf, ”quit”) == 0) break;
127.         printf(“matoi2=%d\n”, matoi2(buf));
128.     }
129.     return 0;
130. }

1. if (neg) {
2.             if ((acc < cutoff || acc == cutoff) && c > cutlim) {
3.                 any = -1;
4.                 acc = LONG_MIN;
5.                 errno = ERANGE;
6.             } else {
7.                 any = 1;
8.                 acc *= base;
9.                 acc -= c;
10.             }
11.         } else {
12.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {
13.                 any = -1;
14.                 acc = LONG_MAX;
15.                 errno = ERANGE;

1. if ((acc > cutoff || acc == cutoff) && c > cutlim)

1. if ( acc > cutoff ||  (acc == cutoff) && c > cutlim)  )

1. if ((acc < cutoff || acc == cutoff) && c > cutlim) {

1. if (acc < cutoff || (acc == cutoff && c > cutlim)) {

1. 一种是诸如2147483650，即n > MAX/10 的；
2. 一种是诸如2147483649，即n == MAX/10 && c > MAX%10。”

1. if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))
2.         {
3.             n = MAX;
4.             break;
5.         }
6.         else if (sign < 0 && (n > (unsigned)MIN/10
7.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))
8.         {
9.             n = MIN;
10.             break;
11.         }

1. //copyright@cao_peng 2013/4/23
2. int str_len(char *a) {  //字符串长度
3.     if (a == 0) {
4.         return 0;
5.     }
6.     char *t = a;
7.     for (;*t;++t)
8.         ;
9.     return (int) (t - a);
10. }
12. void str_copy(char *a,const char *b,int len) {  //拷贝字符串 a = b
13.     for (;len > 0; –len, ++b,++a) {
14.         *a = *b;
15.     }
16.     *a = 0;
17. }
19. char *str_join(char *a,const char *b,int lenb) { //连接字符串 第一个字符串被回收
20.     char *t;
21.     if (a == 0) {
22.         t = (char *) malloc(sizeof(char) * (lenb + 1));
23.         str_copy(t, b, lenb);
24.         return t;
25.     }
26.     else {
27.         int lena = str_len(a);
28.         t = (char *) malloc(sizeof(char) * (lena + lenb + 2));
29.         str_copy(t, a, lena);
30.         *(t + lena) = ’ ’;
31.         str_copy(t + lena + 1, b, lenb);
32.         free(a);
33.         return t;
34.     }
35. }
37. int canMatch(char *input, char *rule) { // 返回最长匹配长度 -1表示不匹配
38.     if (*rule == 0) { //已经到rule尾端
39.         return 0;
40.     }
41.     int r = -1 ,may;
42.     if (*rule == ’*') {
43.         r = canMatch(input, rule + 1);  // *匹配0个字符
44.         if (*input) {
45.             may = canMatch(input + 1, rule);  // *匹配非0个字符
46.             if ((may >= 0) && (++may > r)) {
47.                 r = may;
48.             }
49.         }
50.     }
51.     if (*input == 0) {  //到尾端
52.         return r;
53.     }
54.     if ((*rule == ’?') || (*rule == *input)) {
55.         may = canMatch(input + 1, rule + 1);
56.         if ((may >= 0) && (++may > r)) {
57.             r = may;
58.         }
59.     }
60.     return r;
61. }
63. char * my_find(char  input[],   char rule[]) {
64.     int len = str_len(input);
65.     int *match = (int *) malloc(sizeof(int) * len);  //input第i位最多能匹配多少位 匹配不上是-1
66.     int i,max_pos = - 1;
67.     char *output = 0;
69.     for (i = 0; i < len; ++i) {
70.         match[i] = canMatch(input + i, rule);
71.         if ((max_pos < 0) || (match[i] > match[max_pos])) {
72.             max_pos = i;
73.         }
74.     }
75.     if ((max_pos < 0) || (match[max_pos] <= 0)) {  //不匹配
76.         output = (char *) malloc(sizeof(char));
77.         *output = 0;   // \0
78.         return output;
79.     }
80.     for (i = 0; i < len;) {
81.         if (match[i] == match[max_pos]) { //找到匹配
82.             output = str_join(output, input + i, match[i]);
83.             i += match[i];
84.         }
85.         else {
86.             ++i;
87.         }
88.     }
89.     free(match);
90.     return output;
91. }

1. //copyright@chpeih 2013/4/23
2. char* my_find(char  input[],   char rule[])
3. {
4.     //write your code here
5.     int len1,len2;
6.     for(len1 = 0;input[len1];len1++);
7.     for(len2 = 0;rule[len2];len2++);
8.     int MAXN = len1>len2?(len1+1):(len2+1);
9.     int  **dp;
11.     //dp[i][j]表示字符串1和字符串2分别以i j结尾匹配的最大长度
12.     //记录dp[i][j]是由之前那个节点推算过来  i*MAXN+j
13.     dp = new int *[len1+1];
14.     for (int i = 0;i<=len1;i++)
15.     {
16.         dp[i] = new int[len2+1];
18.     }
20.     dp[0][0] = 0;
21.     for(int i = 1;i<=len2;i++)
22.         dp[0][i] = -1;
23.     for(int i = 1;i<=len1;i++)
24.         dp[i][0] = 0;
26.     for (int i = 1;i<=len1;i++)
27.     {
28.         for (int j = 1;j<=len2;j++)
29.         {
30.             if(rule[j-1]==’*'){
31.                 dp[i][j] = -1;
32.                 if (dp[i-1][j-1]!=-1)
33.                 {
34.                     dp[i][j] = dp[i-1][j-1]+1;
36.                 }
37.                 if (dp[i-1][j]!=-1 && dp[i][j]<dp[i-1][j]+1)
38.                 {
39.                     dp[i][j] = dp[i-1][j]+1;
41.                 }
42.             }else if (rule[j-1]==’?')
43.             {
44.                 if(dp[i-1][j-1]!=-1){
45.                     dp[i][j] = dp[i-1][j-1]+1;
47.                 }else dp[i][j] = -1;
48.             }
49.             else
50.             {
51.                 if(dp[i-1][j-1]!=-1 && input[i-1]==rule[j-1]){
52.                     dp[i][j] = dp[i-1][j-1]+1;
53.                 }else dp[i][j] = -1;
54.             }
55.         }
56.     }
58.     int m = -1;//记录最大字符串长度
59.     int *ans = new int[len1];
60.     int count_ans = 0;//记录答案个数
61.     char *returnans = new char[len1+1];
62.     int count = 0;
63.     for(int i = 1;i<=len1;i++)
64.         if (dp[i][len2]>m){
65.             m = dp[i][len2];
66.             count_ans = 0;
67.             ans[count_ans++] = i-m;
68.         }else if(dp[i][len2]!=-1 &&dp[i][len2]==m){
69.             ans[count_ans++] = i-m;
70.         }
72.         if (count_ans!=0)
73.         {
74.             int len = ans[0];
75.             for (int i = 0;i<m;i++)
76.             {
77.                 printf(“%c”,input[i+ans[0]]);
78.                 returnans[count++] = input[i+ans[0]];
79.             }
80.             for (int j = 1;j<count_ans;j++)
81.             {
82.                 printf(“ ”);
83.                 returnans[count++] = ’ ’;
84.                 len = ans[j];
85.                 for (int i = 0;i<m;i++)
86.                 {
87.                     printf(“%c”,input[i+ans[j]]);
88.                     returnans[count++] = input[i+ans[j]];
89.                 }
90.             }
91.             printf(“\n”);
92.             returnans[count++] = ’\0′;
93.         }
95.         return returnans;
96. }

本文链接地址: c++字符串转换成整数，带通配符的字符串匹配http://www.hongyanliren.com/2014m07/11564.html

相关文章

• ESP8266文档中心
• ESP8266使用AT指令开发示例
• ESP8266-01 固件更新过程
• Arduino+ESP8266WIFI（2）——DHT11温湿度数据自动上传
• Arduino+ESP8266WIFI（1）——模块测试
• Arduino结合ESP8266 Serial WIFI模块访问远程服务器
• 快速排序
• 快速排序基本思路