수조에서 한 번만 나오는 수를 찾아내다

이 제목은 세 가지 변형이 있다.
첫 번째, 하나의 수조에서 모든 수가 두 번 나타났고, 단지 한 수만 한 번 나타났으니, 이 수를 구하자.이 문제는 비교적 간단해서 숫자 간의 차이나 특성만 알면 쉽게 답을 얻을 수 있다.

int find_num_appear_once(int *data, int length){

    if(data==NULL || length==0)return;

    int i=0;

    int res=0;

    for(;i<length;i++){

        res ^= data[i];

    }

    return res;

}

두 번째는 한 수조에 있는 모든 수가 두 번 나타나고 두 개만 한 번 나타나면 이 두 수를 구한다.이 문제는 비교적 어려워서 미지의 문제를 이미 알고 있는 문제로 전환시켜야 한다.먼저 모든 수를 전부 다르게 하거나 한 수를 얻는다. 이 수는 답안의 두 개의 수가 다르거나 다른 결과이기 때문에 반드시 0이 아니다. 그러면 그것을 2진수로 바꿀 때 반드시 한 사람이 1이다.이 수의 2진수 중 첫 번째가 1인 그 사람을 통해 수조의 수를 두 부분으로 나누면 이 두 부분은 문제 1리의 상황이다. 각각 문제 1의 방법으로 답을 찾아낸다.

int *find_num_appear_once(int *data, int length){

    if(data==NULL || length<2)return;

    int i=0;

    int j=0;

    int temp=0;

    int res[2]={0};

    for(;i<length;i++){

        temp ^= data[i];

    }

    unsigned int index=find_first_index(res);

    for(;j<length;j++){

        if(is_bit_one(index, data[j])){

            res[0] ^= data[j];

        }else{

            res[1] ^= data[j];

        }

    }

    return res;

}



unsigned int find_first_index(int num){// 1 

    int index_bit=0;

    while((num&1)==0 && index_bit<32){

        num>>1;

        index_bit++;

    }

    return index_bit;

}



bool is_bit_one(unsigned int num1, int num2){// num1 1

    int num = num2>>num1;

    return (num&1);

}

세 번째, 한 수조에 있는 모든 수는 세 번 나타났고, 한 수만 한 번 나타났으니, 이 수를 구하자.이 문제의 해결 방법은 이 수조에서 숫자의 한 자리를 더하고 3과 나머지를 얻는 것이다. 이렇게 하면 이 나머지가 1이 아니면 0이다.다시 이 여수를 상응하는 위치에 놓아라. (수조 중수의 몇 위를 통해 얻은 여수는 몇 위에 놓아라.) 그러면 그 단일한 수를 재구성할 수 있다.

int *find_num_appear_once(int *data, int length){

    if(data==NULL || length==0)return;

    int i=0;

    int j=0;

    int res=0;

    int num=0;

    for(;i<32;i++){

        num=0;

        for(j=0;j<length;j++){

            num += (data[j]>>i)&1;// ，num 1

        }

        res |= (num%3)<<i;

    }

    return res;

}