// ConsoleApplication46.cpp : 定义控制台应用程序的入口点。 //统计出现一次的数字（其它数字只出现两次） #include "stdafx.h" #include #include #include using namespace std; unsigned int FirstBitIs1(int num){ if (num<0 || num>0xffff){ cout <<"beyond range" << endl; return INFINITY; } int k = 0; for (; num % 2 == 0; num /= 2){ k++; } return k; } //unsigned int FirstBitIs1(int num){ // int index = 0; // while (((num & 1)== 0) && index < 8 * sizeof(int)){ // num = num >> 1; // index++; // } // return index; //} //bool Is1(int num, unsigned int bit){ // int s = pow(2, bit); // return num & s; //} bool Is1(int num, unsigned int bit){ num = num >> bit; return (num & 1); } void FindNumsAppearOnce(int data[], int length,int *num1,int *num2){ int i,s=0; unsigned int j; if (data == NULL && length < 2){ return; } for (i = 0; i < length; i++){ s ^= data[i]; } j = FirstBitIs1(s); *num1 = 0; *num2 = 0; for (i = 0; i < length; i++){ if (Is1(data[i], j) == 1){ (*num1) ^= data[i]; } else{ (*num2) ^= data[i]; } } } // ====================测试代码==================== void Test(char* testName, int data[], int length, int expected1, int expected2) { if (testName != NULL) printf("%s begins: ", testName); int result1, result2; FindNumsAppearOnce(data, length, &result1, &result2); if ((expected1 == result1 && expected2 == result2) || (expected2 == result1 && expected1 == result2)) printf("Passed.\n\n"); else printf("Failed.\n\n"); } void Test1() { int data[] = { 2, 4, 3, 6, 3, 2, 5, 5 }; Test("Test1", data, sizeof(data) / sizeof(int), 4, 6); } void Test2() { int data[] = { 4, 6 }; Test("Test2", data, sizeof(data) / sizeof(int), 4, 6); } void Test3() { int data[] = { 4, 6, 1, 1, 1, 1 }; Test("Test3", data, sizeof(data) / sizeof(int), 4, 6); } int _tmain(int argc, _TCHAR* argv[]) { Test1(); Test2(); Test3(); /*cout < << endl; cout < << endl;*/ system("pause"); return 0; } 题目原意是在数字序列中找出其中只出现一次的数字，而序列中的其他数字出现两次。
可以这样考虑：由于序列中的其它数据出现2次，因此，相同的数字异或运算得到的结果是0，而不同的两数异或得到的二进制结果中某个位上的数字必定为1。异或运算服从交换率，因此，将序列中的数字依次执行异或运算，最后得到的二进制位中最低某位为1，假设该位为m位。很显然，将序列中按第m位为1或0分为2个子序列，出现一次的数字分别位于两个子序列中，两个子序列中的其它数字军出现两次。再次分别将两个子序列中的数字做异或运算，得到的两个结果即为原序列中出现一次的数字。
该方法充分利用异或运算中同一位置二进制数相同为0的性质，出现两次的数字相异的结果为0，最终得出结果。
// ConsoleApplication46.cpp : 定义控制台应用程序的入口点。 //剑指Offer中统计出现一次的数字（其它数字只出现两次） #include "stdafx.h" #include<iostream> #include<string> #include<math.h> using namespace std; unsigned int FirstBitIs1(int num){ if (num<0 || num>0xffff){ cout <<"beyond range" << endl; return INFINITY; } int k = 0; for (; num % 2 == 0; num /= 2){ k++; } return k; } //unsigned int FirstBitIs1(int num){ // int index = 0; // while (((num & 1)== 0) && index < 8 * sizeof(int)){ // num = num >> 1; // index++; // } // return index; //} //bool Is1(int num, unsigned int bit){ // int s = pow(2, bit); // return num & s; //} bool Is1(int num, unsigned int bit){ num = num >> bit; return (num & 1); } void FindNumsAppearOnce(int data[], int length,int *num1,int *num2){ int i,s=0; unsigned int j; if (data == NULL && length < 2){ return; } for (i = 0; i < length; i++){ s ^= data[i]; } j = FirstBitIs1(s); *num1 = 0; *num2 = 0; for (i = 0; i < length; i++){ if (Is1(data[i], j) == 1){ (*num1) ^= data[i]; } else{ (*num2) ^= data[i]; } } } // ====================测试代码==================== void Test(char* testName, int data[], int length, int expected1, int expected2) { if (testName != NULL) printf("%s begins: ", testName); int result1, result2; FindNumsAppearOnce(data, length, &result1, &result2); if ((expected1 == result1 && expected2 == result2) || (expected2 == result1 && expected1 == result2)) printf("Passed.\n\n"); else printf("Failed.\n\n"); } void Test1() { int data[] = { 2, 4, 3, 6, 3, 2, 5, 5 }; Test("Test1", data, sizeof(data) / sizeof(int), 4, 6); } void Test2() { int data[] = { 4, 6 }; Test("Test2", data, sizeof(data) / sizeof(int), 4, 6); } void Test3() { int data[] = { 4, 6, 1, 1, 1, 1 }; Test("Test3", data, sizeof(data) / sizeof(int), 4, 6); } int _tmain(int argc, _TCHAR* argv[]) { Test1(); Test2(); Test3(); /*cout <<FirstBitIs1(8) << endl; cout <<Is1(14,5) << endl;*/ system("pause"); return 0; }
