Source: bits.go in package math/bits

go:generate go run make_tables.go

Package bits implements bit counting and manipulation functions for the predeclared unsigned integer types.

package bits

const uintSize = 32 << (^uint(0) >> 32 & 1) // 32 or 64

UintSize is the size of a uint in bits.

const UintSize = uintSize

--- LeadingZeros ---

LeadingZeros returns the number of leading zero bits in x; the result is UintSize for x == 0.

func LeadingZeros(x uint) int { return UintSize - Len(x) }

LeadingZeros8 returns the number of leading zero bits in x; the result is 8 for x == 0.

func LeadingZeros8(x uint8) int { return 8 - Len8(x) }

LeadingZeros16 returns the number of leading zero bits in x; the result is 16 for x == 0.

func LeadingZeros16(x uint16) int { return 16 - Len16(x) }

LeadingZeros32 returns the number of leading zero bits in x; the result is 32 for x == 0.

func LeadingZeros32(x uint32) int { return 32 - Len32(x) }

LeadingZeros64 returns the number of leading zero bits in x; the result is 64 for x == 0.

func LeadingZeros64(x uint64) int { return 64 - Len64(x) }

--- TrailingZeros ---

See http://supertech.csail.mit.edu/papers/debruijn.pdf

const deBruijn32 = 0x077CB531

var deBruijn32tab = [32]byte{
	0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
	31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
}

const deBruijn64 = 0x03f79d71b4ca8b09

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

TrailingZeros returns the number of trailing zero bits in x; the result is UintSize for x == 0.

func TrailingZeros(x uint) int {
	if UintSize == 32 {
		return TrailingZeros32(uint32(x))
	}
	return TrailingZeros64(uint64(x))
}

TrailingZeros8 returns the number of trailing zero bits in x; the result is 8 for x == 0.

func TrailingZeros8(x uint8) int {
	return int(ntz8tab[x])
}

TrailingZeros16 returns the number of trailing zero bits in x; the result is 16 for x == 0.

func TrailingZeros16(x uint16) int {
	if x == 0 {
		return 16

see comment in TrailingZeros64

	return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)])
}

TrailingZeros32 returns the number of trailing zero bits in x; the result is 32 for x == 0.

func TrailingZeros32(x uint32) int {
	if x == 0 {
		return 32

see comment in TrailingZeros64

	return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)])
}

TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0.

func TrailingZeros64(x uint64) int {
	if x == 0 {
		return 64

If popcount is fast, replace code below with return popcount(^x & (x - 1)). x & -x leaves only the right-most bit set in the word. Let k be the index of that bit. Since only a single bit is set, the value is two to the power of k. Multiplying by a power of two is equivalent to left shifting, in this case by k bits. The de Bruijn (64 bit) constant is such that all six bit, consecutive substrings are distinct. Therefore, if we have a left shifted version of this constant we can find by how many bits it was shifted by looking at which six bit substring ended up at the top of the word. (Knuth, volume 4, section 7.3.1)

	return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)])
}

--- OnesCount ---


const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff00ff00ff // etc.
const m4 = 0x0000ffff0000ffff

OnesCount returns the number of one bits ("population count") in x.

func OnesCount(x uint) int {
	if UintSize == 32 {
		return OnesCount32(uint32(x))
	}
	return OnesCount64(uint64(x))
}

OnesCount8 returns the number of one bits ("population count") in x.

func OnesCount8(x uint8) int {
	return int(pop8tab[x])
}

OnesCount16 returns the number of one bits ("population count") in x.

func OnesCount16(x uint16) int {
	return int(pop8tab[x>>8] + pop8tab[x&0xff])
}

OnesCount32 returns the number of one bits ("population count") in x.

func OnesCount32(x uint32) int {
	return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
}

OnesCount64 returns the number of one bits ("population count") in x.

Implementation: Parallel summing of adjacent bits. See "Hacker's Delight", Chap. 5: Counting Bits. The following pattern shows the general approach: x = x>>1&(m0&m) + x&(m0&m) x = x>>2&(m1&m) + x&(m1&m) x = x>>4&(m2&m) + x&(m2&m) x = x>>8&(m3&m) + x&(m3&m) x = x>>16&(m4&m) + x&(m4&m) x = x>>32&(m5&m) + x&(m5&m) return int(x) Masking (& operations) can be left away when there's no danger that a field's sum will carry over into the next field: Since the result cannot be > 64, 8 bits is enough and we can ignore the masks for the shifts by 8 and up. Per "Hacker's Delight", the first line can be simplified more, but it saves at best one instruction, so we leave it alone for clarity.

	const m = 1<<64 - 1
	x = x>>1&(m0&m) + x&(m0&m)
	x = x>>2&(m1&m) + x&(m1&m)
	x = (x>>4 + x) & (m2 & m)
	x += x >> 8
	x += x >> 16
	x += x >> 32
	return int(x) & (1<<7 - 1)
}

--- RotateLeft ---

RotateLeft returns the value of x rotated left by (k mod UintSize) bits. To rotate x right by k bits, call RotateLeft(x, -k). This function's execution time does not depend on the inputs.

func RotateLeft(x uint, k int) uint {
	if UintSize == 32 {
		return uint(RotateLeft32(uint32(x), k))
	}
	return uint(RotateLeft64(uint64(x), k))
}

RotateLeft8 returns the value of x rotated left by (k mod 8) bits. To rotate x right by k bits, call RotateLeft8(x, -k). This function's execution time does not depend on the inputs.

func RotateLeft8(x uint8, k int) uint8 {
	const n = 8
	s := uint(k) & (n - 1)
	return x<<s | x>>(n-s)
}

RotateLeft16 returns the value of x rotated left by (k mod 16) bits. To rotate x right by k bits, call RotateLeft16(x, -k). This function's execution time does not depend on the inputs.

func RotateLeft16(x uint16, k int) uint16 {
	const n = 16
	s := uint(k) & (n - 1)
	return x<<s | x>>(n-s)
}

RotateLeft32 returns the value of x rotated left by (k mod 32) bits. To rotate x right by k bits, call RotateLeft32(x, -k). This function's execution time does not depend on the inputs.

func RotateLeft32(x uint32, k int) uint32 {
	const n = 32
	s := uint(k) & (n - 1)
	return x<<s | x>>(n-s)
}

RotateLeft64 returns the value of x rotated left by (k mod 64) bits. To rotate x right by k bits, call RotateLeft64(x, -k). This function's execution time does not depend on the inputs.

func RotateLeft64(x uint64, k int) uint64 {
	const n = 64
	s := uint(k) & (n - 1)
	return x<<s | x>>(n-s)
}

--- Reverse ---

Reverse returns the value of x with its bits in reversed order.

func Reverse(x uint) uint {
	if UintSize == 32 {
		return uint(Reverse32(uint32(x)))
	}
	return uint(Reverse64(uint64(x)))
}

Reverse8 returns the value of x with its bits in reversed order.

func Reverse8(x uint8) uint8 {
	return rev8tab[x]
}

Reverse16 returns the value of x with its bits in reversed order.

func Reverse16(x uint16) uint16 {
	return uint16(rev8tab[x>>8]) | uint16(rev8tab[x&0xff])<<8
}

Reverse32 returns the value of x with its bits in reversed order.

func Reverse32(x uint32) uint32 {
	const m = 1<<32 - 1
	x = x>>1&(m0&m) | x&(m0&m)<<1
	x = x>>2&(m1&m) | x&(m1&m)<<2
	x = x>>4&(m2&m) | x&(m2&m)<<4
	return ReverseBytes32(x)
}

Reverse64 returns the value of x with its bits in reversed order.

func Reverse64(x uint64) uint64 {
	const m = 1<<64 - 1
	x = x>>1&(m0&m) | x&(m0&m)<<1
	x = x>>2&(m1&m) | x&(m1&m)<<2
	x = x>>4&(m2&m) | x&(m2&m)<<4
	return ReverseBytes64(x)
}

--- ReverseBytes ---

ReverseBytes returns the value of x with its bytes in reversed order. This function's execution time does not depend on the inputs.

func ReverseBytes(x uint) uint {
	if UintSize == 32 {
		return uint(ReverseBytes32(uint32(x)))
	}
	return uint(ReverseBytes64(uint64(x)))
}

ReverseBytes16 returns the value of x with its bytes in reversed order. This function's execution time does not depend on the inputs.

func ReverseBytes16(x uint16) uint16 {
	return x>>8 | x<<8
}

ReverseBytes32 returns the value of x with its bytes in reversed order. This function's execution time does not depend on the inputs.

func ReverseBytes32(x uint32) uint32 {
	const m = 1<<32 - 1
	x = x>>8&(m3&m) | x&(m3&m)<<8
	return x>>16 | x<<16
}

ReverseBytes64 returns the value of x with its bytes in reversed order. This function's execution time does not depend on the inputs.

func ReverseBytes64(x uint64) uint64 {
	const m = 1<<64 - 1
	x = x>>8&(m3&m) | x&(m3&m)<<8
	x = x>>16&(m4&m) | x&(m4&m)<<16
	return x>>32 | x<<32
}

--- Len ---

Len returns the minimum number of bits required to represent x; the result is 0 for x == 0.

func Len(x uint) int {
	if UintSize == 32 {
		return Len32(uint32(x))
	}
	return Len64(uint64(x))
}

Len8 returns the minimum number of bits required to represent x; the result is 0 for x == 0.

func Len8(x uint8) int {
	return int(len8tab[x])
}

Len16 returns the minimum number of bits required to represent x; the result is 0 for x == 0.

func Len16(x uint16) (n int) {
	if x >= 1<<8 {
		x >>= 8
		n = 8
	}
	return n + int(len8tab[x])
}

Len32 returns the minimum number of bits required to represent x; the result is 0 for x == 0.

func Len32(x uint32) (n int) {
	if x >= 1<<16 {
		x >>= 16
		n = 16
	}
	if x >= 1<<8 {
		x >>= 8
		n += 8
	}
	return n + int(len8tab[x])
}

Len64 returns the minimum number of bits required to represent x; the result is 0 for x == 0.

func Len64(x uint64) (n int) {
	if x >= 1<<32 {
		x >>= 32
		n = 32
	}
	if x >= 1<<16 {
		x >>= 16
		n += 16
	}
	if x >= 1<<8 {
		x >>= 8
		n += 8
	}
	return n + int(len8tab[x])
}

--- Add with carry ---

Add returns the sum with carry of x, y and carry: sum = x + y + carry. The carry input must be 0 or 1; otherwise the behavior is undefined. The carryOut output is guaranteed to be 0 or 1. This function's execution time does not depend on the inputs.

func Add(x, y, carry uint) (sum, carryOut uint) {
	if UintSize == 32 {
		s32, c32 := Add32(uint32(x), uint32(y), uint32(carry))
		return uint(s32), uint(c32)
	}
	s64, c64 := Add64(uint64(x), uint64(y), uint64(carry))
	return uint(s64), uint(c64)
}

Add32 returns the sum with carry of x, y and carry: sum = x + y + carry. The carry input must be 0 or 1; otherwise the behavior is undefined. The carryOut output is guaranteed to be 0 or 1. This function's execution time does not depend on the inputs.

func Add32(x, y, carry uint32) (sum, carryOut uint32) {
	sum64 := uint64(x) + uint64(y) + uint64(carry)
	sum = uint32(sum64)
	carryOut = uint32(sum64 >> 32)
	return
}

Add64 returns the sum with carry of x, y and carry: sum = x + y + carry. The carry input must be 0 or 1; otherwise the behavior is undefined. The carryOut output is guaranteed to be 0 or 1. This function's execution time does not depend on the inputs.

func Add64(x, y, carry uint64) (sum, carryOut uint64) {

The sum will overflow if both top bits are set (x & y) or if one of them is (x | y), and a carry from the lower place happened. If such a carry happens, the top bit will be 1 + 0 + 1 = 0 (&^ sum).

	carryOut = ((x & y) | ((x | y) &^ sum)) >> 63
	return
}

--- Subtract with borrow ---

Sub returns the difference of x, y and borrow: diff = x - y - borrow. The borrow input must be 0 or 1; otherwise the behavior is undefined. The borrowOut output is guaranteed to be 0 or 1. This function's execution time does not depend on the inputs.

func Sub(x, y, borrow uint) (diff, borrowOut uint) {
	if UintSize == 32 {
		d32, b32 := Sub32(uint32(x), uint32(y), uint32(borrow))
		return uint(d32), uint(b32)
	}
	d64, b64 := Sub64(uint64(x), uint64(y), uint64(borrow))
	return uint(d64), uint(b64)
}

Sub32 returns the difference of x, y and borrow, diff = x - y - borrow. The borrow input must be 0 or 1; otherwise the behavior is undefined. The borrowOut output is guaranteed to be 0 or 1. This function's execution time does not depend on the inputs.

func Sub32(x, y, borrow uint32) (diff, borrowOut uint32) {

The difference will underflow if the top bit of x is not set and the top bit of y is set (^x & y) or if they are the same (^(x ^ y)) and a borrow from the lower place happens. If that borrow happens, the result will be 1 - 1 - 1 = 0 - 0 - 1 = 1 (& diff).

	borrowOut = ((^x & y) | (^(x ^ y) & diff)) >> 31
	return
}

Sub64 returns the difference of x, y and borrow: diff = x - y - borrow. The borrow input must be 0 or 1; otherwise the behavior is undefined. The borrowOut output is guaranteed to be 0 or 1. This function's execution time does not depend on the inputs.

func Sub64(x, y, borrow uint64) (diff, borrowOut uint64) {

See Sub32 for the bit logic.

	borrowOut = ((^x & y) | (^(x ^ y) & diff)) >> 63
	return
}

--- Full-width multiply ---

Mul returns the full-width product of x and y: (hi, lo) = x * y with the product bits' upper half returned in hi and the lower half returned in lo. This function's execution time does not depend on the inputs.

func Mul(x, y uint) (hi, lo uint) {
	if UintSize == 32 {
		h, l := Mul32(uint32(x), uint32(y))
		return uint(h), uint(l)
	}
	h, l := Mul64(uint64(x), uint64(y))
	return uint(h), uint(l)
}

Mul32 returns the 64-bit product of x and y: (hi, lo) = x * y with the product bits' upper half returned in hi and the lower half returned in lo. This function's execution time does not depend on the inputs.

func Mul32(x, y uint32) (hi, lo uint32) {
	tmp := uint64(x) * uint64(y)
	hi, lo = uint32(tmp>>32), uint32(tmp)
	return
}

Mul64 returns the 128-bit product of x and y: (hi, lo) = x * y with the product bits' upper half returned in hi and the lower half returned in lo. This function's execution time does not depend on the inputs.

func Mul64(x, y uint64) (hi, lo uint64) {
	const mask32 = 1<<32 - 1
	x0 := x & mask32
	x1 := x >> 32
	y0 := y & mask32
	y1 := y >> 32
	w0 := x0 * y0
	t := x1*y0 + w0>>32
	w1 := t & mask32
	w2 := t >> 32
	w1 += x0 * y1
	hi = x1*y1 + w2 + w1>>32
	lo = x * y
	return
}

--- Full-width divide ---

Div returns the quotient and remainder of (hi, lo) divided by y: quo = (hi, lo)/y, rem = (hi, lo)%y with the dividend bits' upper half in parameter hi and the lower half in parameter lo. Div panics for y == 0 (division by zero) or y <= hi (quotient overflow).

func Div(hi, lo, y uint) (quo, rem uint) {
	if UintSize == 32 {
		q, r := Div32(uint32(hi), uint32(lo), uint32(y))
		return uint(q), uint(r)
	}
	q, r := Div64(uint64(hi), uint64(lo), uint64(y))
	return uint(q), uint(r)
}

Div32 returns the quotient and remainder of (hi, lo) divided by y: quo = (hi, lo)/y, rem = (hi, lo)%y with the dividend bits' upper half in parameter hi and the lower half in parameter lo. Div32 panics for y == 0 (division by zero) or y <= hi (quotient overflow).

func Div32(hi, lo, y uint32) (quo, rem uint32) {
	if y != 0 && y <= hi {
		panic(overflowError)
	}
	z := uint64(hi)<<32 | uint64(lo)
	quo, rem = uint32(z/uint64(y)), uint32(z%uint64(y))
	return
}

Div64 returns the quotient and remainder of (hi, lo) divided by y: quo = (hi, lo)/y, rem = (hi, lo)%y with the dividend bits' upper half in parameter hi and the lower half in parameter lo. Div64 panics for y == 0 (division by zero) or y <= hi (quotient overflow).

func Div64(hi, lo, y uint64) (quo, rem uint64) {
	const (
		two32  = 1 << 32
		mask32 = two32 - 1
	)
	if y == 0 {
		panic(divideError)
	}
	if y <= hi {
		panic(overflowError)
	}

	s := uint(LeadingZeros64(y))
	y <<= s

	yn1 := y >> 32
	yn0 := y & mask32
	un32 := hi<<s | lo>>(64-s)
	un10 := lo << s
	un1 := un10 >> 32
	un0 := un10 & mask32
	q1 := un32 / yn1
	rhat := un32 - q1*yn1

	for q1 >= two32 || q1*yn0 > two32*rhat+un1 {
		q1--
		rhat += yn1
		if rhat >= two32 {
			break
		}
	}

	un21 := un32*two32 + un1 - q1*y
	q0 := un21 / yn1
	rhat = un21 - q0*yn1

	for q0 >= two32 || q0*yn0 > two32*rhat+un0 {
		q0--
		rhat += yn1
		if rhat >= two32 {
			break
		}
	}

	return q1*two32 + q0, (un21*two32 + un0 - q0*y) >> s
}

Rem returns the remainder of (hi, lo) divided by y. Rem panics for y == 0 (division by zero) but, unlike Div, it doesn't panic on a quotient overflow.

func Rem(hi, lo, y uint) uint {
	if UintSize == 32 {
		return uint(Rem32(uint32(hi), uint32(lo), uint32(y)))
	}
	return uint(Rem64(uint64(hi), uint64(lo), uint64(y)))
}

Rem32 returns the remainder of (hi, lo) divided by y. Rem32 panics for y == 0 (division by zero) but, unlike Div32, it doesn't panic on a quotient overflow.

func Rem32(hi, lo, y uint32) uint32 {
	return uint32((uint64(hi)<<32 | uint64(lo)) % uint64(y))
}

Rem64 returns the remainder of (hi, lo) divided by y. Rem64 panics for y == 0 (division by zero) but, unlike Div64, it doesn't panic on a quotient overflow.

We scale down hi so that hi < y, then use Div64 to compute the rem with the guarantee that it won't panic on quotient overflow. Given that hi ≡ hi%y (mod y) we have hi<<64 + lo ≡ (hi%y)<<64 + lo (mod y)

	_, rem := Div64(hi%y, lo, y)
	return rem