Amazon Interview Question
Software Engineer / Developerscan u explain a bit more ?
what does the following do?
i = (i<<3) + (i<<1) + ((*str) - '0');
Thanks Yokuki,
This is one of the most awesome tricks I have ever learned! It made my day.
For those wondering how it works:
You have string "364"
Taking chars from left (one by one):
Example: '3'
('3' - '0') - This gives the actual number in the char.
So i becomes 3. (initially i was 0, therefore bit manipulations resulted in 0)
Then we have to somehow make i from 3 to 30 to left shift the number.
Basically, we want to multiply the number by 10.
(i<<3) + (i<<1) does exactly that.
(i<<3) is 8x
(i<<1)is 2x
(i<<3) + (i<<1) becomes 10x.
Well, I guess now its clear to every one.
Twist: Handle negative numbers and out of range case
int atoi( char* source )
{
int ret = 0;
int negative = 1;
char* i = source;
if( *i == '-' ){
negative = -1;
i++;
}
for( ; *i; i++ )
{
if( *source >= '0' && *source <= '9' ){
int temp = ret*10 + (negative)*(*source-'0');
if( temp < MININT || temp > MAXINT )
return 0; // or whatever is your out of range handler
else
ret = temp;
else
return ret;
}
return ret;
}
#define MIN_INT -2147483648
#define MAX_INT 2147483647
int my_atoi(const char str[])
{
if(str == NULL) return 0;
int len = strlen(str);
if(len <= 0) return 0;
int index = 0;
//skip leading spaces
while(str[index] == ' ') index++;
bool isNeg = str[index] == '-';
int outNum = 0;
if(isNeg)
{
index++;
// skip white space after the sign
while(str[index] == ' ') index++;
}
while(index < len)
{
char currentChar = str[index++];
if(currentChar >= '0' && currentChar <= '9')
{
int oldValue = outNum;
int charVal = currentChar - '0';
outNum *= 10;
outNum += charVal;
//overflow underflow detection
if(outNum < oldValue)
{
if(isNeg)
outNum = MIN_INT;
else
outNum = MAX_INT;
return outNum;
}
}
else
break;
}
if(isNeg)
outNum = outNum * -1;
return outNum;
}
// to-do: 1.take the first char in str for signed/unsigned check
- yokuki February 18, 2010// 2.check for invalid char in str
int my_atoi(const char *str)
{
int i=0;
while ( *str )
{
i = (i<<3) + (i<<1) + ((*str) - '0');
++str;
}
return i;
}