2008년 04월 16일
2008년 1학기 시스템 프로그래밍 - sum3
sum3.
이 함수는 인자 셋을 받아서 모두 합치는 함수입니다.
여기서 특이한 것은 마지막에 두 인자를 보내 +연산을 하는 함수를 마지막으로 합니다.
즉, + 연산자를 쓰지 않고 마지막에 +를 하는 어떤 변수 두 개를 만들면
최종적으로 제대로 된 답이 나온다는 뜻이지요.
사실 다른 함수의 경우 어떻게 해야할지 그 길이 바로 보였습니다.
(다만 중간에 그 길이 조금 틀렸다는 것을 알고서 계속 수정하였지만...)
하지만 이 함수는 처음부터 어떻게 해야할지 모르겠더군요.
한참을 고민하다가
문득 덧셈 연산은 그 자리에 내려오는 것과 carry의 합이라는 것을 알았습니다.
사실 아주 당연한 것이지만.....;;;;;
따라서 세 변수에 맞춰 진리표를 만들어보았습니다.
그리고 carry를 왼쪽으로 1 shift하여 둘을 더하도록 하였습니다.
그러자 값이 제대로 나오더군요.^^
처음에는 진리표에서 나온 최소항(minterm)으로 적었습니다만,
연산자의 수가 너무 많아 어떻게 줄여야 하나 고민한 끝에
XOR로 간단히 묶여진다는 것을 발견하였습니다.
/*
* sum3 - x+y+z using only a single '+'
* Example: sum3(3, 4, 5) = 12
* Legal ops: ! ~ & ^ | << >>
* Max ops: 16
* Rating: 3
*/
/* A helper routine to perform the addition. Don't change this code */
static int sum(int x, int y) {
return x+y;
}
int sum3(int x, int y, int z) {
int word1 = 0;
int word2 = 0;
/**************************************************************
Fill in code below that computes values for word1 and word2
without using any '+' operations
***************************************************************/
/**************************************************************
Don't change anything below here
***************************************************************/
/* I make true table.
* x y z sum carry
* 0 0 0 0 0
* 0 0 1 1 0
* 0 1 0 1 0
* 0 1 1 0 1
* 1 0 0 1 0
* 1 0 1 0 1
* 1 1 0 0 1
* 1 1 1 1 1
*
* So sum is x'y'z + x'yz' + xy'z' + xyz
* => x'(y'z + yz') + x(y'z' + yz)
* => x'(y^z) + x((y^z)')
* (because a^b == ~a&b | a&~b)
* and carry is yz + xy + xz
*
* carry is add with front of bit.
* so word1 is sum, word2 is carry doing shift to left 1
* then sum(word1, word2) is added two variable
*
* 20080404 | 20080405 | 20080406
*/
word1 = (~x & (y ^ z)) | (x & ~(y ^ z)); // sum
word2 = ((y & z) | (x & y) | (x & z)) << 1; // carry
return sum(word1,word2);
}
# by | 2008/04/16 12:31 | in Lesson | 트랙백 | 핑백(1) | 덧글(1)
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
... 시스템 프로그래밍 - bitParity' '2008년 1학기 시스템 프로그래밍 - isEqual' '2008년 1학기 시스템 프로그래밍 - isNonZero' '2008년 1학기 시스템 프로그래밍 - sum3' '2008년 1학기 시스템 프로그래밍 - bitCount' '2008년 1학기 시스템 프로그래밍 - sm2tc' 대략 일주일 정도 걸린 과제 ... more
word1 = x ^ y ^ z;
문제를 풀 때는 16개 안으로 줄어들어 더 이상 생각을 하지 않았습니다만,
다시 살펴보니 더 줄일 수 있었네요.OTL....