bits package - math/bits

bits package - math/bits - Go Packages

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

Functions in this package may be implemented directly by the compiler, for better performance. For those functions the code in this package will not be used. Which functions are implemented by the compiler depends on the architecture and the Go release.

UintSize is the size of a uint in bits.

This section is empty.

func Add(x, y, carry uint) (sum, carryOut uint)

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.

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 33<<32 + 12
	n1 := []uint32{33, 12}
	// Second number is 21<<32 + 23
	n2 := []uint32{21, 23}
	// Add them together without producing carry.
	d1, carry := bits.Add32(n1[1], n2[1], 0)
	d0, _ := bits.Add32(n1[0], n2[0], carry)
	nsum := []uint32{d0, d1}
	fmt.Printf("%v + %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)

	// First number is 1<<32 + 2147483648
	n1 = []uint32{1, 0x80000000}
	// Second number is 1<<32 + 2147483648
	n2 = []uint32{1, 0x80000000}
	// Add them together producing carry.
	d1, carry = bits.Add32(n1[1], n2[1], 0)
	d0, _ = bits.Add32(n1[0], n2[0], carry)
	nsum = []uint32{d0, d1}
	fmt.Printf("%v + %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)
}

Output:

[33 12] + [21 23] = [54 35] (carry bit was 0)
[1 2147483648] + [1 2147483648] = [3 0] (carry bit was 1)

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 33<<64 + 12
	n1 := []uint64{33, 12}
	// Second number is 21<<64 + 23
	n2 := []uint64{21, 23}
	// Add them together without producing carry.
	d1, carry := bits.Add64(n1[1], n2[1], 0)
	d0, _ := bits.Add64(n1[0], n2[0], carry)
	nsum := []uint64{d0, d1}
	fmt.Printf("%v + %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)

	// First number is 1<<64 + 9223372036854775808
	n1 = []uint64{1, 0x8000000000000000}
	// Second number is 1<<64 + 9223372036854775808
	n2 = []uint64{1, 0x8000000000000000}
	// Add them together producing carry.
	d1, carry = bits.Add64(n1[1], n2[1], 0)
	d0, _ = bits.Add64(n1[0], n2[0], carry)
	nsum = []uint64{d0, d1}
	fmt.Printf("%v + %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)
}

Output:

[33 12] + [21 23] = [54 35] (carry bit was 0)
[1 9223372036854775808] + [1 9223372036854775808] = [3 0] (carry bit was 1)

func Div(hi, lo, y uint) (quo, rem uint)

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).

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).

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 0<<32 + 6
	n1 := []uint32{0, 6}
	// Second number is 0<<32 + 3
	n2 := []uint32{0, 3}
	// Divide them together.
	quo, rem := bits.Div32(n1[0], n1[1], n2[1])
	nsum := []uint32{quo, rem}
	fmt.Printf("[%v %v] / %v = %v\n", n1[0], n1[1], n2[1], nsum)

	// First number is 2<<32 + 2147483648
	n1 = []uint32{2, 0x80000000}
	// Second number is 0<<32 + 2147483648
	n2 = []uint32{0, 0x80000000}
	// Divide them together.
	quo, rem = bits.Div32(n1[0], n1[1], n2[1])
	nsum = []uint32{quo, rem}
	fmt.Printf("[%v %v] / %v = %v\n", n1[0], n1[1], n2[1], nsum)
}

Output:

[0 6] / 3 = [2 0]
[2 2147483648] / 2147483648 = [5 0]

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).

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 0<<64 + 6
	n1 := []uint64{0, 6}
	// Second number is 0<<64 + 3
	n2 := []uint64{0, 3}
	// Divide them together.
	quo, rem := bits.Div64(n1[0], n1[1], n2[1])
	nsum := []uint64{quo, rem}
	fmt.Printf("[%v %v] / %v = %v\n", n1[0], n1[1], n2[1], nsum)

	// First number is 2<<64 + 9223372036854775808
	n1 = []uint64{2, 0x8000000000000000}
	// Second number is 0<<64 + 9223372036854775808
	n2 = []uint64{0, 0x8000000000000000}
	// Divide them together.
	quo, rem = bits.Div64(n1[0], n1[1], n2[1])
	nsum = []uint64{quo, rem}
	fmt.Printf("[%v %v] / %v = %v\n", n1[0], n1[1], n2[1], nsum)
}

Output:

[0 6] / 3 = [2 0]
[2 9223372036854775808] / 9223372036854775808 = [5 0]

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

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("LeadingZeros8(%08b) = %d\n", 1, bits.LeadingZeros8(1))
}

Output:

LeadingZeros8(00000001) = 7

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("LeadingZeros16(%016b) = %d\n", 1, bits.LeadingZeros16(1))
}

Output:

LeadingZeros16(0000000000000001) = 15

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("LeadingZeros32(%032b) = %d\n", 1, bits.LeadingZeros32(1))
}

Output:

LeadingZeros32(00000000000000000000000000000001) = 31

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("LeadingZeros64(%064b) = %d\n", 1, bits.LeadingZeros64(1))
}

Output:

LeadingZeros64(0000000000000000000000000000000000000000000000000000000000000001) = 63

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

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("Len8(%08b) = %d\n", 8, bits.Len8(8))
}

Output:

Len8(00001000) = 4

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("Len16(%016b) = %d\n", 8, bits.Len16(8))
}

Output:

Len16(0000000000001000) = 4

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("Len32(%032b) = %d\n", 8, bits.Len32(8))
}

Output:

Len32(00000000000000000000000000001000) = 4

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("Len64(%064b) = %d\n", 8, bits.Len64(8))
}

Output:

Len64(0000000000000000000000000000000000000000000000000000000000001000) = 4

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.

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 0<<32 + 12
	n1 := []uint32{0, 12}
	// Second number is 0<<32 + 12
	n2 := []uint32{0, 12}
	// Multiply them together without producing overflow.
	hi, lo := bits.Mul32(n1[1], n2[1])
	nsum := []uint32{hi, lo}
	fmt.Printf("%v * %v = %v\n", n1[1], n2[1], nsum)

	// First number is 0<<32 + 2147483648
	n1 = []uint32{0, 0x80000000}
	// Second number is 0<<32 + 2
	n2 = []uint32{0, 2}
	// Multiply them together producing overflow.
	hi, lo = bits.Mul32(n1[1], n2[1])
	nsum = []uint32{hi, lo}
	fmt.Printf("%v * %v = %v\n", n1[1], n2[1], nsum)
}

Output:

12 * 12 = [0 144]
2147483648 * 2 = [1 0]

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 0<<64 + 12
	n1 := []uint64{0, 12}
	// Second number is 0<<64 + 12
	n2 := []uint64{0, 12}
	// Multiply them together without producing overflow.
	hi, lo := bits.Mul64(n1[1], n2[1])
	nsum := []uint64{hi, lo}
	fmt.Printf("%v * %v = %v\n", n1[1], n2[1], nsum)

	// First number is 0<<64 + 9223372036854775808
	n1 = []uint64{0, 0x8000000000000000}
	// Second number is 0<<64 + 2
	n2 = []uint64{0, 2}
	// Multiply them together producing overflow.
	hi, lo = bits.Mul64(n1[1], n2[1])
	nsum = []uint64{hi, lo}
	fmt.Printf("%v * %v = %v\n", n1[1], n2[1], nsum)
}

Output:

12 * 12 = [0 144]
9223372036854775808 * 2 = [1 0]

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("OnesCount(%b) = %d\n", 14, bits.OnesCount(14))
}

Output:

OnesCount(1110) = 3

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("OnesCount8(%08b) = %d\n", 14, bits.OnesCount8(14))
}

Output:

OnesCount8(00001110) = 3

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("OnesCount16(%016b) = %d\n", 14, bits.OnesCount16(14))
}

Output:

OnesCount16(0000000000001110) = 3

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("OnesCount32(%032b) = %d\n", 14, bits.OnesCount32(14))
}

Output:

OnesCount32(00000000000000000000000000001110) = 3

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("OnesCount64(%064b) = %d\n", 14, bits.OnesCount64(14))
}

Output:

OnesCount64(0000000000000000000000000000000000000000000000000000000000001110) = 3

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.

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.

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.

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

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%08b\n", 19)
	fmt.Printf("%08b\n", bits.Reverse8(19))
}

Output:

00010011
11001000

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%016b\n", 19)
	fmt.Printf("%016b\n", bits.Reverse16(19))
}

Output:

0000000000010011
1100100000000000

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%032b\n", 19)
	fmt.Printf("%032b\n", bits.Reverse32(19))
}

Output:

00000000000000000000000000010011
11001000000000000000000000000000

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%064b\n", 19)
	fmt.Printf("%064b\n", bits.Reverse64(19))
}

Output:

0000000000000000000000000000000000000000000000000000000000010011
1100100000000000000000000000000000000000000000000000000000000000

ReverseBytes returns the value of x with its bytes in reversed order.

This function's execution time does not depend on the inputs.

ReverseBytes16 returns the value of x with its bytes in reversed order.

This function's execution time does not depend on the inputs.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%016b\n", 15)
	fmt.Printf("%016b\n", bits.ReverseBytes16(15))
}

Output:

0000000000001111
0000111100000000

ReverseBytes32 returns the value of x with its bytes in reversed order.

This function's execution time does not depend on the inputs.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%032b\n", 15)
	fmt.Printf("%032b\n", bits.ReverseBytes32(15))
}

Output:

00000000000000000000000000001111
00001111000000000000000000000000

ReverseBytes64 returns the value of x with its bytes in reversed order.

This function's execution time does not depend on the inputs.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%064b\n", 15)
	fmt.Printf("%064b\n", bits.ReverseBytes64(15))
}

Output:

0000000000000000000000000000000000000000000000000000000000001111
0000111100000000000000000000000000000000000000000000000000000000

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.

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%08b\n", 15)
	fmt.Printf("%08b\n", bits.RotateLeft8(15, 2))
	fmt.Printf("%08b\n", bits.RotateLeft8(15, -2))
}

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%016b\n", 15)
	fmt.Printf("%016b\n", bits.RotateLeft16(15, 2))
	fmt.Printf("%016b\n", bits.RotateLeft16(15, -2))
}

Output:

0000000000001111
0000000000111100
1100000000000011

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%032b\n", 15)
	fmt.Printf("%032b\n", bits.RotateLeft32(15, 2))
	fmt.Printf("%032b\n", bits.RotateLeft32(15, -2))
}

Output:

00000000000000000000000000001111
00000000000000000000000000111100
11000000000000000000000000000011

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("%064b\n", 15)
	fmt.Printf("%064b\n", bits.RotateLeft64(15, 2))
	fmt.Printf("%064b\n", bits.RotateLeft64(15, -2))
}

Output:

0000000000000000000000000000000000000000000000000000000000001111
0000000000000000000000000000000000000000000000000000000000111100
1100000000000000000000000000000000000000000000000000000000000011

func Sub(x, y, borrow uint) (diff, borrowOut uint)

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.

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 33<<32 + 23
	n1 := []uint32{33, 23}
	// Second number is 21<<32 + 12
	n2 := []uint32{21, 12}
	// Sub them together without producing carry.
	d1, carry := bits.Sub32(n1[1], n2[1], 0)
	d0, _ := bits.Sub32(n1[0], n2[0], carry)
	nsum := []uint32{d0, d1}
	fmt.Printf("%v - %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)

	// First number is 3<<32 + 2147483647
	n1 = []uint32{3, 0x7fffffff}
	// Second number is 1<<32 + 2147483648
	n2 = []uint32{1, 0x80000000}
	// Sub them together producing carry.
	d1, carry = bits.Sub32(n1[1], n2[1], 0)
	d0, _ = bits.Sub32(n1[0], n2[0], carry)
	nsum = []uint32{d0, d1}
	fmt.Printf("%v - %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)
}

Output:

[33 23] - [21 12] = [12 11] (carry bit was 0)
[3 2147483647] - [1 2147483648] = [1 4294967295] (carry bit was 1)

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.

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	// First number is 33<<64 + 23
	n1 := []uint64{33, 23}
	// Second number is 21<<64 + 12
	n2 := []uint64{21, 12}
	// Sub them together without producing carry.
	d1, carry := bits.Sub64(n1[1], n2[1], 0)
	d0, _ := bits.Sub64(n1[0], n2[0], carry)
	nsum := []uint64{d0, d1}
	fmt.Printf("%v - %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)

	// First number is 3<<64 + 9223372036854775807
	n1 = []uint64{3, 0x7fffffffffffffff}
	// Second number is 1<<64 + 9223372036854775808
	n2 = []uint64{1, 0x8000000000000000}
	// Sub them together producing carry.
	d1, carry = bits.Sub64(n1[1], n2[1], 0)
	d0, _ = bits.Sub64(n1[0], n2[0], carry)
	nsum = []uint64{d0, d1}
	fmt.Printf("%v - %v = %v (carry bit was %v)\n", n1, n2, nsum, carry)
}

Output:

[33 23] - [21 12] = [12 11] (carry bit was 0)
[3 9223372036854775807] - [1 9223372036854775808] = [1 18446744073709551615] (carry bit was 1)

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

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("TrailingZeros8(%08b) = %d\n", 14, bits.TrailingZeros8(14))
}

Output:

TrailingZeros8(00001110) = 1

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("TrailingZeros16(%016b) = %d\n", 14, bits.TrailingZeros16(14))
}

Output:

TrailingZeros16(0000000000001110) = 1

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("TrailingZeros32(%032b) = %d\n", 14, bits.TrailingZeros32(14))
}

Output:

TrailingZeros32(00000000000000000000000000001110) = 1

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

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Printf("TrailingZeros64(%064b) = %d\n", 14, bits.TrailingZeros64(14))
}

Output:

TrailingZeros64(0000000000000000000000000000000000000000000000000000000000001110) = 1

This section is empty.