## DEV Community is a community of 850,636 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

protium

Posted on

# Advent of code: Rust, Go, and Binary operators

Hi everyone, I got late into the advent of code problems and currently I'm solving day 3 and 4.
I've been writing my solutions in `rust` and `go` (see my aoc repo), and today, while solving day 03 I came across with an interesting comparison between rust and go code that I'd like to share in this post.

## The problem: Binary Diagnostic

The solution to the problem can be found with array/slice methods: filter, map and reduce and bitwise operators. For the first part of the problem I knew that I would need to calculate the complement of a number applying the NOT operator to the `gamma rate` value so I could get the `epsilon rate`.

Let's compare both solutions:

``````fn part_one() -> i32 {
.lines()
.map(|l| {
l.unwrap()
.chars()
.map(|c| (c as u8 - b'0') as i32)
.collect()
})
.collect();
let cols = data[0].len();
let half = data.len() as i32 / 2;
let gama_rate = data
.iter()
.fold(vec![0; cols], |mut v, line| {
for i in 0..cols as usize {
v[i] += line[i]
}
v
})
.iter()
.map(|d| if *d > half { 1 } else { 0 })
.fold(0, |acc, d| (acc << 1) + d);
gama_rate * (!gama_rate << (32 - cols) >> (32 - cols))
}
``````
``````func day03_partOne() uint32 {
file, _ := os.Open("data/day_03.test")
defer file.Close()

scanner := bufio.NewScanner(file)
lineCount := uint(0)
var columnSums []uint
for scanner.Scan() {
line := scanner.Text()
if columnSums == nil {
columnSums = make([]uint, len(line))
}
for i, c := range line {
columnSums[i] += uint(c - '0')
}
lineCount += 1
}
gamaRate := uint32(0)
for _, s := range columnSums {
gamaRate = gamaRate << 1
if s > lineCount/2 {
gamaRate += 1
}
}
colShift := 32 - len(columnSums)
return gamaRate * (^gamaRate << colShift >> colShift)
}
``````

Worth to mention: I coded the `rust` solution first.
At first glance, both solutions seem to have the same amount of code, but one solution performs less operations than the other. In the `rust` solution I used array/vector methods to reduce and map the bits into decimal numbers having the total sum of each column. Whereas in `go`, and since `go` is is not a functional language I had to use the good old for loops. This "constraint" made me rethink the solution I already had working with `rust` and thus reduced the auxiliary space. For the time complexity we can see that in rust we do a few more iterations than in `go` over the data due to the usage of `map` and `fold` functions.

## Analisys

In the `rust` code, we can identify these steps:

• Transform the input into a 2D vector of integers, transforming line by line.
• Reduce the matrix to a a vector where each item is the sum of each column
• Transform the vector to a vector of 1 and 0's. For each item, set 1 if the sum is greater than half of the number of row (this is basically checking if 1 is the most common bit in each column). Else, set it to 0. At this point we are left with a binary number.
• Transform the binary number into a decimal number
• Calculate the `epsilon rate` by getting the complement of the `gamma rate`.

Note: Rust uses the two’s complement to find the bitwise negation for signed types. Rust’s signed integer types are called the signed two’s complement integer types.

For the `go` code our steps are:

• Iterate each line of text
• For each line start adding up the sum of each column by converting string to int.
• Iterate over the columns and start converting the binary number to decimal. Note: we actually calculate each bit of the binary number in each loop and store it into an uint32 variable. More on that later.
• Calculate the `epsilon rate` by getting the complement of the `gamma rate`.

At this point I was more satisfied with my `go` solution.

## Bitwise operations

Let's analyze what exactly is going on in the last line of each solution.
Let's first consider our data types. When using bitwise operators we can only use unsigned integers. As noted before, `rust` handles this for us when working with i32. For `go` I explicitly used `uint32`.
So now we want to calculate the complement, this is done with the `NOT` operator. `rust` uses `!` whereas `go` doesn't have the unary operator but it can be replaced with the `XOR` operator `^` (nicely explained here). Let's assume our `game rate` is 11, which is `1011`. But since our data container has 32 bits this will actually be `00000000 0000000 00000000 00001011`. See the problem? If we get the compliment of this number, we will get the complement for the for all the bits and this will not be the complement of 11. Our number looks like this:

``````11111111 11111111 11111111 11111100
``````

In order to solve this problem, we need to bit shift the bits in the number 32 - cols times to the left, losing the most significant bits. At this point our number looks like this:

``````01000000 0000000 00000000 00000000
``````

If we now shift 32 - cols bits to the right, the least significant bits are lost and zeros are inserted. Now our number looks like:

``````00000000 0000000 00000000 00000100
``````

So now our decimal value is 4, our `epsilon rate`.

What are your thoughts on this solutions?