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.
fmt.Println(bits.OnesCount(255)) // 8
Try it
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.
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
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.
Lenis the floor of log2 plus one.bits.Len(n) - 1isfloor(log2 n)forn > 0;1 << bits.Len(n-1)rounds up to the next power of two forn > 1.- Lowest set bit:
x & -xisolates it andbits.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. Add64chains build arbitrary-size addition: pass the carry of one limb into the next, which is howmath/bigworks.- Portability: results do not depend on the platform except
UintSizeand the width ofuint. - Hash functions and CRC code use
RotateLeftconstantly; it is recognized by the compiler as a rotate instruction.
Related
- Bitwise operators, Shift operators,
math,math/big - Lessons: Operators, Numbers