2020-06-22：已知两个非负数的异或值为M，两数之和为N，求这两个数？
【摘要】 福哥答案2020-06-22：1.遍历法时间复杂度：O(N)最好空间复杂度：O(1)平均空间复杂度：O(sqrt(N))最坏空间复杂度：O(N)[0,N/2]依次遍历，符合条件的就是需要的结果。2.位运算法最好时间复杂度：O(1)平均时间复杂度：O(sqrt(N))最坏时间复杂度：O(N)最好空间复杂度：O(1)平均空间复杂度：O(sqrt(N))最坏空间复杂度：O(N)1100100 两数...
福哥答案2020-06-22：
1.遍历法
时间复杂度：O(N)
最好空间复杂度：O(1)
平均空间复杂度：O(sqrt(N))
最坏空间复杂度：O(N)
[0,N/2]依次遍历，符合条件的就是需要的结果。
2.位运算法
最好时间复杂度：O(1)
平均时间复杂度：O(sqrt(N))
最坏时间复杂度：O(N)
最好空间复杂度：O(1)
平均空间复杂度：O(sqrt(N))
最坏空间复杂度：O(N)
1100100 两数和N=100，已知
0010100 异或值M=20，已知
1010000 差N-M=80，如果差为负数或者差为奇数，直接返回空
0101000 差右移1位。
0010100 异或值M=20，已知
0101000 差右移1位。
将上面两个二进制数换成中文如下：
同同异同异同同
零幺零幺零零零
零幺异幺异零零=01x1x00，x代表0和1，只要满足这样的数就行。规则：同零=0，同幺=1，异零=x，异幺=不符合条件。只要出现了异幺，直接返回空。
golang代码如下：
|
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
package
test23_xorandsum
import
(
"fmt"
"testing"
)
const
(
SameOne =
1
SameZero =
0
Different =
2
DifferentZero =
0
)
//go test -v -test.run TestXorAndSum
func TestXorAndSum(t *testing.T) {
//M := uint(20)
//N := uint(100)
M := uint(
1
)
N := uint(
9
)
fmt.Println(
"M = "
, M)
fmt.Println(
"N = "
, N)
fmt.Println(
"遍历法："
, xorAndSum1(M, N))
fmt.Println(
"位操作法："
, xorAndSum2(M, N))
}
//M是两个数异或值
//N是两个数之和
//1.遍历法
func xorAndSum1(M uint, N uint) [][]uint {
ret := make([][]uint,
0
)
//返回多个值
n := N >>
1
//只需要遍历一半
temp := uint(
0
)
for
i := uint(
0
); i <= n; i++ {
temp = M ^ i
if
N-i == temp {
//找到异或值和两数和的两个数了
ret = append(ret, []uint{i, temp})
}
}
return
ret
}
//M是两个数异或值
//N是两个数之和
//2.位操作法
func xorAndSum2(M uint, N uint) [][]uint {
ret := make([][]uint,
0
)
//返回多个值
//两数之和小于两数异或值，不存在这样的情况
if
N < M {
return
ret
}
sub := N - M
//差值
//不能被2整除，不存在这样的情况
if
sub&
1
==
1
{
return
ret
}
//生成中间结果
sub >>=
1
//差值右移动一位，方便做判断
slicebit := make([]
byte
,
0
)
kind := uint(
1
)
for
sub >
0
|| M >
0
{
if
M&
1
==
1
{
//当前位，两数不同
if
sub&
1
==
1
{
//不存在这样的情况
return
ret
}
else
{
slicebit = append(slicebit, Different)
kind <<=
1
}
}
else
{
//当前位，两数相同
if
sub&
1
==
1
{
//当前位肯定都为1
slicebit = append(slicebit, SameOne)
}
else
{
//当前位肯定都为0
slicebit = append(slicebit, SameZero)
}
}
sub >>=
1
M >>=
1
}
//两数异或值M第1个1位0，作用是去重
for
i := len(slicebit) -
1
; i >=
0
; i-- {
if
slicebit[i] == Different {
slicebit[i] = DifferentZero
kind >>=
1
break
}
}
//生成结果
retsingle := uint(
0
)
tempi1 := uint(
0
)
tempi2 := uint(
0
)
for
i := uint(
0
); i < kind; i++ {
//遍历种类
retsingle =
0
tempi1 = i
//这段代码可以省略，影响打印顺序
//00=0 01=1 10=2 11=3
//00=0 10=2 01=1 11=3
kindtemp := kind
tempi2 =
0
for
{
tempi2 <<=
1
tempi2 |= tempi1 &
1
tempi1 >>=
1
kindtemp >>=
1
if
kindtemp <=
1
{
break
}
}
tempi1 = tempi2
//生成结果
for
j := len(slicebit) -
1
; j >=
0
; j-- {
retsingle <<=
1
if
slicebit[j] <= SameOne {
retsingle |= uint(slicebit[j])
}
else
{
retsingle |= uint(tempi1 &
1
)
tempi1 >>=
1
}
}
//将结果保存起来
ret = append(ret, []uint{retsingle, N - retsingle})
}
return
ret
}
|
敲命令go test -v -test.run TestXorAndSum，执行结果如下：
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
- 2025-03-07：网格图操作后的最大分数。给定一个 n x n 的二维矩阵 grid，初始时所有格子均为白色。你可以进行操作
- 2025-03-06：给定一个长度为 n 的整数组 nums，其中 n 是偶数，同时还有一个整数 k。 你可以进行一些操作，每次
- 绝了！k3s (k8s) 安装 ollama 运行 deepseek 全流程揭秘，yaml全公开
- 2025-03-04：求出硬币游戏的赢家。用go语言，给定两个正整数 x 和 y，分别代表75元和10元硬币的数量。 Alice
- 2025-03-03：切蛋糕的最小总开销Ⅱ。用go语言，你有一个大小为 m x n 的矩形蛋糕，需要将其切割成 1 x 1 的小
评论（0）