자바 의 특이 하거나 깊이 있 는 설명
이 또는 이 진 을 기반 으로 하 는 비트 연산 은 기호 XOR 또는^로 그 연산 법칙 은 연산 자 양쪽 수의 모든 이 진 비트,같은 값 은 0,다른 값 은 1 을 취한 다.
성질
1.교환 율
2.결합 율(즉(a^b)^c==a^(b^c))
3.모든 수 x 에 대해 x^x=0,x^0=x 가 있 습 니 다.
4.자 반성 A XOR B XOR B=A XOR 0=A
이 또는 연산 은 다항식 나눗셈 에서 가장 흔히 볼 수 있 지만 가장 중요 한 성질 은 역시 자 반성 이다.A XOR B XOR B=A,즉 주어진 수 A 에 대해 같은 연산 인자(B)로 두 번 의 이 또는 연산 을 한 후에 도 A 자 체 를 얻는다.이것 은 신기 한 성질 로 이 성질 을 이용 하면 많은 재 미 있 는 응용 을 얻 을 수 있다.예 를 들 어 모든 프로그램 교과 서 는 초보 자 에 게 두 변수의 값 을 교환 하려 면 중간 변 수 를 도입 해 야 한다 고 지적 했다.그러나 다른 변 수 를 사용 하면 하나의 변수의 저장 공간 을 절약 할 수 있 습 니 다.A,B 두 개의 변수 가 있 고 저 장 된 값 은 각각 a,b 이 며 다음 세 줄 표현 식 은 그들의 값 표현 식(값)을 바 꿀 것 입 니 다.
A=A XOR B (a XOR b)
B=B XOR A (b XOR a XOR b = a)
A=A XOR B (a XOR b XOR a = b)
예:
int a = 10, b = 5
a = a ^ b;
b = a ^ b;
a = a ^ b;
이와 유사 하 게 이 연산 은 암호 화,데이터 전송,검사 등 여러 분야 에 도 응용 할 수 있다.응용 예:1-1000 은 1001 개의 요 소 를 포함 한 배열 에 놓 여 있 고 유일한 요소 값 만 중복 되 며 다른 것 은 모두 한 번 만 나타 납 니 다.각 배열 요 소 는 한 번 만 접근 할 수 있 고 알고리즘 을 설계 하여 찾 을 수 있 습 니 다.보조 저장 공간 을 사용 하지 않 고 알고리즘 을 설계 하여 실현 할 수 있 습 니까?
해법 1.분명히 누군가가 비교적 멋 진 해법 을 제시 했다.모든 수 를 합치 면 1+2+...+1000 의 합 을 뺀 것 이다.이 알고리즘 은 이미 충분히 완벽 하 다.출제 자의 표준 답안 이 바로 이 알고리즘 이 라 고 믿는다.유일한 문 제 는 수열 이 너무 크 면 넘 칠 수 있다 는 것 이다.
해법 2.이상 하거나 이 문제 가 없 으 며 성능 이 더 좋다.모든 수 를 다 바 꾸 거나 얻 은 결 과 를 1^2^3^...^1000 의 결과 와 다 르 게 하거나 얻 은 결 과 는 중복 수 입 니 다.
그러나 이 알고리즘 은 간단 하지만 쉬 운 일이 아니 라 는 것 을 증명 한다.이것 은 이 또는 연산 의 몇 가지 특성 과 관계 가 있다.우선 이 또는 연산 이 교환 율,결합 율 을 만족시킨다.
그래서 1^2^...^n^...^n^...^1000,이 두 n 이 어느 위치 에 나타 나 든 지 간 에 1^2^...^1000^(n^n)의 형식 으로 전환 할 수 있 습 니 다.
그 다음으로 모든 수 x 에 대해 x^x=0,x^0=x 가 있 습 니 다.
그래서 1^2^...^n^...^n^...^1000=1^2^...^1000^(n^n)=1^2^...^1000^0=1^2^...^1000(즉 서열 에서 n 을 제외 한 모든 수의 차이 나).
령,1^2^...^1000(시퀀스 에 n 포함 되 지 않 음)의 결 과 는 T 입 니 다.
1^2^...^1000(서열 에 n 포함)의 결 과 는 T^n 입 니 다.
T^(T^n)=n。
따라서 모든 수 를 다 바 꾸 거나 얻 은 결 과 를 1^2^3^...^1000 의 결과 와 다 르 게 하거나 얻 은 결 과 는 중복 수 입 니 다.
물론 1+2+...+1000 의 결 과 는 고 스 법칙 으로 빠르게 계산 할 수 있 지만 실제로 1^2^..^1000 의 결과 도 규칙 적 이 고 알고리즘 은 고 스 법칙 보다 훨씬 간단 하 다.
구 글 면접 문제 의 변형:한 배열 에 몇 개의 정 수 를 저장 하고 한 수 에 홀수 가 나타 나 며 나머지 수 는 모두 짝수 가 나타 납 니 다.이 홀수 가 나타 나 는 수 를 찾 아 보 시 겠 습 니까?
public void fun() {
int a[] = { 22, 38,38, 22,22, 4, 4, 11, 11 };
int temp = 0;
for (int i = 0; i < a.length; i++) {
temp ^= a[i];
}
System.out.println(temp);
}
해법 은 많 지만 가장 좋 은 것 은 위 와 마찬가지 로 모든 수 를 다 르 게 하거나 마지막 결 과 는 찾 는 것 입 니 다.원 리 는 같 습 니 다!!**************************************************************************************************************************
이렇게 하면 사람의 세 번 째 변 수 를 끌 어 들 이지 않 고 교환 을 실현 할 수 있 지만 계산 은 세 번 째 변수 에 비해 많 기 때문에 효율 이 낮 을 것 이다.
다른 방법 에 대해 서 는 int a=5,b=10;
a=a+b; //a=15,b=10
b=a-b; //a=15,b=5
a=a-b; //a=10,b=5
그러나 이렇게 하 는 데 결함 이 있 습 니 다.만약 에 vc6 환경 에서 실행 된다 고 가정 하면 int 의 크기 는 4 Bytes 이기 때문에 int 변수 가 저장 하 는 최대 치 는 2^31-1 즉 2147483647 입 니 다.만약 에 우리 가 a 의 값 을 214748300,b 의 값 이 100000000 이 라면 a 와 b 를 더 하면 경 계 를 넘 습 니 다.
사실은 실제 운행 통 계 를 보면 우 리 는 교환 해 야 할 두 변 수 는 같은 번호 의 확률 이 매우 크다 는 것 을 알 게 되 었 다.그리고 그들 사이 가 서로 줄 어 들 고 경 계 를 넘 는 상황 도 매우 적 기 때문에 우 리 는 위의 가감 법 을 교환 할 수 있다.그러면 프로그램 이 잘못 될 확률 이 줄어든다.
int a=5,b=10;
a -= b; //a=-5,b=10
b += a; //b=5,a=-5
a = b - a; //a=10,b=5
이상 의 연산 을 통 해 a 와 b 의 값 을 교환 하 였 다.겉 으로 는 간단 해 보이 지만 생각 하기 쉽 지 않다.특히 세 번 째 변 수 를 습관 적 으로 도입 한 알고리즘 이후 다.
그것 의 원 리 는 a,b 를 수축 의 점 으로 보고 두 점 사이 의 거 리 를 둘러싸 고 계산 하 는 것 이다.
구체 적 인 과정:첫 번 째 문장 인'a-=b'는 ab 두 점 의 거 리 를 구하 고 이 를 a 에 저장한다.두 번 째 문장 인'b+=a'는 a 에서 원점 까지 의 거리(b 에서 원점 까지 의 거리 와 ab 두 점 의 거리 차이)를 구하 고 이 를 b 에 저장한다.세 번 째 문장 인'a+=b'는 b 에서 원점 까지 의 거리(a 에서 원점 까지 의 거리 와 ab 두 점 의 거리의 합)를 구하 고 이 를 a 에 저장한다.교환 완료.
다음은 두 개의 수 를 교환 하 는 세 가지 방법 을 소개 한다.
총결산
이상 은 이 글 의 모든 내용 입 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가 치 를 가지 기 를 바 랍 니 다.여러분 의 저희 에 대한 지지 에 감 사 드 립 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.