Here's my lunch break solution to atoi. (and here's hoping WordPress has intelligent handling of whitespace...)
<pre> int atoi ( char *s ) { while ( ! isnum ( *s ) ) { ++s; if ( ! *s) return -1; } char *left = s; while ( isnum ( *s ) ) ++s; int sum = 0, place = 1; while ( --s > left ) { sum += ( (*s) - '0' ) * place; place *= 10; } return sum; } </pre>
For #1, I'm not famliar enough with volatile to say... it always connotes scary mental images of concurrency and nasty hardware issues like caching...
For #2, every C programmer should have a mental concept of what allocating a buffer to hold a string should look like, and this doesn't match. Need a "+1" after the call to strlen to make room for the terminating NUL.
Score me!
Peace,
Warren
noah
· 3 years ago
Your atoi looks like it will work in most cases (although it may do strange things in the case where s[0] = 0, since I'm not sure how isnum('\0') will work), although its a bit more complicated than it needs to be (hint: instead of multiplying the digit you are adding to the sum by the place of the digit, can you a similar operation to the sum instead, i.e. working left -> right?). Also, I think you might leave off the largest digit by accident (with: <pre>--s > left</pre>
and left being the first numeral, then you will skip over it on the way back).
As for question#2, that is only one of the errors. From my count, there are at least 3.
For #1, you are on the right track, you just need to use your imagination at what the compiler can do with the code that is there.
I would give you near full credit for atoi (near full credit for workingness, partial credit for being a bit over-complicated), 1/3 credit on #2, and a bit for #1. And, of course, my love and affection for being the Warren. Cheers!
mwoz
· 3 years ago
For the atoi, I felt that supporting the -1 return value would be a bit inelegant, so mine returns 0 on error instead. int atoi( char* s ) { int i = 0; while( !( ( *s - 0x0030 )
mwoz
· 3 years ago
(It seems my previous comment was cut off due to the presence of <, here is it again)
For the atoi, I felt that supporting the -1 return value would be a bit inelegant, so mine returns 0 on error instead. int atoi( char* s ) { int i = 0; while( !( ( *s - 0x0030 ) < 10U ) && *++s ); while( *s && ( *s - 0x0030 ) < 10U ) i = ( i << 3 ) + i + i + *s++ - 0x0030; return i; }
One of the other errors in #2 is the fact that it returns a pointer to the end of the string not the beginning.
In number 1 the without the volatile the compiler is likely to optimize this statement: val |= (*p << 16); to something like this: *p |= (*p << 16); Which will overflow (because *p is only a short), whereas val is an integer.
noah
· 3 years ago
mwoz:
First, returning -1 for a function that can only return integers >= 0 makes much more sense than returning the legal value, 0. I'm not sure what you mean by inelegant, but I think following the paradigm of most other functions of the same type makes much more sense, as well as returning an illegal value.
As to your answer for atoi, that is probably some of the most illegible C/C++ code I've seen in awhile. First of all, use '0' to get the value of the character 0, not a literal hex value. Second, your initial while will have major issues. If you take any character less than '0' in the ascii range, that value - 0x0030 will be less than 10U. So your function would include, for example, most punctuation as a number. The same holds true for the other loop.
The whole i = (i << 3) + i + i is just plain silly. Multiply by ten. Multiplying by 8 and adding twice just looks ridiculuous. Never mind the fact that you just killed the compiler's ability to produce code and the processor's ability to pipeline, the code is just plain inelegant. You are closer to the right idea, but please, for the sake of humanity, never _ever_ write anything like that.
For Question #2, that is one of the other errors.
For Question #3, you are working in the wrong direction. val is a copy of *p, and the compiler can't magically assign to *p what it was going to assign to val. The compiler can cache reads of the thing, but it can't magically change it in one case but not the other.
Andrew Younge
· 3 years ago
well making something volatile in question #1 im pretty sure tells the compliler not to optimize anything out about that variable. So in that examble, part a would probably optimize out the assignment part in "int val = *p;" (assuming we are using gcc 3.3 and not 2.X). This would seem probably harmless except for the fact that we may actually want to do this b/c that may be mapped to a device of some sort, so that statement is explisitly needed. This would mean that only part B would work correctly under such conditions.
I also think the volatile modifier also has something to do w/ multithreaded programming in C++ which probably has the same idea as above but just in a different context?
For question #2, because s was declared const, you cannot actually modify it, which you are doing when you say s++. instead maybe use a index variable and do something like s[i];i++;
im not sure about this, but wouldnt you want to set your variable p back to the start of the string and not at the very end of it?
For question #3.... im lazy and someone already answered it :-P let me know how i did :-P
noah
· 3 years ago
#1 - You have the right idea, now you just have to say what exactly the compiler could do about it, and what you have written isn't entirely correct.
#2 - s++ modifies s, but s itself isn't const; it was declared "const char*", which is a (non-const) pointer to constant characters. The second thing you mentioned (setting p back to the start of the string) is correct, as mwoz pointed out in his comment.
Warren
· 3 years ago
For #3, there's also a fair bit of sloppiness in checking variables for validity, making sure malloc returns a valid pointer, etc, but even assuming all that, Alexandrescu and Raymond Chen are still unhappy with you, because your caller doesn't know with what API/operator/incantation that dynamic memory was allocated...
noah
· 3 years ago
For the memory part, are you talking about question #2? If so, it is an extremely valid point that we shouldn't forget, _ever_. If you create functions that are quasi-public, you should almost never be allocating memory for the caller (unless it is an explicit part of the API, e.g. malloc/calloc/realloc/etc.). I don't think that is what nvidia wanted as part of the answer, but it definitely crossed my mind. As to the Raymond Chen reference, I searched for a bit but couldn't find the article (it was recent, if I remember correctly) where he talked about how important it is to match up allocators/deallocators.
Checking for a valid result from malloc is the last of the major problems, I believe. I may have missed some, so please feel free to point out any others that you find.
mwoz
· 3 years ago
"Second, your initial while will have major issues. If you take any character less than ‘0? in the ascii range, that value - 0?0030 will be less than 10U. So your function would include, for example, most punctuation as a number. The same holds true for the other loop." Actually 10U forces the operation to be unsigned: "If either operand is of type unsigned int, the other operand is converted to type unsigned int." - MSDN C++ reference (http://msdn2.microsoft.com/en-us/library/09ka8b...)
noah
· 3 years ago
mwoz:
Quote the C++ or C standard if you want, but don't quote MSDN. It isn't the standard and has never been.
You are correct and my initial criticism was not: primitives are casted towards unsigned-ness, not away from. In addition, according to the C standard (6.3.1.3.2):
"Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value". This means that the cast would leave you with a number greater than 10, and therefore that part of your solution will work.
Regardless, its rather unclear what you mean in the code - you are relying on an implicit (and probably unassumed, as in why it is one of the more prevalent warnings created with "g++ -Wall") cast to bring a number into a range that makes no sense conceptually, but happens to work technically. I'm probably not the only person who at least had to think about where the implicit cast was, and what effect it would have on the resulting statement.
This style is consistent with your use of "(i << 3) + i + i", and using "0x0030" instead of (the character) '0'. All of these work technically, but are semantically (in reference to the problem) meaningless. In the same respect, I could have written (for the in-range check):
Which will probably also work, but looks like it came out of my ass instead of my head. The point is still that you should write what you mean, not what you think looks cool. Remember that.
All Comments
edit by noah: fixed up the spacing for the code
Here's my lunch break solution to atoi. (and here's hoping WordPress has intelligent handling of whitespace...)
<pre>
int atoi ( char *s )
{
while ( ! isnum ( *s ) )
{
++s;
if ( ! *s)
return -1;
}
char *left = s;
while ( isnum ( *s ) )
++s;
int sum = 0, place = 1;
while ( --s > left )
{
sum += ( (*s) - '0' ) * place;
place *= 10;
}
return sum;
}
</pre>
For #1, I'm not famliar enough with volatile to say... it always connotes scary mental images of concurrency and nasty hardware issues like caching...
For #2, every C programmer should have a mental concept of what allocating a buffer to hold a string should look like, and this doesn't match. Need a "+1" after the call to strlen to make room for the terminating NUL.
Score me!
Peace,
Warren
Your atoi looks like it will work in most cases (although it may do strange things in the case where s[0] = 0, since I'm not sure how isnum('\0') will work), although its a bit more complicated than it needs to be (hint: instead of multiplying the digit you are adding to the sum by the place of the digit, can you a similar operation to the sum instead, i.e. working left -> right?). Also, I think you might leave off the largest digit by accident (with:
<pre>--s > left</pre>
and left being the first numeral, then you will skip over it on the way back).
As for question#2, that is only one of the errors. From my count, there are at least 3.
For #1, you are on the right track, you just need to use your imagination at what the compiler can do with the code that is there.
I would give you near full credit for atoi (near full credit for workingness, partial credit for being a bit over-complicated), 1/3 credit on #2, and a bit for #1. And, of course, my love and affection for being the Warren. Cheers!
int atoi( char* s )
{
int i = 0;
while( !( ( *s - 0x0030 )
For the atoi, I felt that supporting the -1 return value would be a bit inelegant, so mine returns 0 on error instead.
int atoi( char* s )
{
int i = 0;
while( !( ( *s - 0x0030 ) < 10U ) && *++s );
while( *s && ( *s - 0x0030 ) < 10U )
i = ( i << 3 ) + i + i + *s++ - 0x0030;
return i;
}
One of the other errors in #2 is the fact that it returns a pointer to the end of the string not the beginning.
In number 1 the without the volatile the compiler is likely to optimize this statement:
val |= (*p << 16);
to something like this:
*p |= (*p << 16);
Which will overflow (because *p is only a short), whereas val is an integer.
First, returning -1 for a function that can only return integers >= 0 makes much more sense than returning the legal value, 0. I'm not sure what you mean by inelegant, but I think following the paradigm of most other functions of the same type makes much more sense, as well as returning an illegal value.
As to your answer for atoi, that is probably some of the most illegible C/C++ code I've seen in awhile. First of all, use '0' to get the value of the character 0, not a literal hex value. Second, your initial while will have major issues. If you take any character less than '0' in the ascii range, that value - 0x0030 will be less than 10U. So your function would include, for example, most punctuation as a number. The same holds true for the other loop.
The whole i = (i << 3) + i + i is just plain silly. Multiply by ten. Multiplying by 8 and adding twice just looks ridiculuous. Never mind the fact that you just killed the compiler's ability to produce code and the processor's ability to pipeline, the code is just plain inelegant. You are closer to the right idea, but please, for the sake of humanity, never _ever_ write anything like that.
For Question #2, that is one of the other errors.
For Question #3, you are working in the wrong direction. val is a copy of *p, and the compiler can't magically assign to *p what it was going to assign to val. The compiler can cache reads of the thing, but it can't magically change it in one case but not the other.
I also think the volatile modifier also has something to do w/ multithreaded programming in
C++ which probably has the same idea as above but just in a different context?
For question #2, because s was declared const, you cannot actually modify it, which you are doing when you say s++. instead maybe use a index variable and do something like s[i];i++;
im not sure about this, but wouldnt you want to set your variable p back to the start of the string and not at the very end of it?
For question #3.... im lazy and someone already answered it :-P let me know how i did :-P
#2 - s++ modifies s, but s itself isn't const; it was declared "const char*", which is a (non-const) pointer to constant characters. The second thing you mentioned (setting p back to the start of the string) is correct, as mwoz pointed out in his comment.
For the memory part, are you talking about question #2? If so, it is an extremely valid point that we shouldn't forget, _ever_. If you create functions that are quasi-public, you should almost never be allocating memory for the caller (unless it is an explicit part of the API, e.g. malloc/calloc/realloc/etc.). I don't think that is what nvidia wanted as part of the answer, but it definitely crossed my mind. As to the Raymond Chen reference, I searched for a bit but couldn't find the article (it was recent, if I remember correctly) where he talked about how important it is to match up allocators/deallocators.
Checking for a valid result from malloc is the last of the major problems, I believe. I may have missed some, so please feel free to point out any others that you find.
Actually 10U forces the operation to be unsigned:
"If either operand is of type unsigned int, the other operand is converted to type unsigned int." - MSDN C++ reference (http://msdn2.microsoft.com/en-us/library/09ka8b...)
mwoz:
Quote the C++ or C standard if you want, but don't quote MSDN. It isn't the standard and has never been.
You are correct and my initial criticism was not: primitives are casted towards unsigned-ness, not away from. In addition, according to the C standard (6.3.1.3.2):
"Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value". This means that the cast would leave you with a number greater than 10, and therefore that part of your solution will work.
Regardless, its rather unclear what you mean in the code - you are relying on an implicit (and probably unassumed, as in why it is one of the more prevalent warnings created with "g++ -Wall") cast to bring a number into a range that makes no sense conceptually, but happens to work technically. I'm probably not the only person who at least had to think about where the implicit cast was, and what effect it would have on the resulting statement.
This style is consistent with your use of "(i << 3) + i + i", and using "0x0030" instead of (the character) '0'. All of these work technically, but are semantically (in reference to the problem) meaningless. In the same respect, I could have written (for the in-range check):
while(*s / 0x10 > 2 && *s / 0x10 < 5 && *s % 0x10 < 0xa)
Which will probably also work, but looks like it came out of my ass instead of my head. The point is still that you should write what you mean, not what you think looks cool. Remember that.