The Power of Bitwise Operations

This year, the rust-dd team decided to solve the Advent of Code challenges entirely in Rust. This blog post was inspired by the first part of Day 7’s challenge.

Problem of Day 7 Part 1

The task involves equations where numbers are missing operators (+ or *). For each equation, you must determine if inserting operators can yield the given target value.

For example, in the equation 190: 10 19, placing * between the numbers gives 10 * 19 = 190, which matches the target value. The goal is to identify solvable equations and sum their target values.

You can follow our progress and solutions here:
➡️ Advent of Code 2024 in Rust

Short Summary About the Results

Bitwise operations might not be part of a programmer’s daily toolkit, but when the situation calls for them, they can be incredibly powerful. One of my favorite YouTubers, Chris Biscardi, streams his Advent of Code solutions daily on YouTube. For Day 7’s challenge (link to the video), he demonstrates how long the code runs and explores how Rayon enables parallel execution.

In his implementation:

A single-threaded iterator-based solution for Part 1 runs in 10.57 ms.
Using Rayon to parallelize the solution brings it down to 2.441 ms.

In contrast, the bitwise-based approach we showcase here runs in just 0.001475209 µs (or 1.4752 ns) on a single thread! Imagine the possibilities if we parallelized this further.

We’d like to take a moment to thank Chris Biscardi and other content creators in the Rust community. Their educational and inspiring content motivates the community—including us at rust-dd—to constantly push the boundaries of what’s possible with Rust.

Why Bitwise Operations?

While there are many solutions available online, we chose to approach this problem using bitwise operations. Bitwise operations allow memory manipulation at the bit level, enabling extraordinary performance in specific cases. In this task, bitwise operations were both justified and effective. Before jumping to conclusions about overengineering, let’s explore the solution step by step:

let input = fs::read_to_string("./inputs/day07.txt").expect("Failed to read input file");
let data: IResult<&str, Vec<(u64, Vec<u64>)>, nom::error::Error<&str>> = separated_list1(
    line_ending,
    separated_pair(
        complete::u64,
        tag(": "),
        separated_list1(space1, complete::u64),
    ),
)(input.as_str());
let (_, data) = data.unwrap();

// A.
let mut result = 0;

for (left, right) in &data {
    let len = right.len();

    if len < 1 {
        continue;
    }

    // Test every combination of add/mul between the right side
    // All combinations are 2^(len - 1)
    for i in 0..(1 << (len - 1)) {
        let mut sum = right[0];

        for j in 0..(len - 1) {
            if i & (1 << j) != 0 {
                sum += right[j + 1];
            } else {
                sum *= right[j + 1];
            }
        }

        if &sum == left {
            result += left;
            break;
        }
    }
}

Step-by-Step Explanation

Loading the Input
The task input is read from a file and parsed into a data structure. Each line of the input corresponds to an equation:
- The number on the left (before the colon) is the target value.
- The numbers on the right are stored in a vector to represent operands.
Generating Combinations
```
for i in 0..(1 << (len - 1)) {
```
Here, 1 << (len - 1) generates all possible combinations of operators between the numbers on the right side. For example, if the right vector has 3 elements (len = 3), there are 2^(3 - 1) = 4 combinations:
- 00 (binary for 0): Multiply both pairs.
- 01 (binary for 1): Multiply the first pair, add the second.
- 10 (binary for 2): Add the first pair, multiply the second.
- 11 (binary for 3): Add both pairs.
Each bit in the binary representation of i represents whether to add (1) or multiply (0) at that position.
Applying Operators with Bit Masking
```
if i & (1 << j) != 0 {
    sum += right[j + 1];
} else {
    sum *= right[j + 1];
}
```
Here’s how the code works step by step:
- 1 << j: Creates a bit mask with the 1 at the position j.
  - For example:
    - 1 << 0 = 0001 (binary), corresponding to the first bit.
    - 1 << 1 = 0010 (binary), corresponding to the second bit.
    - 1 << 2 = 0100 (binary), corresponding to the third bit.
- i & (1 << j): Checks if the j-th bit of i is 1 (add) or 0 (multiply). This is done with the bitwise AND operator:
  - If i & (1 << j) != 0, it means the j-th bit of i is 1, so addition is performed.
  - Otherwise, multiplication is performed.
Why use AND and bit shifts together?
- The combination of AND and bit shifts allows us to efficiently isolate and evaluate specific bits in the binary representation of i.
- This ensures we can systematically test every possible combination of addition and multiplication for the given numbers.

Example Walkthrough

For the equation 292: 11 6 16 20:

right = [11, 6, 16, 20], len = 4.
Total combinations: 2^(4 - 1) = 8 (binary 000 to 111).

Here are the 8 combinations in binary form and how they are evaluated:

Binary (i)	Operations	Calculation	Result
`000`	`* * *`	`11 * 6 * 16 * 20`	21120
`001`	`* * +`	`11 * 6 * 16 + 20`	1060
`010`	`* + *`	`11 * 6 + 16 * 20`	3940
`011`	`* + +`	`11 * 6 + 16 + 20`	106
`100`	`+ * *`	`11 + 6 * 16 * 20`	19211
`101`	`+ * +`	`11 + 6 * 16 + 20`	292
`110`	`+ + *`	`11 + 6 + 16 * 20`	327
`111`	`+ + +`	`11 + 6 + 16 + 20`	53

For i = 5 (binary 101):

sum = 11.
j = 0: i & (1 << 0) is 1 (101 & 001), so sum += 6 → sum = 17.
j = 1: i & (1 << 1) is 0 (101 & 010), so sum *= 16 → sum = 272.
j = 2: i & (1 << 2) is 1 (101 & 100), so sum += 20 → sum = 292.

This matches the target value (292), so the equation is valid, and 292 is added to the result.

Conclusion

Bitwise operations, combined with efficient parsing and logical structures, provide an elegant and high-performance solution to problems like these. They allow systematic iteration through possibilities while keeping the code both compact and readable. This example highlights how even seemingly small optimizations, like bit masking, can significantly impact performance.