# Leetcode Single Number Ii

2020-12-29

https://leetcode-cn.com/problems/single-number-ii/

single-number 利用了异或的特性:

0 ^ a => a
0 ^ a ^ a => 0


0 @ a => a
0 @ a @ a @ a => 0


0 + 1 => 1
1 + 1 => 2
2 + 1 => 0 (进位)


// 加 0 保持不变
00 + 0 => 00
01 + 0 => 01
10 + 0 => 10

// 加 1 在三种状态下循环
00 + 1 => 01
01 + 1 => 10
10 + 1 => 00


high low x newHigh newLow
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0

### 推导 newLow 表达式

high low x newLow
0 1 0 1
0 0 1 1

newLow = (~high & low & ~x) | (~high & ~low & x)

### 推导 newHigh 表达式

high x newLow newHigh
1 0 0 1
0 1 0 1

newHigh = (high & ~x & ~newLow) | (~high & x & ~newLow)

Golang

func singleNumber(nums []int) int {
high := 0
low := 0
for i := 0; i < len(nums); i++ {
low = (^high & low & ^nums[i]) | (^high & ^low & nums[i])
high = (high & ^nums[i] & ^low) | (^high & nums[i] & ^low)
}
fmt.Println(high,low)
return low
}