For large data sets, storing information in single bits can reduce space requirements. But accessing, and counting, this information is more complex.
In the math bits package, we find some helpful methods for bitwise operations in Go. With OnesCount
we have a population count (popcnt).
OnesCount
The bits.OnesCount
method performs a population count (a bitcount) on a uint
. We must first cast a value like an int
to a uint
to use OnesCount
.
int
and smaller data types like int16
, casting to a uint
will not change the bit count result.package main import ( "math/bits" "fmt" ) func main() { value := 100 // Must cast to uint for OnesCount. result := bits.OnesCount(uint(value)) fmt.Println(result) }3
UintSize
, constantHow many bits are in a uint
in the Go language? We can determine this number with the bits.UintSize
constant.
package main import ( "math/bits" "fmt" ) func main() { // Use constant to determine bits in a uint. fmt.Println("BITS IN UINT:", bits.UintSize) }BITS IN UINT: 64
We have found that a uint
has 64 bits. With bitwise operators, we can display each individual bit as 1 or 0. We use a for
-loop for this example.
OnesCount
for 100 should be 3.package main import ( "math/bits" "fmt" ) func main() { value := uint(100) // Loop over all bits in the uint. for i := 0; i < bits.UintSize; i++ { // If there is a bit set at this position, write a 1. // ... Otherwise write a 0. if value & (1 << uint(i)) != 0 { fmt.Print("1") } else { fmt.Print("0") } } }0010011000000000000000000000000000000000000000000000000000000000
TrailingZeros
It is possible to loop over a uint
and call TrailingZeros
. This lets us iterate through set bits, ignoring bits that are not set.
for
-loop until our value is 0 (this means all bits have been set to 0).TrailingZeros
gives us index of a set bit. We can erase the bit (set it to zero) so that the next call will find the next bit.for
-loop over the bits.package main import ( "math/bits" "fmt" ) func main() { value := uint(100) count := 0 // Continue looping until we are zero. for value != 0 { // Use trailing zeros in our bit count method. index := bits.TrailingZeros(value) // Print the bit set at this index. fmt.Println("Bit set at:", index) // Erase the bit. value &= ^(1 << uint(index)) // Count it. count++ } fmt.Println("Count:", count) }Bit set at: 2 Bit set at: 5 Bit set at: 6 Count: 3
From the Go language specification, we can find a reference table of the bitwise operators available. We use a caret ("^") instead of a tilde ("~") for NOT.
& bitwise AND | bitwise OR ^ bitwise XOR &^ bit clear (AND NOT) << left shift >> right shift
For things like bitcounts, more advanced algorithms (such as ones that use lookup tables) may have performance benefits. Bits.OnesCount
is simpler to use in programs.
The math bits package was not in early versions of the Go installation. It was added in Go 1.9. This is a useful package for low-level operations.