Difference between some operators "|", "^", "&", "&^". Golang

Question

Recently I read golang specification and faced with some interesting operators:

&    bitwise AND            integers
|    bitwise OR             integers
^    bitwise XOR            integers
&^   bit clear (AND NOT)    integers

I've tried to play with it, but the only one I have understood is that "|" add integers and "+" operator additionally work with floats, strings etc.

What they are used for in practice? Could anyone give some explanation about these 4 operators above?

Solution 1

Bitwise operators come into play when you have to work with byte- or bit-level data.

Here I list a handful of examples using bit operations with code samples (in no particular order):

---

1. They are common and part of many algorithms in cryptography and hash functions (e.g. MD5).

2. They are also often used if you want to "save" space and you pack multiple "bool" variables into one int for example, you assign a bit to each bool variable. You have to use bitwise operators to be able to individually change/read the bits.

For example packing 8 bits/bools into one int:

flags := 0x00  // All flags are 0
flags |= 0x02  // Turn the 2nd bit to 1 (leaving rest unchanged)
flags |= 0xff  // Turn 8 bits (0..7) to 1
flags &= 0xfe  // Set the lowest bit to 0 (leaving rest unchanged)

istrue := flags&0x04 != 0 // Test if 3rd bit is 1

3. Another area is compressing data where you want to get the most out of a byte and use all its bits to store/retreive some info (a bit is the basic unit of information in computing and digital communications).

4. Similar to compression but not quite the same: bitstreams. It is also used to save space in a data stream by not sending complete bytes but rather fields having arbitrary bit-length.

I've written and published a highly optimized bit-level Reader and Writer package, open sourced here: github.com/icza/bitio. You will see extensive usage of all kinds of bit operations in its sources.

5. Another practical usage: testing certain properties of an (integer) number. Knowing the binary representation of integer numbers (Two's complement) there are certain characteristics of numbers in their binary representation. For example an integer number (in 2's complement) is even (can be divided by 2) if the lowest bit is 0:

func isEven(i int) bool {
    return i&0x01 == 0
}

By testing the bits of an integer you can also tell if it's a power of 2. For example if a positive number only contains one 1 bit, then it is a power of 2 (e.g. 2 = 0x02 = 00000010b, 16 = 0x10 = 00010000 but for example 17 = 0x11 = 00010001 not power of 2).

6. Many encoding/decoding procedures also use bit operations. The most trivial is the UTF-8 encoding which uses a variable-length encoding for representing unicode code points (rune in Go) as byte sequences.
A simple variation of a variable-length encoding could be to use the highest bit of a byte (8th or 7th if 0-indexed) to signal if more bytes are required to decode a number, and the remaining 7 bits are always the "useful" data. You can test the highest bit and "separate" the 7 useful bits like this:

b := readOneByte()
usefulBits := b & 0x7f
hasMoreBytes := b & 0x80 != 0

The profit of using such a variable-length encoding is that even if you use uint64 type in Go which is 8 bytes in memory, small numbers can still be represented using less bytes (numbers in the range 0..127 only require 1 byte!). If the samples you want to store or transfer have many small values, this alone can compress the data to 1/8th = 12.5 %. The down side is that big numbers (which have bits even in the highest byte) will use more than 8 bytes. Whether it's worth it depends on the heuristic of the samples.

X. And the list goes on...

---

Can you live without knowing/using bitwise operators in Go (and in many other programming languages)? The answer is Yes. But if you know them, sometimes they can make your life easier and your programs more efficient.

If you want to learn more on the topic, read the Wikipedia article: Bitwise operation and google the term "Bitwise Operators Tutorial", there are many good articles.

Solution 2

For what they technically do check out the comments in this

package main

import "fmt"

func main() {
    // Use bitwise OR | to get the bits that are in 1 OR 2
    // 1     = 00000001
    // 2     = 00000010
    // 1 | 2 = 00000011 = 3
    fmt.Println(1 | 2)

    // Use bitwise OR | to get the bits that are in 1 OR 5
    // 1     = 00000001
    // 5     = 00000101
    // 1 | 5 = 00000101 = 5
    fmt.Println(1 | 5)

    // Use bitwise XOR ^ to get the bits that are in 3 OR 6 BUT NOT BOTH
    // 3     = 00000011
    // 6     = 00000110
    // 3 ^ 6 = 00000101 = 5
    fmt.Println(3 ^ 6)

    // Use bitwise AND & to get the bits that are in 3 AND 6
    // 3     = 00000011
    // 6     = 00000110
    // 3 & 6 = 00000010 = 2
    fmt.Println(3 & 6)  

    // Use bit clear AND NOT &^ to get the bits that are in 3 AND NOT 6 (order matters)
    // 3      = 00000011
    // 6      = 00000110
    // 3 &^ 6 = 00000001 = 1
    fmt.Println(3 &^ 6)
}

View it on the playground

Please note that I gave two examples of | to show that it's not really addition like 1 + 5.

As for practical uses I'm sure some others could comment with more examples but one common use is to create a bitmask of flags for something like a permission system.

Comments

[Lee Daniel Crocker]

Grab a book like Petzold's "Code" to get a basic understanding of binary representation and the foundations of computing.

[Timur Fayzrakhmanov]

Thank you! Really good answer. Could you suggest the book, that explain some basics of "low level" programming for newbie like me? (without deepening into too technical and mathematical terms)

[icza]

@TimurFayzrakhmanov Just google it (the term "bitwise operators tutorial"), there are many good tutorials on the internet. Most are language specific but more or less they apply to all programming languages. Here is a good one found in 1 minute googling: Understanding Bitwise Operators. Also read the wikipedia article: Bitwise operation

[RayfenWindspear]

Umm... your isOdd() function actually returns true if the number is even. isOdd should check for == 1

[icza]

@RayfenWindspear You're right. I mixed up the words odd and even. Corrected it.