Bit Hacking with Go

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 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 this program in the Go 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 least significant bits 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 196because 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.

Update: couple of readers suggested the followings for the code above:

const (
    UPPER  = 1<<iota // upper case
    LOWER            // lower case
    CAP              // capitalizes
    REV              // reverses
)

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

Update: after feedback from another reader, here is the full definition of ^x:
Given number x, ^x = y ^ x where all bits in y = 1 for unsigned x or y = -1 for signed x.

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

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

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.

func main() {
    a := 200
    fmt.Printf(“%d\n”, a>>1)
}
// prints:
100
// Run on Playground

Or to multiply the value by 4:

func main() {
    a := 12
    fmt.Printf(“%d\n”, a<<2)
}
// prints:
48
// Run on 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 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 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 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 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.

As always, if you find this writeup useful, please let me know by clicking on the ♡ icon to recommend this post.

Also, don’t forget to checkout my book on Go, titled Learning Go Programming from Packt Publishing.