c*****e
发帖数: 737 | 1 主要是溢出判断上，正的和负的有区别。
网上一搜原来几乎全部都写的有同样问题。 |
q****x
发帖数: 7404 | 2 学艺不精。写完不测试。
【在 c*****e 的大作中提到】
: 主要是溢出判断上，正的和负的有区别。
: 网上一搜原来几乎全部都写的有同样问题。
|
g*********e
发帖数: 14401 | |
i******r
发帖数: 793 | 4 我也被问过这个，当时没想清楚怎么处理溢出的问题
挂了 |
d****o
发帖数: 1055 | 5 哪位大神有比较好的能处理溢出的itoa代码，给贴出来学习学习。
【在 c*****e 的大作中提到】
: 主要是溢出判断上，正的和负的有区别。
: 网上一搜原来几乎全部都写的有同样问题。
|
i**********e
发帖数: 1145 | 6 用 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 - '0';
num = num*10 + dig;
if (sign == 1 && num > INT_MAX ||
sign == -1 && -num < INT_MIN)
overflow = true;
str++;
}
if (sign == -1) {
num = -num;
}
if (overflow) {
return (sign == 1) ? INT_MAX : INT_MIN;
} else {
return (int)num;
}
}
bool isAlpha(char c) {
return c >= '0' && c <= '9';
} |
i**********e
发帖数: 1145 | 7 还有另一个检测溢出的思路就是 wraparound，因为这里只是乘于十而以，如果wraparound 的话 sign 必定会有变化，例如从 + 变成 -。但这个因
语言而异。Java 有wraparound，可以利用此方法来检测溢出。但是 C++ 里的 standard 说明溢出是 undefined behavior，不是每一个编译器都有 wraparound。 |
c*****e
发帖数: 737 | 8 依然有很多问题，比如出错需要报告错误，而你居然overflow了就返回max...
【在 i**********e 的大作中提到】
: 用 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++;
|
i**********e
发帖数: 1145 | 9 我是照着 C++ library 里的 atoi 函数实现。
你当然可以 throw exception 或者返回 error code 等等，这些跟面试官沟通。
【在 c*****e 的大作中提到】
: 依然有很多问题，比如出错需要报告错误，而你居然overflow了就返回max...
|
c*****e
发帖数: 737 | 10 another issue:
suppose char s[] = " -"
your code will access over the boundary of the string
【在 i**********e 的大作中提到】
: 我是照着 C++ library 里的 atoi 函数实现。
: 你当然可以 throw exception 或者返回 error code 等等，这些跟面试官沟通。
|
|
|
i**********e
发帖数: 1145 | 11 Thanks for your test case.
Actually this is ok, because there is always a '\0' character that
terminates a C-style string.
isAlpha('\0') will evaluate as false and break out the loop immediately.
【在 c*****e 的大作中提到】
: another issue:
: suppose char s[] = " -"
: your code will access over the boundary of the string
|
c*****e
发帖数: 737 | 12 and how about
char s = '-'
then call your func with &s?
firstly, "-" is not a valid number, but you return 0.
second, it may access over boundary of memory as well.
【在 i**********e 的大作中提到】
: Thanks for your test case.
: Actually this is ok, because there is always a '\0' character that
: terminates a C-style string.
: isAlpha('\0') will evaluate as false and break out the loop immediately.
|
c****p
发帖数: 6474 | 13 谁家写代码这么变态把一个字符变量的地址传给函数当字符串使。。。
【在 c*****e 的大作中提到】
: and how about
: char s = '-'
: then call your func with &s?
: firstly, "-" is not a valid number, but you return 0.
: second, it may access over boundary of memory as well.
|
c*****e
发帖数: 737 | 14 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
【在 i**********e 的大作中提到】
: Thanks for your test case.
: Actually this is ok, because there is always a '\0' character that
: terminates a C-style string.
: isAlpha('\0') will evaluate as false and break out the loop immediately.
|
c*****e
发帖数: 737 | 15 ok, then char array
char s[2] = {'-', '1'};
or you even call atoi(NULL);
【在 c****p 的大作中提到】
: 谁家写代码这么变态把一个字符变量的地址传给函数当字符串使。。。
|
c****p
发帖数: 6474 | 16 第一种除非在传参时加入串长，否则字串的合法性应该由caller保证。
就用你这个s[2]的例子，如果紧跟其后的内存恰好是"23456\0"，这个函数应该返回-1还
是-123456？
系统提供的atoi和strtol函数原型也只接收串首地址而不接收串长，
错误返回值中也没有处理字符串未以'\0'的情况。
第二种情况也类似于第一种，交给caller或者callee处理都可以。
【在 c*****e 的大作中提到】
: ok, then char array
: char s[2] = {'-', '1'};
: or you even call atoi(NULL);
|
c*****e
发帖数: 737 | 17 ok, then consider:
str = "-"
it will return 0, but that's incorrect.
1还
【在 c****p 的大作中提到】
: 第一种除非在传参时加入串长，否则字串的合法性应该由caller保证。
: 就用你这个s[2]的例子，如果紧跟其后的内存恰好是"23456\0"，这个函数应该返回-1还
: 是-123456？
: 系统提供的atoi和strtol函数原型也只接收串首地址而不接收串长，
: 错误返回值中也没有处理字符串未以'\0'的情况。
: 第二种情况也类似于第一种，交给caller或者callee处理都可以。
|
c****p
发帖数: 6474 | 18 这是另外一个问题，
我只是说写代码的不应该用&c当字符串的这种变态（有意造成段错的）做法。
【在 c*****e 的大作中提到】
: ok, then consider:
: str = "-"
: it will return 0, but that's incorrect.
:
: 1还
|
s**********e
发帖数: 326 | 19 贴个我之前写的代码，仿照java里面的源码写的
public static long stringToLong(String str) throws Exception{
if(!chekValid(str)){
throw new Exception("invalid input!!");
}
long limit;
boolean isNegative = false;
int curIndex = 0;
if(str.charAt(0) == '-'){
limit = Long.MIN_VALUE;
isNegative = true;
curIndex = 1;
}else{
limit = -1 * Long.MAX_VALUE;
}
long preLimit = limit/10;
long result = -1 * (str.charAt(curIndex++) - '0');
while(curIndex < str.length()){
int digit = (str.charAt(curIndex++) - '0');
if(result < preLimit) throw new Exception("preLimit overflow !");
result *= 10;
if(result < limit + digit) throw new Exception("limit overflow!"
);
result = result - digit;
}
if(!isNegative){
result *= -1;
}
return result;
}
public static boolean chekValid(String str){
if(str == null || str.length() == 0) return false;
int strtIndex = 0;
if(str.charAt(0) == '-'){
if(str.length() == 1){
return false;
}
strtIndex = 1;
}
for(int i = strtIndex; i < str.length(); i++){
if(str.charAt(i) - '0' < 0 || str.charAt(i) - '0' > 9)
return false;
}
return true;
}
} |
a**********t
发帖数: 20 | 20 这题其实挺土得，
就是那种你答好了未必出彩，会被怀疑准备过，没答好就要挂的。
所以说，还是要准备的。。。
【在 c*****e 的大作中提到】
: 主要是溢出判断上，正的和负的有区别。
: 网上一搜原来几乎全部都写的有同样问题。
|
|
|
r****t
发帖数: 10904 | 21 真的是 c++ library 的 atoi 么？libc 里面是用 unsigned 来处理溢出，并且有两个
不同的 cutoff 才对阿。
【在 i**********e 的大作中提到】
: 我是照着 C++ library 里的 atoi 函数实现。
: 你当然可以 throw exception 或者返回 error code 等等，这些跟面试官沟通。
|
r****t
发帖数: 10904 | 22 这个错在用户了。
【在 c*****e 的大作中提到】
: ok, then consider:
: str = "-"
: it will return 0, but that's incorrect.
:
: 1还
|
r****t
发帖数: 10904 | 23 这种情况，如果不写操作的话，是不会段错的吧? 我概念不是很清楚。。。
【在 c****p 的大作中提到】
: 这是另外一个问题，
: 我只是说写代码的不应该用&c当字符串的这种变态（有意造成段错的）做法。
|
w**z
发帖数: 8232 | 24 Source Code from Java
/*
* @author Lee Boynton
* @author Arthur van Hoff
* @author Josh Bloch
* @version 1.92, 04/07/06
* @since JDK1.0
*/
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* ASCII minus sign '-' ('\u002D') to
* indicate a negative value. The resulting integer value is returned.
*
* An exception of type NumberFormatException is
* thrown if any of the following situations occurs:
*
* - The first argument is
null or is a string of
* length zero.
* - The radix is either smaller than
* {@link java.lang.Character#MIN_RADIX} or
* larger than {@link java.lang.Character#MAX_RADIX}.
* - Any character of the string is not a digit of the specified
* radix, except that the first character may be a minus sign
* '-' ('\u002D') provided that the
* string is longer than length 1.
* - The value represented by the string is not a value of type
* int.
*
* Examples:
*
* parseInt("0", 10) returns 0
* parseInt("473", 10) returns 473
* parseInt("-0", 10) returns 0
* parseInt("-FF", 16) returns -255
* parseInt("1100110", 2) returns 102
* parseInt("2147483647", 10) returns 2147483647
* parseInt("-2147483648", 10) returns -2147483648
* parseInt("2147483648", 10) throws a NumberFormatException
* parseInt("99", 8) throws a NumberFormatException
* parseInt("Kona", 10) throws a NumberFormatException
* parseInt("Kona", 27) returns 411787
*
*
* @param s the String containing the integer
* representation to be parsed
* @param radix the radix to be used while parsing s.
* @return the integer represented by the string argument in the
* specified radix.
* @exception NumberFormatException if the String
* does not contain a parsable int.
*/
public static int parseInt(String s, int radix)
throws NumberFormatException
{
if (s == null) {
throw new NumberFormatException("null");
}
if (radix < Character.MIN_RADIX) {
throw new NumberFormatException("radix " + radix +
" less than Character.MIN_RADIX");
}
if (radix > Character.MAX_RADIX) {
throw new NumberFormatException("radix " + radix +
" greater than Character.MAX_RADIX");
}
int result = 0;
boolean negative = false;
int i = 0, max = s.length();
int limit;
int multmin;
int digit;
if (max > 0) {
if (s.charAt(0) == '-') {
negative = true;
limit = Integer.MIN_VALUE;
i++;
} else {
limit = -Integer.MAX_VALUE;
}
multmin = limit / radix;
if (i < max) {
digit = Character.digit(s.charAt(i++),radix);
if (digit < 0) {
throw NumberFormatException.forInputString(s);
} else {
result = -digit;
}
}
while (i < max) {
// Accumulating negatively avoids surprises near MAX_VALUE
digit = Character.digit(s.charAt(i++),radix);
if (digit < 0) {
throw NumberFormatException.forInputString(s);
}
if (result < multmin) {
throw NumberFormatException.forInputString(s);
}
result *= radix;
if (result < limit + digit) {
throw NumberFormatException.forInputString(s);
}
result -= digit;
}
} else {
throw NumberFormatException.forInputString(s);
}
if (negative) {
if (i > 1) {
return result;
} else { /* Only got "-" */
throw NumberFormatException.forInputString(s);
}
} else {
return -result;
}
} |
a****a
发帖数: 186 | 25 按照那个 从左往右*10+当前位 的方法，溢出的时候数就变小了，这种方法可行吗？ |
k*****y
发帖数: 744 | 26 这样写是不是比较safe?
bool is_overflow(int sign, int head_number, int unit_number) {
if (sign == 1)
return ((INT_MAX - unit_number)/10 >= head_number)?
false : true;
else
return ((INT_MIN + unit_number)/10 <= head_number)?
false : true;
}
int my_atoi(char *s, int &error) {
int the_number = 0;
int sign = 1;
error = 0;
// skip the the spaces at front
while (*s && *s==' ')
++s;
// determine if there is a sign
if (*s == '-'){
sign = -1;
++s;
}
else if (*s == '+')
++s;
// valid first digit?
if (*s >= '0' && *s <= '9')
// loop while it is still a digit
while (*s >= '0' && *s <= '9') {
int unit_number = *s-'0';
if (is_overflow(sign, the_number, unit_number)) {
error = 1;
break;
}
else
the_number = the_number*10 + sign*unit_number;
++s;
}
else
error = 1;
return the_number;
} |
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
input base is 10, cutoff will be set to 214748364 and cutLimit to either 7 (
sign==1) or 8 (sign==-1), meaning that if we have accumulated a value >
214748364, or equal but the next digit is > 7 (or 8), the number is too big,
and we will return a range error. |
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 base is 10, cutoff will be set to 214748364 and cutLimit to either 7 (
sign==1) or 8 (sign==-1), meaning that if we have accumulated a value >
214748364, or equal but the next digit is > 7 (or 8),the number is too big,
and we will return a range error. |
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
input base is 10, cutoff will be set to 214748364 and cutLimit to either 7 (
sign==1) or 8 (sign==-1), meaning that if we have accumulated a value >
214748364, or equal but the next digit is > 7 (or 8), the number is too big,
and we will return a range error. |
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
input base is 10, cutoff will be set to 214748364 and cutLimit to either 7 (
sign==1) or 8 (sign==-1), meaning that if we have accumulated a value >
214748364, or equal but the next digit is > 7 (or 8), the number is too big,
and we will return a range error. |
|
|
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 base is 10, cutoff will be set to 214748364 and cutLimit to either 7 (
sign==1) or 8 (sign==-1), meaning that if we have accumulated a value >
214748364, or equal but the next digit is > 7 (or 8),the number is too big,
and we will return a range error. |
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 base is 10, cutoff will be set to 214748364 and cutLimit to either 7 (
sign==1) or 8 (sign==-1), meaning that if we have accumulated a value >
214748364, or equal but the next digit is > 7 (or 8),the number is too big,
and we will return a range error. |
p*i
发帖数: 411 | 33 int myatoi(const string& str) {
const int n = str.size();
int curr = 0; // current index
while ((curr < n) && (isspace(str[curr]))) curr++; // skip leading
spaces
int sign = 1; // positive
if (str[curr] == '-') {
sign = -1; curr++;
}
if (curr == n)
throw runtime_error("Invalid input");
// prepare overflow check
int base, extra;
if (sign == 1) {
base = numeric_limits::max() / 10;
extra = numeric_limits::max() % 10;
} else {
// be careful: |MIN| = |MAX|+1
base = -(numeric_limits::min() / 10);
extra = -(numeric_limits::min() % 10);
}
unsigned result = 0;
while ((curr < n) && (isdigit(str[curr]))) {
// first, test if overflow
if (result < base) {
// no problem
result = result*10 + (str[curr] - '0');
} else if (result > base) {
// overflow happened
throw overflow_error("Overflow");
} else {
// result == base, tricky
int digit = str[curr] - '0';
if (digit <= extra)
result = result*10 + digit;
else
throw overflow_error("Overflow");
}
curr++;
}
// we need to know the exact reason of quitting the while loop
while (curr < n) {
if (!isspace(str[curr++]))
throw runtime_error("Invalid input");
}
return (sign==1)? result:-result;
}
【在 c*****e 的大作中提到】
: 主要是溢出判断上，正的和负的有区别。
: 网上一搜原来几乎全部都写的有同样问题。
|
