[TOC]
背景
位运算上篇文章位运算简单介绍了什么是位运算,以及
goalng位运算的特点.这篇结合几个实例深入位运算的理解
异或
异或的真值表如下:
| a | b | ⊕ |
|---|---|---|
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
一些规律
交换律：a ^ b ^ c <=> a ^ c ^ b
任何数于0异或为该数: 0 ^ n => n
相同的数异或为0: n ^ n => 0
任何数&该数的取反为0: x & ^x = 0,
任何数&非0为该数: x & ^0 = x;
逻辑操作与加减法结合起来的恒等式:
-x = ^x + 1
-x = ^(x-1)
^x = -x -1
-^x = x +1
…
示例
136. singleNumber1
描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度O(n),空间复杂度为O(1)
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
思路
根据这个规律:
相同的数异或为0: n ^ n => 0
交换律：a ^ b ^ c <=> a ^ c ^ b
var a = [2,3,2,4,4]
2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3
代码
func SingleNumber(nums []int) int {
x := nums[0]
for i := 0; i < len(nums); i++ {
x ^= nums[i]
}
return x
}
137. SingleNumber2
描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度O(n),空间复杂度为O(1)
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
思路1
大佬说: 能设计一个状态转换电路，使得一个数出现3次时能自动抵消为0，最后剩下的就是只出现1次的数。
则有:
x出现一次:
a = (a ^ x) & ^b ==> a = x
b = (b ^ x) & ^a ==> (因为a=x,所有b=0)
x出现两次:
a = (a ^ x) & ^b ==> a = (x ^ x) & ^0 ==> a = 0
b = (b ^ x) & ^a ==> b = (0 ^ x) & ^0 ==> b = x
x出现三次:
a = (a ^ x) & ^b ==> a = (0 ^ x) & ^x ==> a = 0
b = (b ^ x) & ^a ==> b = (x ^ x) & ^0 ==> b = 0
代码
func SingleNumber2(nums []int) int {
a, b := 0, 0
for _, x := range nums {
a = (a ^ x) & ^b
b = (b ^ x) & ^a
}
return a
}
思路2
利用hashmap来存储出现的次数. key存储该数, value存储该数出现的状态.
代码
func SingleNumber2x(nums []int) int {
var (
map1 = make(map[int]int8)
)
for _, value := range nums {
map1[value]++
}
for key, v := range map1 {
if v == 1 {
return key
}
}
return 0
}
测试性能
两种思路性能比对,Benchmark测试
func BenchmarkSingleNumber2(b *testing.B) {
var a = []int{1, 1, 1, 3, 3, 3, 5, 5, 5, 2, 6, 6, 6, 8, 8, 8}
b.ResetTimer()
for i := 0; i <= b.N; i++ {
SingleNumber2(a)
}
}
func BenchmarkSingleNumber2x(b *testing.B) {
var a = []int{1, 1, 1, 3, 3, 3, 5, 5, 5, 2, 6, 6, 6, 8, 8, 8}
b.ResetTimer()
for i := 0; i <= b.N; i++ {
SingleNumber2x(a)
}
}
测试性能
$ go test -bench=. -benchmem -run=none
goos: windows
goarch: amd64
pkg: gogs.wangke.co/go/algo/leetcode
BenchmarkSingleNumber2-4 63165872 24.6 ns/op 0 B/op 0 allocs/op
BenchmarkSingleNumber2x-4 2542356 472 ns/op 64 B/op 2 allocs/op
PASS
ok gogs.wangke.co/go/algo/leetcode 3.508s
很明显,利用hashmap会产生多余的内存空间.速度下降.性能比对疑惑,leetcode上面是hashmap占优.
260. SingleNumber3
描述
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
思路
位运算，异或运算。对于一个数组nums = [1, 1 , 2, 2, 3, 4, 4, 5]。
其一，如果，进行一次全部异或运算，将会得到3 ^ 5。
其二， 3 ^ 5 = 110b。那么在出现1的位置，必然一个为1一个为0，这样就可以根据特征区分出两个数字。
Hacker’s Delight 2nd Edition Chinese
Use the following formula to isolate the rightmost 1-bit, producing 0 if none (eg, 01011000 ==> 0000 1000):
x & (-x)翻译过来: 下列公式可以保留x中最靠右且值为1的位元,并将其余位元置0;若不存在,则生成的数为0.(01011000 ==> 0000 1000):
x & (-x)
其三，于是将问题转化为了“一个数字出现1次，其他数字出现两次”。
代码
func SingleNumber3(nums []int) []int {
var diff int
var res = make([]int, 2)
for _, v := range nums {
diff ^= v
}
// 3(011),5(101) 两个不一样， diff = 110
// diff &= ^diff +1 //==> 找到只出现一次的两个数最右侧不相同的位
diff &= -diff
// diff = 10
for _, v := range nums {
if v&diff == 0 {
res[0] ^= v
} else {
res[1] ^= v
}
}
return res
}
测试用例
func TestSingleNumber3(t *testing.T) {
type args struct {
nums []int
}
tests := []struct {
name string
args args
want []int
}{
{"test01",args{[]int{1,2,1,3,2,5}},[]int{3,5}},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got := SingleNumber3(tt.args.nums)
sort.Ints(got) //返回的数组未排序,比较起来不方便
if !reflect.DeepEqual(got, tt.want) {
t.Errorf("SingleNumber3() = %v, want %v", got, tt.want)
}
})
}
}
/*
=== RUN TestSingleNumber3
=== RUN TestSingleNumber3/test01
--- PASS: TestSingleNumber3 (0.00s)
--- PASS: TestSingleNumber3/test01 (0.00s)
PASS
*/
感谢阅读~源码