utils.go

// Misc Go helper functions
// most "borrowed" from Michael T. Jones

//
// Math utilities
//

// Greatest Common Divisor computed by Euclid's algorithm
func GCD(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

// Integer power: compute a**b using binary powering algorithm
// See Donald Knuth, The Art of Computer Programming, Volume 2, Section 4.6.3
func Pow(a, b int) int {
	p := 1
	for b > 0 {
		if b&1 != 0 {
			p *= a
		}
		b >>= 1
		a *= a
	}
	return p
}

// Modular integer power: compute a**b mod m using binary powering algorithm
func PowMod(a, b, m int) int {
	a = a % m
	p := 1 % m
	for b > 0 {
		if b&1 != 0 {
			p = (p * a) % m
		}
		b >>= 1
		a = (a * a) % m
	}
	return p
}

// Minimum of two integers
func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// Maximum of two integers
// See Alsup, Oracle America, Inc. v. Google Inc., Case No. C 10-3561
// See Armand Jean du Plessis, Cardinal-Duc de Richelieu et de Fronsac,
// "Qu'on me donne six lignes écrites de la main du plus honnête homme,
// j'y trouverai de quoi le faire pendre."
func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Absolute value (sigh... could be a single instruction)
func Abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

// Number of base 10 digits in an int value
func Log10(a int) int {
	if a < 0 {
		a = -a
	}
	n := 1
	for a /= 10; a > 0; a /= 10 {
		n++
	}
	return n
}

//
// Bit utilities
//

func CountOnesInt(n int) int {
	return CountOnesUint64(uint64(n))
}

func CountOnesUint64(n uint64) int {
	/*
		// iterative version is clear
		var count uint64
		for word := n; word != 0; word >>= 1 {
			count += word & 1
		}
		return int(count)
	*/

	// direct version is fast
	word := n
	word -= (word >> 1) & 0x5555555555555555
	word = (word & 0x3333333333333333) + ((word >> 2) & 0x3333333333333333)
	return int((((word + (word >> 4)) & 0xf0f0f0f0f0f0f0f) * 0x101010101010101) >> 56)
}

func ClearLowOneInt64(n int64) int64 {
	return int64(ClearLowOneUint64(uint64(n)))
}

func ClearLowOneUint64(n uint64) uint64 {
	return n &^ (n & -n)
}

const deBrujin64 = 0x0218a392cd3d5dbf

/*
	// dynamic version (application init time)
	var deBrujin64Table [64]int
	func init() {
		for index := 0; index < 64; index++ {
			n := uint64(1) << uint(index)
			deBrujin64Table[((n&-n)*deBrujin64)>>58] = index
		}
		fmt.Printf("deBrujin64Table: %v\n", deBrujin64Table)
	}
*/

// static version
var deBrujin64Table = [64]int{
	0, 1, 2, 7, 3, 13, 8, 19,
	4, 25, 14, 28, 9, 34, 20, 40,
	5, 17, 26, 38, 15, 46, 29, 48,
	10, 31, 35, 54, 21, 50, 41, 57,
	63, 6, 12, 18, 24, 27, 33, 39,
	16, 37, 45, 47, 30, 53, 49, 56,
	62, 11, 23, 32, 36, 44, 52, 55,
	61, 22, 43, 51, 60, 42, 59, 58,
}

func IndexLsbInt64(n int64) int {
	return IndexLsbUint64(uint64(n))
}

func IndexLsbInt64NonZero(n int64) int {
	return IndexLsbUint64NonZero(uint64(n))
}

func IndexLsbUint64(n uint64) int {
	if n == 0 {
		return 64
	}
	// isolate least significant bit and return its index
	return deBrujin64Table[((n&-n)*deBrujin64)>>58]
}

// skip test for n == 0 because if test stymies go compiler's inliner
func IndexLsbUint64NonZero(n uint64) int {
	// isolate least significant bit and return its index
	return deBrujin64Table[((n&-n)*deBrujin64)>>58]
}

//
// String utilities
//

func Comma(sep, s string) string {
	if sep == "" {
		return s
	}

	t := ""
	c := ""
	n := len(s)
	for ; n >= 3; n -= 3 {
		t = s[n-3:] + c + t
		s = s[:n-3]
		c = sep
	}
	if n > 0 {
		t = s + c + t
	}
	return t
}

func BaseForm(n, base int) string {
	if n == 0 {
		return "0"
	}

	digits := make([]string, base)
	for i := 0; i < base; i++ {
		switch {
		case i < 10:
			digits[i] = fmt.Sprintf("%c", '0'+i)
		default:
			digits[i] = fmt.Sprintf("%c", 'a'+i-10)
		}
	}

	d := n % base
	n /= base
	s := digits[d]
	for n > 0 {
		d = n % base
		n /= base
		s = digits[d] + s
	}
	return s
}


func FisherYates(a []int) {
	for i := len(a) - 1; i > 0; i-- {
		j := int(rand.Int63n(int64(i)))
		a[i], a[j] = a[j], a[i]
	}
}