class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
// solution1:using sort
// vector<int> res;
// sort(nums.begin(),nums.end());
// if(nums.size() == 2 && nums[0] != nums[1]) return nums;
// for(int i = 0; i < nums.size();) {
// if((nums[i] != nums[i + 1])) {
// res.push_back(nums[i]);
// i ++;
// }
// else i = i + 2;
// }
// return res;
//solution2:using bit manipulation
int n = 0;
vector<int> res;
for(int i = 0; i < nums.size(); i++) {
n = n ^ nums[i];
}
/*flag is the last "1" bit of n,the two elements which appear only once must be defferent in this bit
so we can use flag to devide all the elements into two parts,one contains a and the other one contains b.*/
int flag = n & (~(n  1));
int a = 0,b = 0;
for(int i = 0; i < nums.size(); i ++) {
if((flag&nums[i]) == 0) a ^= nums[i];
else b ^= nums[i];
}
res.push_back(a);
res.push_back(b);
return res;
}
};
Share my c++ solutions using bit manipulation and sort with explanations.


I implemented the same idea, but I don't know: what mean the sign '~'.
As I understand it means all bits turned, isn't it?class Solution { public: vector<int> singleNumber(vector<int>& nums) { int pre = 0; for (auto& num : nums) { pre ^= num; } int div = 1; while ((div & pre) == 0) { div = div << 1; } vector<int> answ(2); for (auto& num : nums) { (num & div) ? (answ[0] ^= num) : (answ[1] ^= num); } return answ; } };