137. Single Number II(#1 ).java

class Solution {
    public int singleNumber(int[] nums) {
        int x1 = 0, x2 = 0, mask = 0;
        
        for (int n : nums) {
            
            x2 = x2 ^ (x1 & n);
            x1 = x1 ^ n;
            mask = ~ (x2 & x1);
            x1 = x1 & mask;
            x2 = x2 & mask;
            
        }
        return x1;
        
    }
}

137. Single Number II(#2 extend to m times and p times).java

/*
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;
        
    }
}

137. Single Number II.java

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;

*/