한 번 만 나타 나 는 숫자 (비트 연산)

하나의 수가 다 르 거나 0 결 과 는 그 자체 이 고, 하나의 수가 다 르 거나 그 자체 의 결 과 는 0 이 며, 이 또는 연산 은 a ^ b ^ c = a ^ (b ^ c) 를 만족 시 킵 니 다.
 
제목 1: 빈 정수 가 아 닌 배열 을 지정 합 니 다. 한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 두 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾 아 라.
사고: 하나의 변수 ret 이 또는 모든 배열 요 소 를 설정 하고 마지막 에 똑 같은 것 은 0 으로 상쇄 합 니 다. 그 유일한 숫자 차이 나 0 은 자신 이 바로 답 입 니 다.
코드 는 다음 과 같 습 니 다:

#include
int main()
{
    int nums[5]={4,1,2,1,2};
    int ret=0,i=0;
    for(i=0;i<5;i++)
        ret^=nums[i];
    printf("%d",ret);
	return 0;
}

제목 2: 빈 정수 가 아 닌 배열 을 지정 하고 두 개의 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 두 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾아내다.
사고: 이 문 제 는 지난 문제 와 다른 것 은 두 가지 요소 가 한 번 만 나 타 났 고 한 가지 요소 가 한 번 나타 난 문 제 를 우리 가 해결 할 수 있다 는 것 이다. 그러면 우 리 는 이 문 제 를 첫 번 째 문제 로 바 꾸 는 방법 을 생각해 야 한다. 우 리 는 이 배열 을 두 개의 배열 로 바 꿀 수 있다. 각 배열 에 한 번 나타 난 요소 가 있 고 그 다음 에 우 리 는 할 수 있다.어 려 운 점 은 두 개의 배열 을 어떻게 바 꾸 느 냐 에 있다.
먼저 배열 을 들 어 라: {2, 3, 4, 1, 2, 4};
먼저 바 이 너 리 를 열거 합 니 다:
2：0010 3：0011    4：0100   1：0001   2：0010   4：0100 
전체 배열 의 이상 또는 결과: 0010;전체 배열 을 다 르 게 하거나 마지막 결 과 는 단독으로 항목 을 낸 두 개의 다 르 거나 최종 결 과 를 발견 하기 어렵 지 않 습 니 다!
최종 이상 또는 결과 (과정 은 열거 되 지 않 음): 0010    그러면 두 번 째 는 1 로 두 개의 단독 출현 수의 두 번 째 가 다르다 는 것 을 의미한다.그러면 우 리 는 이 조건 에 따라 배열 을 나 눌 수 있다.2 위 는 1 조, 2 위 는 0 조 는 1 조.그리고 각 조 가 다 르 거나 얻 은 두 가지 결 과 는 단독으로 나타 난 두 개의 수 입 니 다!(주의: 제 가 예 를 들 면 비교적 간단 합 니 다. 만약 에 최종 적 으로 다 르 거나 결과 가 1 이 많 으 면 우 리 는 첫 번 째 로 나타 난 1 의 위치 에 따라 조 를 나 눕 니 다)
 

#include
#include
 
void FindOnce_Number(int arr[], int sz)
{
	int i = 0;
	int j = 0;
	int num1 = 0;
	int num2 = 0;
 
	int tmp = 0;
 
	for(i = 0; i < sz; i++)
		tmp ^= arr[i];//                    ；
	for(i = 0; i < 32; i++)
	{
		if(((tmp>>i)&1) == 1)
			break;//      1  ，   ；
	}
	for(j = 0; j < sz; j++)
	{
		if(((arr[j]>>i)&1) == 0)// i  0        ；
			num1 ^= arr[j];
		else
			num2 ^= arr[j];//      i  1 ，       ；
	}
	//       num1   num2；
	printf("           ：%d   %d
",num1,num2);
}
 
int main()
{
	int arr[] = {2,3,4,1,2,4};
	int sz = sizeof(arr)/sizeof(arr[0]);//     ，    strlen  
 
	FindOnce_Number(arr,sz);
 
	system("pause");
	return 0;
}

제목 3: 빈 정수 가 아 닌 배열 을 지정 합 니 다. 한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 세 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾아내다.
사고방식: 이것 은 앞의 문제 의 변종 으로 첫 번 째 문제 의 방법 으로 는 통 하지 않 고 자세하게 분석한다.
@ {2, 3, 2, 4, 2, 4, 4} 을 예 로 들 면
2：0010 3：0011 2：0010 4：0100 2：0010 4：0100 4：0100
이렇게 열거 하면 반나절 동안 어떤 특징 이 있 는 지 알 수 없 을 것 이다. 그러면 이렇게 열거 할 까?
2：0010 2：0010 2：0010 4：0100 4：0100 4：0100 3：0011
이렇게 열거 하면 3 이 없 으 면 세 번 나 오 는 수의 2 진법 에서 1 이 3 으로 나 누 어 지 는 것 을 알 수 있다. 그러면 3 을 넣 으 면 원래 의 균형 이 깨 지 는 것 이 아니 냐 는 것 이다. 한 사람 당 1 이 나 오 면 3 으로 나 오지 못 하 는 자 리 를 찾 으 면 한 번 만 나 오 는 이 자 리 는 1 이 고, 다른 한 사람 이 한 번 만 나 오 면...그것 은 틀림없이 단독으로 세 는 1 이다.그렇다면 결국 결 과 를 얻 을 수 있 을 것 이다.
언어 서술 이 잘 모 르 겠 습 니 다. 코드 를 구체 적 으로 보 세 요.

#include
#include
#include

//              1   ，        ，             ！   ！
int FindOnce_Number(int arr[], int sz)
{
    int bit[32];
    int i = 0;
    int j = 0;
    int num = 0;
    memset(bit,0,32*sizeof(int));//     ，      ，   ,      bit   0；
    for(i =  0; i < sz; i++)
    {
        for(j = 0; j < 32; j++)
        {
            bit[j] += ((arr[i]>>j)&1);
        }
    }
    
    for(j = 0; j < 32; j++)//32          32    
    {
        if(bit[j]%3 != 0)
        {
            num |= (1< %d
",num);
    system("pause");
    return 0;
}