Skip to content
Tutorials Center
My learning

Topics

Go Reference ยท Time, Math and Randomness

Go math/bits package

Reference for Go math/bits: OnesCount, LeadingZeros, TrailingZeros, Len, Reverse, RotateLeft, Add64 and Mul64 for fast low-level bit manipulation.

The package math/bits has functions for working with the individual bits of unsigned integers: counting set bits, finding the highest or lowest set bit, reversing and rotating bits, and doing arithmetic with carries. The compiler turns most of these into single CPU instructions, so they are both convenient and fast.

Functions come in sizes: no suffix works on uint (32 or 64 bits depending on the platform), and the suffixes 8, 16, 32 and 64 work on uint8 to uint64.

Go
fmt.Println(bits.OnesCount(255)) // 8

Try it

Go Counting and locating bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

Go Reversing, rotating and carries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

Syntax

Go
const UintSize = 32 or 64

func OnesCount64(x uint64) int
func LeadingZeros64(x uint64) int
func TrailingZeros64(x uint64) int
func Len64(x uint64) int
func Reverse64(x uint64) uint64
func ReverseBytes64(x uint64) uint64
func RotateLeft64(x uint64, k int) uint64
func Add64(x, y, carry uint64) (sum, carryOut uint64)
func Sub64(x, y, borrow uint64) (diff, borrowOut uint64)
func Mul64(x, y uint64) (hi, lo uint64)
func Div64(hi, lo, y uint64) (quo, rem uint64)
Function Result
OnesCount Number of 1 bits (population count).
LeadingZeros Zero bits above the highest set bit. The full width for 0.
TrailingZeros Zero bits below the lowest set bit. The full width for 0.
Len Minimum bits needed to represent x; 0 for 0.
Reverse / ReverseBytes Reverse the bit order / the byte order (endianness swap).
RotateLeft Rotate left by k; a negative k rotates right.
Add, Sub, Mul, Div Arithmetic with carry, borrow or 128-bit operands.

Panics: Div panics on division by zero, and also on overflow, which happens when y <= hi. Rem64 returns only the remainder and never panics on overflow.

Usage notes

  • Unsigned only. To use these on signed values, convert to the unsigned type of the same width first; the bit pattern is preserved.
  • Len is the floor of log2 plus one. bits.Len(n) - 1 is floor(log2 n) for n > 0; 1 << bits.Len(n-1) rounds up to the next power of two for n > 1.
  • Lowest set bit: x & -x isolates it and bits.TrailingZeros(x) gives its index.
  • Plain operators &, |, ^, &^, << and >> cover masking and shifting; use this package for counting, locating, reversing and multiword arithmetic. See bitwise operators and shifts.
  • Add64 chains build arbitrary-size addition: pass the carry of one limb into the next, which is how math/big works.
  • Portability: results do not depend on the platform except UintSize and the width of uint.
  • Hash functions and CRC code use RotateLeft constantly; it is recognized by the compiler as a rotate instruction.