g*********s
发帖数: 1782 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: gandjmitbbs (Nothing), 信区: JobHunting
标 题: 经典题atoi的溢出处理
发信站: BBS 未名空间站 (Tue Feb 22 21:40:03 2011, 美东)
int atoi(const char* s);
assuming INT_MAX = 2^31-1, INT_MIN = -2^31, the following must hold:
atoi("2147483648") = 2147483647
atoi("-2147483649") = -2147483648
but this seems a little tricky. any elegant solution to handle the
overflow? |
|
c********l
发帖数: 8138 | 2 1.小公司招人时是否应该问atoi这种问题？
答：i don't care，那是小公司老板自己的事情。
实践是检验真理的唯一标准。
如果小公司老板觉得这么做对，那就问来面试的大学生。反正招进来的大学生好，技术
就能成
如果这一条技术问题与小公司的用人目的不吻合，那么老板自己吃亏
2.大公司招人时是否应该问atoi这种问题？
答：I don't care,
but if you are looking for a job, you have to take EXTRA care.
别看大公司面试的题目都相当“应试”，但应试是唯一的方法。
我面过的印度阿三，不但人际关系强，而且准备面试题上也强，反正你问他们“
reverse linked list”或者是“detect a cycle in a linked list”这种问题，
他们能倒背如流。对，他们中大部分编程不行，就是靠背！
反倒是中国的小留，纵使实践经验强，但是面试题preparedness不够，吃了不少亏。
在这里，大公司多问一些基础题目，实际上对于中国学生是有好处的。但现在的90后小留
们，由于被“素质教育”的邪魔所忽悠，把... 阅读全帖 |
|
g*********s
发帖数: 1782 | 3 int atoi(const char* s);
assuming INT_MAX = 2^31-1, INT_MIN = -2^31, the following must hold:
atoi("2147483648") = 2147483647
atoi("-2147483649") = -2147483648
but this seems a little tricky. any elegant solution to handle the
overflow? |
|
c*****e
发帖数: 737 | 4 Tested it with
char s = '1', r = ' ';
std::cout << atoi(&s) << "\n";
it prints something randomly, and are wrong.
[root@localhost hello]# ./atoi
1
[root@localhost hello]# ./atoi
10 |
|
S*******0
发帖数: 198 | 5 这个版上讨论过多次了，这是我的code
//atoi
public static int atoi(String str) throws Exception{
String expression = str.trim();
if(expression==null||expression.equals("")){
throw new Exception("expression is empty");
}
int sign = 1;
int index = 0;
if(expression.charAt(0) == '-'){
sign = -1;
}
if(expression.charAt(0) == '-' || expression.charAt(0) == '+'){
index++;
if(expression.length()==1){
... 阅读全帖 |
|
n**e
发帖数: 116 | 6 看到版上太多关于atoi的讨论，我贴一个我的实现，希望对有所帮助。如发现bugs，请
指正。
//--------------------------------------------------------------------
// Convert a string to an integer
// How to handle overflow issue:
// Compute the cutoff value between legal numbers and illegal
// numbers. That is the largest legal value, divided by the
// base. An input number that is greater than this value, if
// followed by a legal input character, is too big. One that
// is equal to this value may be valid or not; the limit
// between... 阅读全帖 |
|
r****t
发帖数: 10904 | 7 atoi(" -12a") 应该返回 -12，标准的 atoi 不检测 overflow。 |
|
t**r
发帖数: 3428 | 8 int atoi(const char *str) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (!str){return 0;}
int i=0;
bool pos=true;
int res=0;
while (str[i]==' '){ i++;}
if (str[i]=='+'){ pos=true;i++;}
if (str[i]=='-'){ pos = false;i++;}
if (!isdigit(str[i])){return 0;}
while (isdigit(str[i])){
if (pos && res>INT_MAX/10){return INT_MAX;}
if (pos && res==INT_MAX/10... 阅读全帖 |
|
L*****e
发帖数: 8347 | 9 靠！一道atoi的题你们就能扯到i++ ++i，再扯倒矩阵运算，再扯到GPU，再扯到宏和编
译优化，楼主的code里的八哥都是小节问题了。。。难怪那么多人觉得面试问atoi太难
了，十年java经验也得挂。。。
★ 发自iPhone App: ChineseWeb 8.2.2
★ 发自iPhone App: ChineseWeb 8.2.2 |
|
i*********y
发帖数: 352 | 10 对方ID:
atoi
Feedback (+/-/0):
+
具体交易内容:
SPG 24,000 points
我的评价:
交易愉快。 |
|
K*****k
发帖数: 430 | 11 从许多面经看，atoi常考，而itoa几乎不考。 |
|
K*****k
发帖数: 430 | 12 atoi是考test case的典范，而itoa则没有太多的test case要考虑？ |
|
r********g
发帖数: 1351 | 13 atoi可以考overflow的判断吧，还有楼上说的test case... |
|
|
m**********r
发帖数: 122 | 15 有没有一个全面一点得关于atoi的答案讨论，包括test case， overflow 等等。 |
|
e***s
发帖数: 799 | 16 atoi可以有不一样的input要求，就有不一样的input验证
比如string中包含子母，是throw error，还是把字母之前的数字输出。
+/-的位置可不可以随便放之类的 |
|
|
A**u
发帖数: 2458 | 18 象c的atoi一样
不用处理溢出
只有在INT_MIN, INT_MAX范围内的，才是正确值 |
|
d****n
发帖数: 1637 | 19 short int atoi(char s[])
{
short int i, n;
n = 0;
if (s[0]=='-' || s[0]=='+') i=1;else i=0;
for (; s[i] >= '0' && s[i] <= '9'; ++i)
n = 10 * n + (s[i] - '0');
return (s[0]=='-'?n*-1:n)
} |
|
r****t
发帖数: 10904 | 20 expression.equals("") is not sufficient.
man pages says strtol needs to call isspace to remove the leading spaces. atoi.c at least processed \t and spaces. |
|
i**********e
发帖数: 1145 | 21 这里：
leetcode.com/onlinejudge
Problem title: String to integer (atoi) |
|
i**********e
发帖数: 1145 | 22 用 long long 检测 overflow，简单一些。。。
int atoi(const char *str) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int sign = 1;
while (*str == ' ') {
str++;
}
if (*str == '+') {
str++;
} else if (*str == '-') {
sign = -1;
str++;
}
long long num = 0;
bool overflow = false;
while (!overflow && isAlpha(*str)) {
int dig = *str... 阅读全帖 |
|
i**********e
发帖数: 1145 | 23 我是照着 C++ library 里的 atoi 函数实现。
你当然可以 throw exception 或者返回 error code 等等，这些跟面试官沟通。 |
|
c*****e
发帖数: 737 | 24 ok, then char array
char s[2] = {'-', '1'};
or you even call atoi(NULL); |
|
c****p
发帖数: 6474 | 25 第一种除非在传参时加入串长，否则字串的合法性应该由caller保证。
就用你这个s[2]的例子，如果紧跟其后的内存恰好是"23456\0"，这个函数应该返回-1还
是-123456？
系统提供的atoi和strtol函数原型也只接收串首地址而不接收串长，
错误返回值中也没有处理字符串未以'\0'的情况。
第二种情况也类似于第一种，交给caller或者callee处理都可以。 |
|
r****t
发帖数: 10904 | 26 真的是 c++ library 的 atoi 么？libc 里面是用 unsigned 来处理溢出，并且有两个
不同的 cutoff 才对阿。 |
|
n**e
发帖数: 116 | 27 How to handle overflow issue on atoi? Hopefully this will be of help.
Compute the cutoff value between legal numbers and illegal numbers. That is
the largest legal value, divided by the base. An input number that is
greater than this value, if followed by a legal input character, is too big.
One that is equal to this value may be valid or not; the limit between
valid and invalid numbers is then based on the last digit.
For instance, if the range for longs is [-2147483648..2147483647] and the... 阅读全帖 |
|
n**e
发帖数: 116 | 28 How to handle overflow issue on atoi? Hope this is of help.
Compute the cutoff value between legal numbers and illegal numbers. That is
the largest legal value, divided by the base. An input number that is
greater than this value, if followed by a legal input character, is too big.
One that is equal to this value may be valid or not; the limit between
valid and invalid numbers is then based on the last digit.
For instance, if the range for longs is [-2147483648..2147483647] and the
input bas... 阅读全帖 |
|
n**e
发帖数: 116 | 29 How to handle overflow issue on atoi? Hopefully this will be of help.
Compute the cutoff value between legal numbers and illegal numbers. That is
the largest legal value, divided by the base. An input number that is
greater than this value, if followed by a legal input character, is too big.
One that is equal to this value may be valid or not; the limit between
valid and invalid numbers is then based on the last digit.
For instance, if the range for longs is [-2147483648..2147483647] and the... 阅读全帖 |
|
n**e
发帖数: 116 | 30 How to handle overflow issue on atoi? Hopefully this will be of help.
Compute the cutoff value between legal numbers and illegal numbers. That is
the largest legal value, divided by the base. An input number that is
greater than this value, if followed by a legal input character, is too big.
One that is equal to this value may be valid or not; the limit between
valid and invalid numbers is then based on the last digit.
For instance, if the range for longs is [-2147483648..2147483647] and the... 阅读全帖 |
|
n**e
发帖数: 116 | 31 How to handle overflow issue on atoi? Hope this is of help.
Compute the cutoff value between legal numbers and illegal numbers. That is
the largest legal value, divided by the base. An input number that is
greater than this value, if followed by a legal input character, is too big.
One that is equal to this value may be valid or not; the limit between
valid and invalid numbers is then based on the last digit.
For instance, if the range for longs is [-2147483648..2147483647] and the
input bas... 阅读全帖 |
|
n**e
发帖数: 116 | 32 How to handle overflow issue on atoi? Hope this is of help.
Compute the cutoff value between legal numbers and illegal numbers. That is
the largest legal value, divided by the base. An input number that is
greater than this value, if followed by a legal input character, is too big.
One that is equal to this value may be valid or not; the limit between
valid and invalid numbers is then based on the last digit.
For instance, if the range for longs is [-2147483648..2147483647] and the
input bas... 阅读全帖 |
|
a********n
发帖数: 1287 | 33 按照c++ reference. 输入错误返回0，上溢返回INT_MAX, 下溢返回INT_MIN.
谢谢。
//return 0 if invalid
int atoi(const char*s) {
assert(s);
const char *p = s;
int sign = 1;
int limit = INT_MAX;
int n = 0;
//skip space
while(*p == ' ') {
p++;
}
if(*p == '-') {
sign = -1;
p++;
limit = INT_MIN;
}else if(*p == '+'){
p++;
}
while(*p) {
if(*p>='0' && *p<='9'){
if(n > INT_MAX/10) {
return sign? INT_MAX: INT... 阅读全帖 |
|
i**********e
发帖数: 1145 | 34 基本思路对，但可能有些 case 考虑不全，例如 INT_MIN = -2147483648，不是 -
2147483647（考虑 int 为 32-bit），要小心处理这个溢出，很多人很容易掉进的陷阱。
还有就是 "1a"，应该 output 是 1，而不是 0。
不过我觉得这些细节不大要紧，最重要是问好问题来，知道 input requirement就好了。
可以在这里执行你的代码：
http://www.leetcode.com/onlinejudge
Problem: String to Integer (atoi)
Progress: 23/30 test cases passed.
input output expected
"-2147483648" 2147483647 -2147483648
"-2147483649" 2147483647 -2147483648 |
|
L***Q
发帖数: 508 | 35 assert(s)应该不对，s为null应该返回0.
const char *p = s;必要不大，可以直接在s上操作，已经是const char*了。俺贴一下
俺的，在http://www.leetcode.com/onlinejudge上测试通过了。
思路比较简单，在判断overflow上借鉴了ihasleetcode大牛用long long的方法。
- step1：NULL string和空string的判断
- step2：跳过最初的空格，判断符号
- step3：读取字符直到非数字。用long long保存中间结果，和INT_MAX和INT_MIN比较
。这样比较简单。
int atoi(const char* str)
{
if ((str == NULL) || (*str == '\0'))
return 0;
bool sign = false;
while (*str == ' ')
str ++;
if (*str == '-')
{
sign = true;
... 阅读全帖 |
|
s******n
发帖数: 3946 | 36 要那么复杂么，只要判断前一个数和后一个数是否翻转了"-"即可
int atoi(char* str) {
bool neg = false;
if (*str=="-") {
str++;
neg = true;
} else if (*str=="+")
str++;
int value = 0;
while (*str) {
int digit = *str-'0';
if (digit>9 || digit<0) throw "error";
int newvalue = value*10 + neg?(-digit):digit;
if (value>0 && newvalue<0 || value<0 && newvalue>0) throw "overflow";
value = newvalue;
str++;
}
return value;
}
} |
|
o****d
发帖数: 2835 | 37 http://discuss.leetcode.com/questions/192/string-to-integer-ato
Am I right?
We can separate INT_MAX and INT_MIN to first n-1 digits and last one digit,
which can be used to check overflow before the answer really overflows. Note
that abs(INT_MIN)=INT_MAX+1.
class Solution {
public:
int atoi(const char *str) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int pos=0;
//skip whitespace
while(str[pos]==' ')pos++;
//check if negative
int negative=0;
if(... 阅读全帖 |
|
k*******2
发帖数: 84 | 38 另外，像atoi这种题目，面试如果问到了，大家觉得要答成什么样为好？多谢！！！ |
|
g***j
发帖数: 1275 | 39 为啥这个代码大小集合都可以过呢？ 明明有result*10啊
class Solution {
public:
int atoi(const char *str) {
long long result(0);
bool sign(true);
for(;*str && *str==' ';++str);
if(*str=='-'){
sign=false;
++str;
}
else if(*str=='+') ++str;
while(*str){
if(isdigit(*str)){
result=result*10+*str-'0';
if(sign&&result>INT_MAX) return INT_MAX;
else if(!sign&&-result阅读全帖 |
|
W*********y
发帖数: 481 | 40 string matching那些题很重要吧？
atoi这种属于细节题
string |
|
p***o
发帖数: 1252 | 41 atoi is part of the standard inherited from C90. You can find it in Table 49
of the C++98 standard. |
|
D*****r
发帖数: 6791 | 42 我也来抄写一遍：（擦，写了半个小时放弃了，又要判断是不是负数，又要判断上下界
，记不住interger的上下界macro,超出上下界还得返回errno，需要exit么？。面试挂
了。）
int atoi(const char *str) {
int i, result, t;
char* p;
if (!str) return 0;
i = 0;
result = 0;
t = 0;
p = str;
while (*p) {
t = (int)(p[i]-'0');
if (!isdigit(t)） return -1;
result = result * 10 + t;
}
} |
|
p***o
发帖数: 1252 | 43 atoi都不明白的人写带循环的代码估计是没戏的。 |
|
e***e
发帖数: 3872 | 44 能抄来凑出正确答案就行，if不会又有什么关系？
atoi这种路子是武当少林的气宗（现在的牛人当然还是这宗出来的，记得Knuth讲起自
己的code来，那个亲密流畅……），但最后笑傲江湖的是剑宗（是，现在要会找，会抄
，会拼凑还是要先练吐納）和变态：机器码农——我理解的葵花宝典。 |
|
n*****t
发帖数: 22014 | 45 atoi 不会写，抄出来的也是错。抄只是省时间，不是无脑 |
|
f*******t
发帖数: 7549 | 46 楼主能举个不会写atoi，但能抄出能运行的代码的例子？
网上几乎所有的代码片断都有错，不能直接编译运行，我无法理解不懂的人如何抄。 |
|
e***e
发帖数: 3872 | 47 所以能抄能拼的人，就算不会写atoi，也比只会做题不会抄的人厉害——两种熟练有相
关性，但没有必然联系。
。。 |
|
r*g
发帖数: 3159 | 48 要是一个人都招不到，面试的自然会反思，改方法。
要是应聘的大大多于需要招的，就算是招个看大门的，非要你写atoi，应聘的也没辙喊
冤，说用不到。 |
|
i**i
发帖数: 1500 | 49 没吃过猪肉，总得见过猪跑吧。
会写atoi才粘得上"见过猪跑"的边。抄东西的时候难道不需要知道从哪个括号开始抄吗? |
|
|
