Skip to content

Instantly share code, notes, and snippets.

@jbardin
Last active February 1, 2022 11:12
Show Gist options
  • Save jbardin/9977838 to your computer and use it in GitHub Desktop.
Save jbardin/9977838 to your computer and use it in GitHub Desktop.
// 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]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment