Saturday, January 21, 2012

Extract Bits

Given two indices in a byte m and n such that m>=n extract all the bits between m and n in a single instruction.

Method 1
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

Method 2

If 'x' is an int input and 'm' & 'n' are indices with 0-base as LSB, then the output can be written in one instruction as
y = (x & ((1 << (m-1)) - (1 << (n-1)))) >> n;
Explanation:
1) (1<<(m-1)) 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)th bit as LSB, and hence the last right shift operation for n times.

Let's take an example:
int m = 7; //1st index
int n = 2; // 2nd index
int x = 173; //input = 10101101
Take out bits from 2nd to 7th index both exclusive i.e.1011 
int y = (x & ((1 << (m-1)) - (1 << (n-1)))) >> (n);
//(1<<(7-1)) - (1<<(2-1)) = 01000000 - 00000010 = 00111100
//x & 00111100 = 10101101 & 00111100 = 00101100 (144 in base 10)
//finally, y = 00101100 >> 2= 00001011 (11 in base 10)

if n==1  then take 0xF and shift the 1's right and take AND
  y=x&(0xF<<(8-(m-n+1))) ;

Useful Links:
http://www.careercup.com/question?id=10537073

No comments:

Post a Comment