算法44-异或运算|交换int|找出出现奇数次的数|提取右边以一个1

1 交换两个数

题目1

不用增加任何的空间，将两个数交换

分析：

异或运算的原则

1 已或运算满足结合律和jiaohuanlv
2 两个相同的数异或运算等于0

代码：

package main
import(
	"fmt"
)

func swip(a,b int){
	a=a^b	//a=1002^5    b=5
	b=a^b	//a=1002^5    a带入b，b=1002^5^5 b=1002   
	a=a^b	//b带入a，a=1002^5^1002  a=5
	fmt.Println(a,b)
}
func main(){
	swip(1002,5)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

PS C:\Mygo\src\wangzhoufengtest\algoeithm\swipint44> go run .\swipint.go
5 1002
1
2

2 找到出现奇数次的数

题目2：

分析：
异或运算的交换律和结合律，相等的数被异或成0，剩下的就是奇数次的数

代码：

func evevtimes(list []int){
	eor:=0
	for i:=0;i<len(list);i++{
		eor=eor^list[i]
	}
	fmt.Println(eor)
}

func main(){
	swip(1002,5)
	list:=[]int{1,3,4,2,1,1,2,4,3,1,2,2,4}
	evevtimes(list)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

```cpp
PS C:\Mygo\src\wangzhoufengtest\algoeithm\swipint44> go run .\swipint.go
5 1002
4
1
2
3
4
5

3 提取出最右侧的1

题目3

分析：

代码：

func getrightone(n uint8){
	fmt.Printf("%08b\n",n)
	fmt.Printf("%08b\n",n&(^n+1))

	

}
1
2
3
4
5
6
7

00001100
00000100
1
2

4 找出两种出现奇数次的数

题目4：

分析：
1 假设a出现了奇数次，b也出现了奇数次，其他数都是偶数次，那么用eor=0与每一个数异或的结果只剩a^b

2 如何从列表中找出a和b，因为a和b是剩下的，所以a和b的某一位上一定是不同的数，通过上面第3题可以找到最右侧是1的数，将他们划为一组，另外对应的位置上是0的数划为一组

3 用eor‘’和最右侧出现1的数异或，这样就找到了一个，剩下的一个就是eor^eor’

代码：

//返回右侧第一位1
func getrightone(n uint8) string{
	// fmt.Printf("%08b\n",n)
	b:=n&(^n+1)
	return convertToBin(int(b))
	

}
func convertToBin(num int) string {
    s := ""
    if num == 0 {
        return "0"
    }    
    // num /= 2 每次循环的时候 都将num除以2  再把结果赋值给 num
    for ;num > 0 ; num /= 2 {
        lsb := num % 2
        // strconv.Itoa() 将数字强制性转化为字符串
        s = strconv.Itoa(lsb) + s
    }
    return s
}
//找出两个偶数次的数
func gettwoevennum(list []int){
	eor:=0
	//先与eor异或得到一个数
	for i:=0;i<len(list);i++{
		eor=eor^list[i]
	}
	// fmt.Println(eor)
	//得到第一次异或的数的右边第一个1
	eor1:=0
	//遍历list元素中右边第一个1与上限得到的第一个元素位置相同，就与eor1异或
	for i:=0;i<len(list);i++{
		//拿到eor右边第一个1，与数组元素取与运算，为true表示这个list元素右边第一个1与eor在同一位
		if list[i] & eor&(^eor+1) !=0{
			eor1=eor1^list[i]
		}
	}
	//与eor1异或后得到的数就是其中一个数
	//再将这个数与eor异或，就得到另外一个数
	fmt.Println(eor1)
	fmt.Println(eor1^eor)

}

func main(){

	// swipint(1002,5)
	// list:=[]int{1,3,4,2,1,1,2,4,3,1,2,2,4}
	// evevtimes(list)
	
    // var d uint8 = 12
	// fmt.Println(getrightone(d))

	// fmt.Println(convertToBin(12))
	list:=[]int{7,9,8,7,8,9,7,8}
	gettwoevennum(list)

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

打印：

PS C:\Mygo\src\wangzhoufengtest\algoeithm\swipint44> go run .\swipint.go
7
8
1
2
3

总结：

1 golang中没有取反~操作，只有^

	a:=7
	b:=^a
	c:=^b
	fmt.Println(a,b,c)
1
2
3
4

7 -8 7
1

5 返回有几个1

题目5
求二进制中一个有几个1

分析：
每次求出最右侧的1，再将这个1抹掉，这样不用遍历完整个二进制数

代码：

func getall1(n int) int{
	count:=0
	for n!=0{
		rightone:=n&(^n+1)//求出最右侧l
		count ++
		n=n^rightone//n与最右侧1与或就可以抹点最右侧1
	}
	return count
}
1
2
3
4
5
6
7
8
9