Alg | 位运算

基础位运算

lowbit

xor

xor：异或，同 0 异 1,又称进位加法。 $$a \bigoplus a = 0 \qquad (1)$$ $$a \bigoplus 0 = a \qquad (2)$$

Lc136

problem

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
找出那个 只出现了一次 的元素。

idea

因为式(1),所以对所有元素进行异或，出现两次的元素异或之后都为 0,
因此变成了:
令 a=只出现一次的元素,则 $a \bigoplus 0 = a$, 即为答案

code

1
2
3
4
5
6
7

func singleNumber(a []int) int {
    res := 0
    for i:=0;i<len(a);i++{
        res ^= a[i]
    }
    return res
}