In the good old days of computing when memory was expensive and processing power was at premium, hacking on bits directly was the preferred (in some cases the only) way to process information. Today, direct bit manipulation is still crucial in many computing use cases such as low-level system programming, image processing, cryptography, etc.
The Go programming language supports several bitwise operators including the followings:
& bitwise AND
| bitwise OR
^ bitwise XOR
&^ AND NOT
<< left shift
>> right shift
The remainder of this writeup provides a detail discussion of each operator and include examples how they can be used.
The & Operator
In Go, the & operator performs the bitwise AND operation between two integer operands. Recall that the AND operation has the following properties:
Given operands a, b
AND(a, b) = 1; only if a = b = 1
else = 0
The AND operator has the nice side effect of selectively clearing bits of an integer value to zero. For instance, we can use the & operator to clear (set to zero) the last 4 least significant bits (LSB) to all zeros.
func main() {
var x uint8 = 0xAC // x = 10101100
x = x & 0xF0 // x = 10100000
}
All binary operators support the short-hand compound assignment form. For instance, the previous example can be re-written as follows.
func main() {
var x uint8 = 0xAC // x = 10101100
x &= 0xF0 // x = 10100000
}
Another neat trick you can do with & operator is to test whether a number is odd or even. This works because a number is odd when its least significant bit is set (equal 1). We can use the & operator apply a bitwise AND operation to an integer the value of 1. If the result is 1, then the original number is odd.
import (
"fmt"
"math/rand"
)
func main() {
for x := 0; x < 100; x++ {
num := rand.Int()
if num&1 == 1 {
fmt.Printf("%d is odd\n", num)
} else {
fmt.Printf("%d is even\n", num)
}
}
}
Run on the Playground.
The | Operator
The | performs a bitwise OR operation on its integer operands. Recall the OR operator has the following properties:
Given operands a, b
OR(a, b) = 1; when a = 1 or b = 1
else = 0
We can use the nature of the bitwise OR operator to selectively set individual bits for a given integer. For instance, in the following example we use the OR operator to set (from least to most significant bits (MSB)) the 3rd, 7th, and 8th bit to 1.
func main() {
var a uint8 = 0
a |= 196
fmt.Printf("%b", a)
}
// prints 11000100
^^ ^
Run on Playground.
Using OR is quite useful when doing bit masking techniques to set arbitrary bits for a given integer value. For instance, we can expand the previous program to set more bits in the value stored in variable a.
func main() {
var a uint8 = 0
a |= 196
a |= 3
fmt.Printf("%b", a)
}
// prints 11000111
Run on Playground.
The previous program, not only has the bits for decimal 196 set, it also has the the last 2 LSBs set for decimal value 3. We can continue on (OR'ing values) until all bit fields in the integer value are set.
Bits as Configuration
Now, recall that AND(a, 1) = a if and only if a = 1. We can use that fact to query a value for its set bits. For instance, from the code above a & 196 will return 196 because the bits for that value are indeed set in a. So we can combine the use of the OR and the AND as a way of specifying configuration values and reading them respectively.
The following source code snippet shows this at work. Function procstr transforms the content of a string. It takes two parameters: the first parameter, str, is the string to be transformed and the second parameter, conf, is an integer used to specify multiple transformation configurations using bit masking.
const (
UPPER = 1 // upper case
LOWER = 2 // lower case
CAP = 4 // capitalizes
REV = 8 // reverses
)
func main() {
fmt.Println(procstr("HELLO PEOPLE!", LOWER|REV|CAP))
}
func procstr(str string, conf byte) string {
// reverse string
rev := func(s string) string {
runes := []rune(s)
n := len(runes)
for i := 0; i < n/2; i++ {
runes[i], runes[n-1-i] = runes[n-1-i], runes[i]
}
return string(runes)
}
// query config bits
if (conf & UPPER) != 0 {
str = strings.ToUpper(str)
}
if (conf & LOWER) != 0 {
str = strings.ToLower(str)
}
if (conf & CAP) != 0 {
str = strings.Title(str)
}
if (conf & REV) != 0 {
str = rev(str)
}
return str
}
Run on Go Playground.
Function call procstr("HELLO PEOPLE!", LOWER|REV|CAP) above will lower the cases for the string, reverse its order, and capitalize each word. This is done by setting the 2nd, 3rd, and 4th bits, of parameter conf, for a value of 14. The code then uses the successive if-statement blocks to extract those bits and apply the proper string transformation.
The ^ Operator
The XOR operator is applied using ^ in Go. The XOR, exclusive OR, has the following properties:
Given operands a, b
XOR(a, b) = 1; only if a != b
else = 0
The implication of this definition is that XOR can be used to toggle bits from one value to another. For instance, given a 16-bit value, we can toggle the first eight bits (starting from the MSB) using the following code.
func main() {
var a uint16 = 0xCEFF
a ^= 0xFF00 // same a = a ^ 0xFF00
}
// a = 0xCEFF (11001110 11111111)
// a ^=0xFF00 (00110001 11111111)
In the previous snippet, the bits that are XOR'd with 1 are flipped (going from 0 to 1 or from 1 to 0). One practical use of XOR, for instance, is to compare sign magnitudes. Two integers a, b have the same signs when (a ^ b) ≥ 0 (or (a ^ b) < 0 for opposite sign) is true as shown in the following program:
func main() {
a, b := -12, 25
fmt.Println("a and b have same sign?", (a ^ b) >= 0)
}
Run on the Go Playground.
When the previous program is executed, it will print: a and b have same sign? false. Use the Go Playground link to change the signs of the numbers to see different results.
^ as Bitwise Complement (NOT)
Unlike other languages (c/c++, Java, Python, Javascript, etc), Go does not have a dedicated unary bitwise complement operator. Instead, the XOR operator, ^, can also be used as a unary operator to apply one's complement to a number. Given bit x, in Go ^x = 1 ^ x which reverses the bit. We can see this in action in the following snippet which uses ^a to take the complement of variable a.
func main() {
var a byte = 0x0F
fmt.Printf("%08b\n", a)
fmt.Printf("%08b\n", ^a)
}
// prints
00001111 // var a
11110000 // ^a
Run on the Playground.
The &^ Operator
The &^ operator, reads as AND NOT, is a short-hand form that applies the AND and the NOT operations to its operands as shown in the following definition.
Given operands a, b
AND_NOT(a, b) = AND(a, NOT(b))
This has the interesting property of clearing the bits in the first operand if the second operand is 1 as defined here:
AND_NOT(a, 1) = 0; clears a
AND_NOT(a, 0) = a;
The next code snippet uses the AND NOT operator to clear the last four LSBs in variable a from 1010 1011 to 1010 0000.
func main() {
var a byte = 0xAB
fmt.Printf("%08b\n", a)
a &^= 0x0F
fmt.Printf("%08b\n", a)
}
// prints:
10101011
10100000
Run on the Playground.
The << and >> Operators
Similar to other C-derived languages, Go uses << and >> to represent the left and the right shift operators respectively as defined as below:
Given integer operands a and n,
a << n; shifts all bits in a to the left n times
a >> n; shifts all bits in a to the right n times
For instance, in the following snippet the left shift operator is used to shift the value stored in a (00000011) three times to the left. Each time the result is printed for illustrative purpose.
func main() {
var a int8 = 3
fmt.Printf("%08b\n", a)
fmt.Printf("%08b\n", a<<1)
fmt.Printf("%08b\n", a<<2)
fmt.Printf("%08b\n", a<<3)
}
// prints:
00000011
00000110
00001100
00011000
Run on Playground.
Notice that with each shift, the LSB on the right is zero-filled. Inversely, using the right shift operator each bit in a value can shift to the right with the MSB zero-filled on the left as shown in the following example (signed numbers has an exception, see the Note on Arithmetic Shifts below).
func main() {
var a uint8 = 120
fmt.Printf("%08b\n", a)
fmt.Printf("%08b\n", a>>1)
fmt.Printf("%08b\n", a>>2)
}
// prints:
01111000
00111100
00011110
Run on the Playground.
Some of the simplest tricks that can be done with the left and right shift operators are the multiplication and division where each shift position represents a power of two. For instance, the following divides 200 (stored in a) by 2 with a right shift.
func main() {
a := 200
fmt.Printf("%d\n", a>>1)
}
// prints:
100
Run on the Playground.
Or to multiply the value by 4, left shift by 2:
func main() {
a := 12
fmt.Printf("%d\n", a<<2)
}
// prints:
48
Run on the Playground.
The shift operators provides interesting ways to manipulate bits at designated position in a binary value. For instance, in the following snippet, the | and << operators are used to set the 3rd bit in variable a.
func main() {
var a int8 = 8
fmt.Printf("%08b\n", a)
a = a | (1<<2)
fmt.Printf("%08b\n", a)
}
// prints:
00001000
00001100
Run on the Playground.
Or you can combine the shift and the & operators to test if nth bit is set in a value as demonstrated in the following snippet.
func main() {
var a int8 = 12
if a&(1<<2) != 0 {
fmt.Println("take action")
}
}
// prints:
take action
Run on the Playground.
Using the &^ and the shift operators, we can unset the nth bit of a value. For instance, the following snippet unsets the third bit in variable a.
func main() {
var a int8 = 13
fmt.Printf("%04b\n", a)
a = a &^ (1 << 2)
fmt.Printf("%04b\n", a)
}
// prints:
1101
1001
Run on the Playground.
A Note on Arithmetic Shifts
When the value to be shifted (the left operand) is a signed value, Go automatically apply arithmetic shifts. During a right shift operation, the (two's complement) sign bit is copied (or extended) to fill the shifted slots.
Conclusion
As with other modern languages, Go supports all bitwise operators. This writeup only provided an small sample of the sorts of bit hacks that can be done with these operators. You can find a lot more recipes online, specifically from Bit Twiddling Hacks by Sean Eron Anderson.
Follow Vladimir on Twitter @vladimirvivien!
If you are learning Go, checkout Vladimir Vivien's book on Go, titled Learning Go Programming from Packt Publishing.
This post was originally published on Medium by its author Vladimir Vivien as Bit Hacking with Go.
Top comments (4)
A note on 'Bits as Configuration' - instead of assigning the values 1, 2, 4 & 8 manually you can use iota.
Makes it easier to reorder and introduce new flags.
Markus, yes thanks for pointing that out.
Thanks Vladimir for this overview!
I have 2 comments:
thanks again,
Dieter
Hi Dieter,
Thanks for taking time to read and asking questions.