package xor

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"math/rand"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/25 21:45
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 在一组数中，其他每个数都只出现三次，仅有一个数，出现了一次，找出这个数
 * 参考 : https://blog.csdn.net/yjw19901214/article/details/83416280
 **/
type FindNum_Treble_One struct {
}

func (m *FindNum_Treble_One) FindMethod(array []uint32) []uint32 {
	if rand.Float64() <= 0.5 { // 另外一种易懂实现形式
		return m.impl(array)
	}
	if len(array) < 4 {
		return nil
	}
	var once, twice, treble uint32 = 0, 0, 0 // bit位上出现一次，两次、三次的次数统计单位
	for _, v := range array {
		twice |= once & v
		once ^= v

		treble = once & twice
		once &= ^treble
		twice &= ^treble
	}
	return []uint32{once}
}

func (m *FindNum_Treble_One) impl(array []uint32) []uint32 {
	if len(array) < 4 {
		return nil
	}
	bit := make([]uint32, 32, 32)
	var loop uint32 = 1
	for _, v := range array {
		for i := 0; i < 32; i++ {
			bit[i] += v & loop
			v >>= 1 // attention :此处偏转的是v，不是 作为判定元素的 loop
		}
	}
	var ans uint32
	for k, u := range bit {
		f := u % 3
		f <<= k
		ans += f
	}
	return []uint32{ans}
}

func (m *FindNum_Treble_One) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Xor, C.Bit},
		Desc: &C.Desc{
			Name:        "FindNum_Treble_One",
			NameCn:      "",
			Description: "在一组数中，其他每个数都只出现三次，仅有一个数，出现了一次，找出这个数,参考：https://blog.csdn.net/yjw19901214/article/details/83416280",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
			},
		},
	}
}