알고리즘 서론 Ch2.1 - 4 연습 문제

제목: 각각 배열 A 와 B 에 저 장 된 n 비트 바 이 너 리 정수 가 두 개 있 는데 이들 의 추가 문 제 를 고려 합 니 다.두 개의 정수 와 이 진 형식 으로 (n + 1) 개의 요 소 를 가 진 배열 C 에 저장 합 니 다.이 문제 의 형식 화 된 설명 을 하고 위조 코드 를 쓰 십시오.
분석: 이 진 정수 의 인 코딩 은 여기 서 원 코드 와 패 치 를 고려 하고 원 코드 는 패 치 로 전환 하여 연산 할 수 있 으 며 이것 은 패 치가 연산 에서 의 장점 을 나타 낸다.
실질 적 으로 아 날로 그 컴퓨터 바 이 너 리 패 치 의 덧셈 이다.
컴퓨터 에 서 는 패 치 로 덧셈 연산 을 하고 저장 장치 와 연산 레지스터 의 수 를 모두 패 치 로 표시 하 며 데이터 연산 결과 도 패 치 로 표시 한다.
    정점 소수 부호 덧셈 의 연산 공식 은
              [x] 보 + [y] 보 = [x + y] 보     (mod 2)
    정점 정수 까지 보급 한 후에 정점 정수 부호 덧셈 의 연산 공식 은 다음 과 같다.
              [x] 보 + [y] 보 = [x + y] 보     (mod 2n+1)     
    이 공식 을 간단하게 증명 한다.
    패 치 의 정의 에 따 르 면: [x] 패 치 = 2n-x      (n 은 글자 길이 - 1)
    그럼, [x] 보 + [y] 보 =  2n-x + 2n-y = 2n+1 –(x+y)  = [x + y] 보충     (mod 2n+1)
   간단하게 언어 로 설명 합 니 다. 코드 를 추가 할 기호 위 치 를 연산 에 가 져 옵 니 다. 위치 에 따라 대응 하고 위치 가 있 으 면 들 어 갑 니 다. 기호 위치의 진 위 를 버 립 니 다 (진 위 를 가지 고 있다 면).
코드 가 간단 해 요.

void sum(int* a, int* b, int len, int* c)
{
	int carry = 0;
	int temp, i;
	for(i=len-1; i>=0; i--)
	{
		temp = a[i] + b[i] + carry;
		if(temp >= 2)
		{
			carry = 1;
			c[i+1] = temp - 2;
		}
		else
		{
			carry = 0;
			c[i+1] = temp;
		}
	}
	c[0] = (a[0] + b[0] + carry) % 2;
}

설명:
1. 보충 코드 의 실질.
시 계 를 예 로 들 면 3 시 는 시계 가 12 시 방향 에서 시계 방향 으로 90 도 를 돌 고 12 시 방향 에서 시계 방향 으로 270 도 를 돌 리 는 것 을 나 타 낼 수 있다.
즉 3 = 0 + 3, 그리고 3 = 12 - 9 이다. 그러면 0 - 12 의 임 의 숫자 는 모두 두 가지 표현 방식 이 있다. x 와 12 - (12 - x).
바 이 너 리 에 대응 하 는 패 치 입 니 다. 시계 와 같은 점 은 값 이 넘 치면 순환 이 생 긴 다 는 것 입 니 다. 12 시 이후 에는 1 시 로 돌아 가 반복 되 며, 최대 양수 가 넘 치면 마이너스 가 됩 니 다.
2 、 왜 패 치 를 사용 합 니까
기 호 를 연산 에 가 져 와 서 감법 을 덧셈 으로 바 꿀 수 있다.
컴퓨터 내 부 는 덧셈 기 만 있 고 뺄셈 기 가 없 으 며 덧셈 기 는 간단 한 것 과 비 문 으로 조합 할 수 있 으 며 뺄셈 기의 제작 라인 이 복잡 하기 때문에 덧셈 을 사용 하여 뺄셈 을 대체 하 는 것 이 필요 하 다.