Qualcomm Interview Question
Software Engineer / DevelopersSolution: I am trying to use a mask 0x01111111 (0x7F) (7 bits '1') to extract the most significant bits for each mapping. Assume "char A[]" stores the byte stream. Put a non-use number into A[0] to start. The real stream starts at A[1];
"turn" records how many extractions are done. Which is reset each 8 turns, because a byte is 8 bits;
A[i-1]>>(8-turn) is to shift the remain bits to the lest significant bits) from last turn extraction. ((A[i] & (0x7F >> turn)) << turn) is to extract bits to fill up 7 bits and append to the next high significant bits.
=====================================
main() {
char A[10] = {000, 0, 1, 2, 3, 4, 5, 6, 7, 8};
char table[9] = {A, B, C, D, E, F, G, H, I}
int turn=0, out, num;
for (i=1; i < 10; i++) {
out = (A[i-1]>>(8-turn) ) | ((A[i] & (0x7F >> turn)) << turn);
turn++;
turn %= 8;
printf("output is:%c", table[out]);
}
}
void out7bitstream()
{
byte st[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int i = 0;
int iRemainingBits = 0;
int iRemainingValue = 0;
int iTmp = 0;
for (i = 0; i < sizeof(st); i++)
{
iTmp = 1;
printf("%d ", (iRemainingValue << (7 - iRemainingBits)) | (st[i] >> (iRemainingBits + 1)));
for (int j = 0; j < iRemainingBits; j++)
{
iTmp = 1+ (iTmp << 1);
}
iRemainingValue = st[i] & iTmp;
iRemainingBits++;
iRemainingBits = iRemainingBits % 7;
if (iRemainingBits == 0)
{
i--;
iRemainingValue = 0;
}
}
}
void shift()
{
char A[10] = {0x0, 0x04, 0x10, 0x40....};
char table[10] = {' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
int turn=1, out, i;
for (i=1; i < 10;) {
int t1 = A[i-1]<<(8-turn);
int t2 = A[i]>>(turn+1);
out = (t1|t2)& 0x7F ;
turn++;
if(turn %= 8) i++;
printf("%c", table[out]);
}
}
Contents of array A are given as an input: a byte array. We are also given a table (Hashtable style). What our program should do is that extract next 7 bits from the array A and return from the Hashtable the value corresponding to the value 7 bit key (just extracted).
The challenge of this problem is bit level manipulation to use the next 7 bits from the array A from byte(=8 bits) stream.
i did not check this for compilation errors.
void main(void)
{
char A[10...] = {0,0,0,0,1,1,0,1,0,0,0,0,1,1...};
char B[20] = "";
unsigned char uchByte7 = 0x00;
for(i = 0 ; i<sizeof(A); i++ )
{
uchByte7 <<= 1;
uchByte7 |= A[i] & 0x1;
if(((i+1)%7) == 0)
{
sprintf(B,"%s%c",B,MapTable(uchByte)); //map table funciton
uchByte7 = 0;
}
}
if((i+1)%7 > 0)
{
sprintf(B,"%s%c",B,MapTable(uchByte)); // add remaining byte straem, incomplete byte stream
}
printf("Code = %s",B);
}
char MapTable(unsigned char uchCode)
{
char Table[100] = {'A','B','C','D'...};
return Table[uchCode];
}
I also didn't understand the question. Please PLEASE TRY TO EXPLAIN THE QUESTION IN DETAIL AND THE SOLUTION TOO. The question seems very confusing. I have been trying to understand it for past 1 hour, but the question is very very confusing. Can anyone provide the link to a question of similar kind!
Input stream consists of contiguous 7 bit "character code"s. Code 0x0 represent 'A', code 0x1 represents 'B', etc. If 13 "character code"s are sent in a burst, you will see a 91-bit bit stream. On the receiver end, you can use 12 bytes to save them in memory buffer for processing. The last byte will have 5 padding bits (5 = 8*12-91). To recover the "character codes" from memory buffer, you extract 7 bits at a time from these bytes sequentially.
It's for embedded software eng. position.
- graduator November 27, 2007