Bit Manipulation & Math

// SingleNumber (LeetCode 136): every value appears twice except one.
// x ^ x == 0 and x ^ 0 == x, so XOR-ing everything cancels the pairs.
func SingleNumber(nums []int) int {
	result := 0
	for _, n := range nums {
		result ^= n
	}
	return result
}

// MissingNumber (LeetCode 268): XOR every index and every value; only the missing number is left unpaired.
func MissingNumber(nums []int) int {
	result := len(nums)
	for i, n := range nums {
		result ^= i ^ n
	}
	return result
}

// HammingWeight (LeetCode 191): n & (n-1) clears the lowest set bit, so the loop runs once per 1-bit.
func HammingWeight(n uint32) int {
	count := 0
	for n != 0 {
		n &= n - 1
		count++
	}
	return count
}

// CountBits (LeetCode 338): bits of i = bits of i/2 (shift right) plus its last bit.
func CountBits(n int) []int {
	bits := make([]int, n+1)
	for i := 1; i <= n; i++ {
		bits[i] = bits[i>>1] + i&1
	}
	return bits
}

// ReverseBits (LeetCode 190): peel the lowest bit off n and push it onto the result from the right.
func ReverseBits(n uint32) uint32 {
	var result uint32
	for range 32 {
		result = result<<1 | n&1
		n >>= 1
	}
	return result
}

// GetSum (LeetCode 371): add without + or -. XOR is addition without carry, AND shows where the carries go.
func GetSum(a, b int32) int32 {
	for b != 0 {
		carry := uint32(a&b) << 1
		a ^= b
		b = int32(carry)
	}
	return a
}

// Reverse (LeetCode 7): reverse the digits of a 32-bit integer, or 0 if the result would overflow.
// The overflow check happens BEFORE multiplying, because afterwards it is too late.
func Reverse(x int) int {
	rev := 0
	for x != 0 {
		digit := x % 10
		x /= 10
		if rev > math.MaxInt32/10 || (rev == math.MaxInt32/10 && digit > 7) {
			return 0
		}
		if rev < math.MinInt32/10 || (rev == math.MinInt32/10 && digit < -8) {
			return 0
		}
		rev = rev*10 + digit
	}
	return rev
}

// MyPow (LeetCode 50): fast exponentiation. x^n = (x^(n/2))^2, times x when n is odd. O(log n) multiplications.
func MyPow(x float64, n int) float64 {
	if n < 0 {
		return 1 / MyPow(x, -n)
	}
	if n == 0 {
		return 1
	}
	half := MyPow(x, n/2)
	if n%2 == 0 {
		return half * half
	}
	return half * half * x
}

// IsHappy (LeetCode 202): sum the squares of the digits repeatedly. Reaching 1 means happy;
// the sequence is a linked list, so a repeat means a cycle (detected with slow and fast pointers).
func IsHappy(n int) bool {
	step := func(x int) int {
		sum := 0
		for ; x > 0; x /= 10 {
			d := x % 10
			sum += d * d
		}
		return sum
	}
	slow, fast := n, step(n)
	for fast != 1 && slow != fast {
		slow = step(slow)
		fast = step(step(fast))
	}
	return fast == 1
}

// PlusOne (LeetCode 66): add one to a number stored as a digit slice.
func PlusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] < 9 {
			digits[i]++
			return digits // no carry left to pass on
		}
		digits[i] = 0 // 9 + 1 = 0, carry one position left
	}
	return append([]int{1}, digits...) // all nines: 999 -> 1000
}

// Rotate (LeetCode 48): rotate an n×n matrix 90° clockwise in place = transpose, then reverse every row.
func Rotate(m [][]int) {
	n := len(m)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			m[i][j], m[j][i] = m[j][i], m[i][j]
		}
	}
	for _, row := range m {
		for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
			row[l], row[r] = row[r], row[l]
		}
	}
}

// SpiralOrder (LeetCode 54): walk the outer ring, then shrink the four boundaries.
func SpiralOrder(m [][]int) []int {
	if len(m) == 0 {
		return nil
	}
	top, bottom, left, right := 0, len(m)-1, 0, len(m[0])-1
	var out []int
	for top <= bottom && left <= right {
		for c := left; c <= right; c++ {
			out = append(out, m[top][c])
		}
		top++
		for r := top; r <= bottom; r++ {
			out = append(out, m[r][right])
		}
		right--
		if top <= bottom { // a single remaining row must not be walked twice
			for c := right; c >= left; c-- {
				out = append(out, m[bottom][c])
			}
			bottom--
		}
		if left <= right { // same for a single remaining column
			for r := bottom; r >= top; r-- {
				out = append(out, m[r][left])
			}
			left++
		}
	}
	return out
}

// Multiply (LeetCode 43): multiply two numbers given as strings, digit by digit like on paper.
// Digit i of a times digit j of b lands in result position i+j+1 (carry goes to i+j).
func Multiply(a, b string) string {
	if a == "0" || b == "0" {
		return "0"
	}
	res := make([]int, len(a)+len(b))
	for i := len(a) - 1; i >= 0; i-- {
		for j := len(b) - 1; j >= 0; j-- {
			sum := int(a[i]-'0')*int(b[j]-'0') + res[i+j+1]
			res[i+j+1] = sum % 10
			res[i+j] += sum / 10
		}
	}
	out := make([]byte, 0, len(res))
	for i, d := range res {
		if i == 0 && d == 0 {
			continue // strip the single possible leading zero
		}
		out = append(out, byte('0'+d))
	}
	return string(out)
}