package xor

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/25 11:31
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 找出数组中唯二出现一次的数
 * 在一组数中，每个数都出现了两次，但是唯独有两个数，仅出现一次，找出这个数
 **/
type FindNum_Twice_Two struct {
}

func (m *FindNum_Twice_Two) FindMethod(array []uint32) []uint32 {
	if len(array) < 3 {
		return nil
	}
	var temp uint32 = 0
	for _, v := range array {
		temp ^= v
	}
	/*point := 1
	for i := 0; i < 32; i++ { //grammar内存 int类型在内存中占用了4个字节，也就是32位
		if point&temp != 0 { // attention : 此处是 "!= 0"，而不是 "==1"
			break
		}
		point <<= 1
	}*/
	point := temp & -temp //tips : 代替上述for循环，二进制的负数就是七本身按位取反，末尾加一，相&就可以求出最右边的1
	var x, y uint32 = 0, 0
	for _, v := range array {
		if v&point == 0 {
			x ^= v
		} else {
			y ^= v
		}
	}
	if y > x {
		return []uint32{x, y}
	}
	return []uint32{y, x}
}

func (m *FindNum_Twice_Two) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Xor, C.Bit},
		Desc: &C.Desc{
			Name:        "FindNum_Twice_Two",
			NameCn:      "找出数组中唯二出现一次的数",
			Description: "在一组数中，每个数都出现了两次，但是唯独有两个数，仅出现一次，找出这个数",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
				1: "数组 [1,1,2,2,3,3,5，6]中，5和6仅仅出现一次，其他数字出现2次",
			},
		},
	}
}