package cap3

import "strings"

// Ex19 高精度阶乘
func Ex19(n uint64) string {
	result := []uint8{1}
	for i := uint64(2); i <= n; i++ {
		result = multiply(result, i)
	}

	return DigitSlice2String(result)
}

func multiply(a []uint8, b uint64) []uint8 {
	result := make([]uint8, len(a)+22)
	resultEndIdx := len(result) - 1
	bOffset := 0
	for i := b; i >= 1; i /= 10 {
		carry := uint8(0)
		bDigit := uint8(i % 10)
		aEnd, resultIdx := len(a)-1, 0
		for j := 0; j < len(a); j++ {
			// 字符转数字
			aDigit := a[aEnd-j]
			// 当前位计算结果 = 当前结果 + aDigit*bDigit + 进位
			resultIdx = resultEndIdx - (bOffset + j)
			num := result[resultIdx] + aDigit*bDigit + carry
			// 当前位为计算结果的个位，进位为十位上的数字
			result[resultIdx] = num % 10
			carry = num / 10
		}

		// 如果还有进位，则对下一个结果位添加进位，此时不会再有进位
		if carry != 0 {
			resultIdx--
			result[resultIdx] += carry
		}

		bOffset++
	}

	return result
}

func multiply2(a []uint8, b uint64) []uint8 {
	result := make([]uint8, len(a)+22)
	resultEndIdx := len(result)*2 - 1
	bOffset := 0
	for i := b; i >= 1; i /= 10 {
		carry := uint8(0)
		bDigit := uint8(i % 10)
		aEnd, resultIdx := len(a)*2-1, 0
		for j := 0; j < len(a); j++ {
			// 字符转数字
			aDigit := uint8(0)
			// 4,5 -> 37(0010,0101)
			aIdx := aEnd - j
			if aIdx%2 == 0 {
				aDigit = a[aIdx/2] >> 4
			} else {
				aDigit = a[aIdx/2] & 0b00001111
			}

			// 当前位计算结果 = 当前结果 + aDigit*bDigit + 进位
			resultIdx = resultEndIdx - (bOffset + j)
			bitIdx := resultIdx / 2
			if resultIdx%2 == 0 {
				num := (result[bitIdx] >> 4) + aDigit*bDigit + carry
				// 清位
				// 4,5 -> 37(0010,0101) => 0,5 -> 5(0000,0101)
				result[bitIdx] &= 0b00001111
				// 位赋值
				// 0,5 -> 5(0000,0101) => 5,5 -> 5(0101,0101)
				// 5(0000,0101) << 4 => 80(0101,0000)
				// 5(0000,0101) | 80(0101,0000) => 5,5 -> 5(0101,0101)
				result[bitIdx] |= (num % 10) << 4
				carry = num / 10
			} else {
				num := (result[bitIdx] & 0b00001111) + aDigit*bDigit + carry
				// 清位
				// 4,5 -> 37(0010,0101) => 4,0 -> 32(0010,0000)
				result[bitIdx] &= 0b11110000
				// 赋值
				// 4,0 -> 32(0010,0000) => 4,5 -> 37(0010,0101)
				// 32(0010,0000) | 5(0000,0101) => 4,5 -> 37(0010,0101)
				result[bitIdx] |= num % 10
				carry = num / 10
			}
		}

		// 如果还有进位，则对下一个结果位添加进位，此时不会再有进位
		if carry != 0 {
			resultIdx--
			bitIdx := resultIdx / 2
			if resultIdx%2 == 0 {
				// 4,5 -> 37(0010,0101) => 5,5 -> 37(0101,0101)
				// 4+1 -> 5(0000,0101) << 4 => 80(0101,0000)
				// 5(0000,0101) | 80(0101,0000) => 5,5 -> 5(0101,0101)
				result[bitIdx] &= 0b00001111
				num := (result[bitIdx] >> 4) + carry
				result[bitIdx] |= num << 4
			} else {
				result[bitIdx] &= 0b11110000
				num := (result[bitIdx] & 0b00001111) + carry
				result[bitIdx] |= num
			}
		}

		bOffset++
	}

	return result
}

// Ex19LowMem 低内存使用版，两位数字结果按位存在同一个uint8中，一个0~9数字只使用四字节，uint8可存两位，一个字节拆成两半用
func Ex19LowMem(n uint64) string {
	result := []uint8{1}
	for i := uint64(2); i <= n; i++ {
		result = multiply2(result, i)
	}

	zeroPrefix := true
	sb := strings.Builder{}
	for _, num := range result {
		if zeroPrefix && num == 0 {
			continue
		} else {
			zeroPrefix = false
		}

		sb.WriteByte((num >> 4) + 48)
		sb.WriteByte((num & 0b00001111) + 48)
	}

	return sb.String()
}