> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/high-frequency/single-number-iii.md).

# Single Number III

题目：

Given 2\*n + 2 numbers, every numbers occurs twice except two, find them.

分析：

把2n+2变成2n+1问题,把原来集合分为2个集合。(c-1)\&c 去掉最后一个1的作用，c-(c-1)\&c得到最后1

解法：

```
public List<Integer> singleNumberIII(int[] A) {
        // write your code here
        int xor = 0;
        for(int i = 0; i < A.length; i++){
            xor ^= A[i];
        }
        int lastBit = xor - (xor & (xor - 1));

        int group1 = 0, group2 = 0;
        for(int i = 0; i < A.length; i++){
            if((A[i] & lastBit) == 0){
                group1 ^= A[i];
            }else{
                group2 ^= A[i];
            }
        }
        List<Integer> ret =  new ArrayList<Integer>();
        ret.add(group1);
        ret.add(group2);
        return ret;

    }
```