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 两数和N=100，已知
0010100 异或值M=20，已知
1010000 差N-M=80，如果差为负数或者差为奇数，直接返回空
0101000 差右移1位。

0010100 异或值M=20，已知
0101000 差右移1位。
将上面两个二进制数换成中文如下：
同同异同异同同
零幺零幺零零零

---

零幺异幺异零零=01x1x00，x代表0和1，只要满足这样的数就行。规则：同零=0，同幺=1，异零=x，异幺=不符合条件。只要出现了异幺，直接返回空。

golang代码如下：

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，执行结果如下：

2020-06-22：已知两个非负数的异或值为M，两数之和为N，求这两个数？的相关教程结束。