2008년 04월 16일
2008년 1학기 시스템 프로그래밍 - bitMask
bitMask.
이 함수는 두 개의 값을 인자로 받아 그 사이에 1을 나머지는 0을 넣는 함수입니다.
이 함수가 저를 제일 머리 아프게 했습니다.
왜냐하면 연산자 수를 16개 이하로 맞추기 위해서였습니다.
처음에는 왼쪽을 1로 하여 1을 만드는 코드를 만들었습니다만,
연산자가 너무 많아져서 골치가 아팠습니다.
그러다 같은 수업을 듣는 친구에게서 조언을 얻었습니다.
방법은 다음과 같습니다.
MSB를 0으로 하고 나머지를 1로 만듭니다.
그런 후 오른쪽으로 shift하여 1의 수를 하나 적게 만듭니다.
그리고 다시 왼쪽으로 shift하여 highbit - 1까지 옮깁니다.
마지막으로 highbit에 1을 채웁니다.
최종적으로 sign bit를 AND하여
highbit와 lowbit가 반대로 들어올 경우 0을 반환하도록 하였습니다.
/*
* bitMask - Generate a mask consisting of all 1's
* lowbit and highbit
* Examples: bitMask(5,3) = 0x38
* Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
* If lowbit > highbit, then mask should be all 0's
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int bitMask(int highbit, int lowbit) {
/* 0x01 to shift left 32 then it's 0x80000000
* shift to right by interval+1. MSB is 1 so it makes 1's sequence.
* If highbit is 31, then shift to right by interval size. because MSB is not changed.
*
* If MSB is 31 then don't changed MSB. other condition is changed.
*
* if highbit is larger than 29(ex: 30, 31), don't move.
* Other condition is moved to right by 32 - (interval + 1) - (lowbit + 1)
*
* if lowbit > highbit then return 0
*
* 20080403 | 20080405
*
* I made the code but it's too many operators.(34)
* So I changed mind.
* Last code is start 0x80000000.
* and make it use right shift(Arithmetic) to make 1 bits.
* Now I use 0x7fffffff.
* and make it use right shift to remove 1 bits.
* and left shift to fit the location.
* last I set 1 on high bit location.
* Therefore I reduced operations.
*
* 20080406 | 20080407
*/
/*
int interval = highbit + (~lowbit + 1); // length 1 bits.
int x = ((1 << 31) >> (interval + (!!(31 + (~highbit + 1))))); // make 1bits by interval +1, if highbit is 31 then makes interval
x &= (1 << highbit) | (~0 ^ (1 << 31)); // make MSB to 0 if highbit 31 then MSB is 1
x = x >> ((~0 + !((1 << 29) >> highbit)) & (30 + (~(interval + lowbit) + 1))); // move 1 bits, if highbit lower than 30
x &= (~(highbit + (~lowbit + 1)) >> 31); // if lowbit > highbit then MSB of ~(highbit - lowbit) is 0, so It makes x is 0.
return x; // return x
*/
int interval = highbit + (~lowbit + 1); // length 1 bits.
int work_space_32bits = ~0 ^ (1 << 31); // return value. initialize 0x7fffffff
work_space_32bits = work_space_32bits >> ((32 + ~interval)); // make 1 bit by interval. 31 + (~interval + 1) == 31 - interval. Therefore it make 1bits. but it is one less. ex) highbit : 5, lowbit : 3, interval : 2. So it make two 1bits. but we want three 1bit.
work_space_32bits = work_space_32bits << lowbit; // move to left by lowbit. ex) 0000 0111 -> 0011 1000 : if lowbit is 3.
work_space_32bits |= (1 << highbit); // above to make 1bits. we want one more bits. That location is highbit. so I add this sentence to make 1 bit at highbit.
work_space_32bits &= ~interval >> 31; // if lowbit > highbit then MSB of ~(highbit - lowbit) is 0, so It makes x is 0.
return work_space_32bits; // return result.
}
# by | 2008/04/16 12:30 | in Lesson | 트랙백 | 핑백(1) | 덧글(0)
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
... 시스템 프로그래밍 - multFiveEights' '2008년 1학기 시스템 프로그래밍 - satAdd' '2008년 1학기 시스템 프로그래밍 - tc2sm' '2008년 1학기 시스템 프로그래밍 - bitMask' '2008년 1학기 시스템 프로그래밍 - bitParity' '2008년 1학기 시스템 프로그래밍 - isEqual' '2008년 1학기 시스템 프로그 ... more