Finally, you say. Thanks to everyone who posted answers as responses to the original nvidia test post. Here we go:
Question #1: What is different about these two segments of code?
a)
int Clocks(unsigned short* p) {
int val = *p;
val |= (*p << 16);
return val;
}
b)
int Clocks(volatile unsigned short* p) {
int val = *p;
val |= (*p << 16);
return val;
}
ANSWER#1: In a), without volatile, the compiler is free to replace the second read of *p (reading *p and left-shifting 16) with the cached result from the first read. In b), the compiler can make no such optimisation (the spelling is for Ricky Rick), and *p will be read each time. The result of this is that if *p were to change between the first and second statement, a) might not reflect the new value of *p, whereas b) has to. As a few people pointed out, we use volatile in systems programming for things like hardware registers, where the value of the register is likely to change outside of our program’s control.
Question #2: What is wrong with the following code segment?
char* SaveString(const char* s) {
char* p = (char*)malloc(strlen(s));
while(*s)
{
*p++ = *s++;
}
*p = 0;
return p;
}
ANSWER #2: There are, from my count, 2 hard errors (i.e. the function will not do as advertised) and a few possible errors/design errors (that should be pointed out). The hard errors are:
- The character allocated is one character short, so the last null byte is being written off allocated memory. When copying strings, you always write: …malloc(strlen(s) + 1).
- The function returns a pointer to the end of p (at the null byte).
The possible errors/design errors
- You should always check the return value of malloc. Failing to do so can have oh-so-interesting consequences. (For those who would point out that trying to dereference the returned null pointer is invalid, know that you could do exactly that on certain systems, e.g. vax [as Carithers tells it]).
- You should be extremely careful about designing a function that allocates memory for the caller (except for those functions made exactly for that). Since various systems use vastly different memory allocation schemes, forcing the user to use malloc (in this case) can be a very bad choice. This is the reason why the standard C string copying functions take a pointer to an already allocated piece of memory.
That’s all I can think of/remember off the top of my head. I probably missed one somewhere, so let me know if you find anything.
Question #3: Write atoi. Ignore all leading and trailing non-numeric characters,
e.g. "abcd1234defg" will return 1234. If no number can be read, return a -1.
Ignore all '-' characters (no negative numbers), and assume the conversion
will not overflow.
int atoi(char* s) { ....
ANSWER #3 note: I didn’t use isdigit() for these, as I wasn’t sure if we were allowed to. I did ask if we could assume the character set was ASCII, which is somewhat of a requirement for any semblance of sanity in writing the function.
int atoi(char* s) {
int sum = 0;
while(*s && (*s < '0' || *s > '9'))
s++;
if(!(*s))
return -1;
while(*s && *s >= '0' && *s <= '9')
sum = (sum * 10) + (*s - '0');
return sum;
}
Oh, and before I forget: counting bits in an unsigned int:
unsigned int count_bits(unsigned int i)
{
unsigned int numbits = 0;
while(i)
{
numbits++;
i &= i - 1;
}
return numbits;
}
The simple solution is just to shift off a bit each time, but this solution takes advantage of a nice property of subtraction of unsigned ints. Consider i, i – 1, and i & (i -1), where i = 0110_1000:
i 0110_1000 i - 1 0110_0111 i & (i -1) 0110_0000
See how it strips off the last bit? Kudos, Sidney Marshall. Kudos.
Well, that’s it for now. I have an interview with nvidia tomorrow afternoon, so we’ll see if lighting strikes twice.