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

)funcmain() {

forx := 0; x < 100; x++ {

num := rand.Int()

ifnum&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.

funcmain() {

var auint8= 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`

.

funcmain() {

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

)funcmain() {

fmt.Println(procstr(“HELLO PEOPLE!”, LOWER|REV|CAP))

}funcprocstr(str string, conf byte) string {

// reverse string

rev :=func(s string) string {

runes := []rune(s)

n := len(runes)

fori := 0; i < n/2; i++ {

runes[i], runes[n-1-i] = runes[n-1-i], runes[i]

}

returnstring(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)

}

returnstr

}// Run on Go Playground

Function call `procstr(“HELLO PEOPLE!”, LOWER`

above will lower the cases for the string, reverse its order, and capitalize each word. This is done by setting the **|**REV**|**CAP)*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.

funcmain() {

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

funcmain() {

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`

:

Givennumberx,`^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`

.

funcmain() {

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

funcmain() {

vara 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).

funcmain() {

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

funcmain() {

a := 200

fmt.Printf(“%d\n”, a>>1)

}// prints:

100// Run on Playground

Or to multiply the value by 4:

funcmain() {

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`

.

funcmain() {

vara 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 n*th* bit is set in a value as demonstrated in the following snippet.

funcmain() {

vara 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 n*th* bit of a value. For instance, the following snippet unsets the third bit in variable `a`

.

funcmain() {

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