> Java > java지도 시간 > 본문

세 번째 변수를 사용하지 않고 두 변수의 값을 바꾸는 네 가지 방법

巴扎黑
풀어 주다: 2017-06-26 09:19:29
원래의
2093명이 탐색했습니다.
일반적으로 우리가 하는 일은(특히 학습 단계에서) 새로운 변수를 정의하고 이를 사용하여 교환을 완료하는 것입니다. 코드는 다음과 같습니다.
int a,b;
a=10; b=15;int t;
t=a; a=b; b=t;
로그인 후 복사

이 알고리즘은 이해하기 쉽고 특히 초보자가 컴퓨터 프로그램의 특성을 이해하는 데 적합합니다. 할당문의 고전적인 응용입니다. 실제 소프트웨어 개발에서 이 알고리즘은 간단하고 명확하며 모호성을 유발하지 않으며 프로그래머 간의 의사소통을 용이하게 합니다. 일반적인 상황에서는 변수 값을 교환하는 문제가 발생할 때 이 알고리즘(이하 표준 알고리즘이라고 함)을 사용해야 합니다.


위 알고리즘의 가장 큰 단점은 임시 변수를 사용해야 한다는 것입니다. 그렇다면 임시변수의 도움 없이 교환이 이루어질 수 있을까? 대답은 그렇습니다! 여기서는 1) 산술 연산, 2) 포인터 주소 연산, 4) 스택 구현을 위해 세 가지 알고리즘을 사용할 수 있습니다.

1) 산술 연산
int a,b;
a=10;b=12;
a=b-a; //a=2;b=12b=b-a; //a=2;b=10a=b+a; //a=10;b=10
로그인 후 복사

원리는: a와 b를 숫자 축의 점으로 취급하고 두 점 사이의 거리를 기준으로 계산합니다.

구체적인 과정: 첫 번째 문장 "a=b-a"는 두 점 ab 사이의 거리를 찾아 a에 저장합니다. 두 번째 문장 "b=b-a"는 a에서 원점까지의 거리(b 사이의 거리)를 찾습니다. 세 번째 문장 "a=b+a"는 b에서 원점까지의 거리(a에서 원점까지의 거리와 ab) 사이의 거리를 구합니다. 두 점 사이의 거리 ab)를 a에 저장합니다. 교환을 완료하세요.
표준 알고리즘에 비해 이 알고리즘은 계산 과정이 3개 더 있지만 임시 변수를 사용하지 않습니다. (이하 산술 알고리즘이라 함)
단점: 숫자형에만 사용할 수 있고 문자열 등에는 사용할 수 없습니다. a+b는 오버플로될 수 있습니다(int 범위를 벗어남). 오버플로는 상대적입니다. +가 오버플로되면 -가 다시 오면 괜찮습니다. 따라서 오버플로 여부는 중요하지 않습니다.

2) 포인터 주소 연산
주소 연산은 실제로 정수 연산을 수행하기 때문입니다. 예를 들어 두 개의 주소를 빼서 정수를 얻습니다. 이는 메모리에서 두 변수의 저장 위치를 ​​몇 바이트만큼 분리하는지를 나타냅니다. 즉, "a+10"은 a를 기본 주소로 하여 a 뒤의 10개 클래스 a 데이터 단위의 주소를 나타냅니다. 따라서 이론적으로는 산술 알고리즘과 유사한 연산을 통해 주소 교환을 완료함으로써 변수 교환 목적을 달성할 수 있다. 즉,
int *a,*b; //假设*a=new int(10);*b=new int(20); //&a=0x00001000h,&b=0x00001200ha=(int*)(b-a); //&a=0x00000200h,&b=0x00001200hb=(int*)(b-a); //&a=0x00000200h,&b=0x00001000ha=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h
로그인 후 복사

위 연산을 통해 a와 b의 주소가 실제로 교환되었고, a는 원래 b가 가리키는 값을 가리키고, b는 원래 a가 가리키는 값을 가리키는 걸까요? 위의 코드는 컴파일 가능하지만 실행 결과는 놀랍습니다! 왜?

먼저 운영체제는 메모리를 시스템 코드/데이터 영역, 애플리케이션 코드/데이터 영역, 스택 영역, 글로벌 데이터 영역 등 여러 영역으로 나눈다는 점을 이해해야 합니다. 소스 프로그램을 컴파일할 때 상수, 글로벌 변수 등은 글로벌 데이터 영역에 배치되고, 로컬 변수와 동적 변수는 스택 영역에 배치됩니다. 이렇게 "a=(int*)(b-a)"로 알고리즘을 실행하면 a의 값은 0x00000200h가 아니고, 변수 a가 위치한 메모리 영역의 기본 주소는 0x008f0200h가 됩니다. , 여기서 0x008f는 기본 주소 0200은 메모리 영역에서 a의 변위입니다. 컴파일러에 의해 자동으로 추가됩니다. 결과적으로 향후 주소 계산이 정확하지 않아 a와 b가 해당 영역의 다른 메모리 장치를 가리키게 됩니다. 셋째, 주소 연산에는 음수가 나타날 수 없습니다. 즉, a의 주소가 b의 주소보다 큰 경우(b-a해결책이 있나요? 틀림없이! 개선된 알고리즘은 다음과 같습니다.
if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff));
a=(int*)(b+(int(a)&0x0000ffff));
}else{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}
로그인 후 복사

알고리즘의 가장 큰 개선점은 비트 연산에서 AND 연산 "int(a)&0x0000ffff"를 사용한 점입니다. 주소의 상위 16비트가 세그먼트 주소이고, 마지막 16비트는 변위 주소입니다. 0x0000ffff로 AND를 하면 세그먼트 주소가 마스크되고 변위 주소만 유지됩니다. 이는 원래 알고리즘과 일치하며 올바른 결과를 얻습니다.

이 알고리즘도 제3의 변수를 사용하지 않고 값 교환을 완료합니다. 산술 알고리즘에 비해 이해하기 어렵지만, 큰 데이터 유형을 교환할 때 산술 알고리즘보다 실행 속도가 빠르다는 장점이 있습니다. 주소를 교환하기 때문에 변수값은 메모리에서 이동되지 않습니다. (이하 주소 알고리즘이라고 함)

3) 비트 연산
int a=10,b=12; //a=1010^b=1100;a=a^b; //a=0110^b=1100;b=a^b; //a=0110^b=1010;a=a^b; //a=1100=12;b=1010;
로그인 후 복사

이 알고리즘의 구현은 XOR 연산의 특성에 따라 결정됩니다. XOR 연산을 통해 데이터의 일부 비트가 반전될 수 있습니다. 다른 비트는 변경되지 않습니다. 이는 임의의 숫자와 주어진 값이 연속으로 두 번 XOR되고 값은 변경되지 않음을 의미합니다.

4) 스택 구현. 더 이상 설명이 필요하지 않으며 스택 및 관련 함수 정의는 생략됩니다.
int exchange(int x,int y) 
{ 
     stack S; 
     push(S,x); 
     push(S,y); 
     x=pop(S); 
     y=pop(S); 
}
로그인 후 복사

위 알고리즘은 모두 다른 변수의 도움 없이 두 변수 값의 교환을 구현합니다. 이에 비해 산술 알고리즘과 비트 산술은 동일한 계산량을 가지고 있으며, 주소 알고리즘의 계산은 더 복잡합니다. 그러나 대규모 계산은 쉽게 수행할 수 있지만 유형(예: 사용자 정의 클래스 또는 구조)은 정수 데이터만 교환할 수 있습니다(이론적으로 "^" 연산자를 오버로드하면 모든 구조의 교환이 가능함). ).

이 세 가지 알고리즘을 소개하는 것은 실제로 적용하기 위한 것이 아니라 기술에 대해 논의하고 프로그래밍의 매력을 보여주기 위한 것입니다. 이를 통해 알 수 있듯이 수학의 작은 능력이 프로그래밍에 상당한 영향을 미치고, 적절히 사용하면 예상치 못한 마법 같은 효과를 낳게 된다는 것을 알 수 있다. 실제 소프트웨어 개발의 관점에서 볼 때 표준 알고리즘은 의심할 여지 없이 최고이며 모든 유형의 교환 문제를 해결할 수 있습니다.

위 내용은 세 번째 변수를 사용하지 않고 두 변수의 값을 바꾸는 네 가지 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!