Ittiam Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Define "single instruction". If it means 1 assembly instruction, that's only possible if value's already in a register and either we know m and n at compile time so we can prepare the appropriate bitmask, or if a special "bit range extraction" instruction exists.
if i is the byte given, we can extract bits between n and m where m>=n with the following single instruction.
[i & [(0xFF << m) ^ (0xFF<< n)]] >> n
how this works:
we create 2 maska (Assuming m=5 and n=2)
11100000 0xFF << m
11111100 0xFF << n
Now we take xor of the above which gives us below mask
00011100 [(0xFF << m) ^ (0xFF<< n)]
Now if the apply the & gate with the given byte i (Assuming its 01010101) it gives us below byte.
00010100 [i & [(0xFF << m) ^ (0xFF<< n)]]
Now we can shift the byte n times to the right to get the extracted byte
00000101
-------------------------------------------
Please let me know if you see any improvement or if you have any comment.
If 'x' in an int input and 'm' & 'n' are indices with 0-base as LSB, then the output can be written in one instruction as
- ravi December 26, 2011y = (x & ((1 << m) - (1 << (n+1)))) >> (n+1);
Explanation:
1) (1<<m) returns 2 to the power m
2) (1<<(n+1)) returns 2 to the power (n+1)
3) Difference of above 2 returns the mask with all bits set between m and n (both exclusive)
4) Now AND the above mask with original input 'x' to extract bit values for only the bits between m and n (both excluded)
5) I assumed that the expected result needs to be returned considering the (n+1)th bit as LSB, and hence the last right shift operation for (n+1) times.
Let's take an example:
int m = 6; //1st index
int n = 1; // 2nd index
int x = 173; //input = 10101101
int y = (x & ((1 << m) - (1 << (n+1)))) >> (n+1);
//(1<<6) - (1<<(1+1)) = 01000000 - 00000100 = 00111100
//x & 00111100 = 10101101 & 00111100 = 00101100 (144 in base 10)
//finally, y = 00101100 >> (1+1)= 00001011 (11 in base 10)