public class Solution {
public int singleNumber(int[] nums) {
int one = 0;
int two = 0;
int mask = 0;
for(int num : nums){
two ^= num & one;
//two |= num & one;
one ^= num;
mask = ~ (one & two);
one &= mask;
two &= mask;
}
return one;
}
}
/*
00 => 01 => 10 => 00
[7, 7, 7, 3]
one 0 0 0
two 0 0 0
first 7:
one 1 1 1
two 0 0 0
second 7:
one 0 0 0
two 1 1 1
third 7:
one 0 0 0
two 0 0 0
first 3:
one 0 1 1
two 0 0 0
return 3
extend to five times
000 => 001 => 010 => 011 => 100 => 000
[7, 7, 7, 7, 7, 3]
three ^= num & one & two;
two ^= num & one;
one ^= num;
mask = ~ (one & ~two & three); //when == 101, go back to 000
one &= mask;
two &= mask;
three &= mask;
*/
/*
There are many numbers appearing m times, and only one number appearing p times. Find the number that appears p times.
https://discuss.leetcode.com/topic/11877/detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers
xm, xm-1, xm-2, ... x1;
xm = xm ^ (xm-1 & xm-2 & ... & x1 & num)
x1 = x1 ^ num
mask = ~ (x1 & ) // according to k
x1 &= mask;
*/
class Solution {
public int singleNumber(int[] nums) {
int x1 = 0, x2 = 0, x3 = 0, mask = 0;
for (int n : nums) {
x3 = x3 ^ (x2 & x1 & n);
x2 = x2 ^ (x1 & n);
x1 = x1 ^ n;
mask = ~ (~x1 & ~x2 & x3);
x1 = x1 & mask;
x2 = x2 & mask;
x3 = x3 & mask;
}
return x2;
}
}