1、对这n个数,按照从高到低考察各个位上是否为1,方法是通过将第i位的数向右移动32-i个位置到达末位,然后和1相与。最后求和sum[i]。
2、对于只出现一次的数,其二进制位值为0时,无异样,sum[i]必定是k的整数倍,取余结果为0,左移多少位都是0,累加不变;
3、对于只出现一次的数,其二进制位值为1时,sum取余不为0,那么对于这个向右移动了i位才到末位的1,将其向左移动i位就会归位。同时ans每次都会累加,
4、经过32次累加,这个只出现一次的数二进制数位上的1全部归位并累加就成了这个数本身。
int foundOnceNumber(int* arr, int arrLen, int k ) { int sum = 0; int ans = 0; //每次循环对n个数的第i位求和,i从高位开始 for(int i = 0; i < 32; i++){ sum = 0; for(int j = 0; j < arrLen; j++){ //累加第j个数的第i位的值 sum += ( (arr[j]) >> i) & 1; } //把第i位的1归位,并求和 ans += ( (sum % k) << i); } return ans; }