137. Single Number II (Bit)
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路：用变量分别存储出现一次、两次、三次的number
出现一次的number: 抑或操作去除了出现两次的可能，与未出现三次的number作“与操作”去除了出现三次的可能
出现两次的number:与出现一次的number作“与操作”
出现三次的number: 出现一次的number“与操作”出现两次的number
class Solution { public: int singleNumber(int A[], int n) { int once = 0; int twice = 0; for (int i = 0; i < n; i++) { twice |= once & A[i]; //将出现两次1的位，在twice中置1 once ^= A[i]; //将出现一次1的位，在once中置1，出现两次则置0 int not_three = ~(once & twice); //将出现三次1的位，在not_tree中置0 once = not_three & once; //将出现三次1的位，在once中置0 twice = not_three & twice; //将出现三次1的位，在twice中置0 } return once; } };