Secret Handshake: Solving an exercise using bitwise operators and comparing performance

A couple of days ago, I took on an interesting task on Exercism. You can find the full description here. The goal is to create a function that takes a number between 1 and 31 and converts it to a list of actions. The sequence is defined by the five rightmost digits of the number when converted to binary. If you're unfamiliar with the binary system, I recommend reading this explanation first.

In this post, I'll discuss how I gradually improved my initial solution and share some interesting findings about the performance of different approaches.

Given

Here are possible actions in binary form:

00001 = wink
00010 = double blink
00100 = close your eyes
01000 = jump
10000 = reverse the order of the operations

Let's consider the input number as 5. Then, the expected action list is "wink, close your eyes", since 5 is 00101 in binary form.

0010|1| = 5
0000|1| = wink - the input number has 1 in the same column, so we add the action

001|0|1 = 5
000|1|0 = double blink - the input number has 0 in the same column, so skip the action

00|1|01 = 5
00|1|00 = close your eyes - the input number has 1 in the same column, so add the action

0|0|101 = 5
0|1|000 = jump - the input number has 0 in the same column, so skip the action

|0|0101 = 5
|1|0000 = reverse the order of the operations - the input number has 0 in the same column, so skip the action

I assume that not all software developers regularly work with binary numbers in high-level languages like Java, let alone test engineers like me. Naturally, I wasn't even aware of the tools I could use.

My approach

Before discussing alternative solutions, let's examine my first attempt and enhance it a little. I do dare to say that it's not perfect.

List<Signal> calculateHandshake(int number) {
    List<Signal> signals = new ArrayList<>();
    String binaryString = "0000" + Integer.toBinaryString(number);

    int wink = binaryString.length() - 1;
    int doubleBlink = binaryString.length() - 2;
    int closeYourEyes = binaryString.length() - 3;
    int jump = binaryString.length() - 4;
    int reverse = binaryString.length() - 5;

    for (int i = binaryString.length() - 1; i >= 0 && i >= reverse; i--) {
        if (binaryString.charAt(i) != '1') {
            continue;
        }

        if (i == wink) {
            signals.add(Signal.WINK);
        } else if (i == doubleBlink) {
            signals.add(Signal.DOUBLE_BLINK);
        } else if (i == closeYourEyes) {
            signals.add(Signal.CLOSE_YOUR_EYES);
        } else if (i == jump) {
            signals.add(Signal.JUMP);
        } else if (i == reverse) {
            Collections.reverse(signals);
        }
    }

    return signals;
}

You, probably:

Parks and Recreation: Throwing away a computer

I didn't know how to solve this. Eventually, I got stuck and mixed different ideas together. I intended to iterate over the binary string from binaryString.length() to minus 5, with five possible actions in mind. Alas, a binary value might be less than 5 characters, such as 9 (1001).

I then considered taking four zeroes and appending the binary string to them. Thi way, I would always have at least 5 positions to iterate over them.

String binaryString = "0000" + Integer.toBinaryString(number);

Yet, the string's length wasn't fixed to 5. With "0000" + "1001" = "00001001" the length would be 8. Thus, the exact position bound to each action had to be calculated dynamically based in the length.

// binaryString = 00001001
int wink = binaryString.length() - 1; // last char: ...0100|1|
int doubleBlink = binaryString.length() - 2; // next char: ...010|0|1
int closeYourEyes = binaryString.length() - 3; // etc.
int jump = binaryString.length() - 4;
int reverse = binaryString.length() - 5;

An alternative method to add missing characters is to use String.format:

// The %s value will be extended to 5 characters if needed
String.format("%5s", Integer.toBinaryString(number))

// "1001" -> " 1001" - a whitespace is added at the beginning

Although "_1001"is not the same as "01001". However, it doesn't matter in the context of this exercise. We only want to know if a character at a given position is equal to 1. It doesn't matter whether it's a zero, a whitespace or anything else, as long as it isn't 1.

Here's a caveat: if the input number is greater than 31 (11111), the binary representation will exceed 5 characters. Unfortunately, despite the specified requirements, one of the Exorcism's tests is using the input vlaue of 35 (100011). In other words, the binary string is not guaranteed to be <= 5 characters.

String binaryString = String.format("%5s", Integer.toBinaryString(number));

// "100011" -> "100011", not "00011" 🙀

I addressed this issue with a regular expression that extracts the last five digits:

String binaryString = String.format("%5s", Integer.toBinaryString(number)).replaceAll(".+(.{5})", "$1");

// "100011" -> "00011" 😻

This approach should also work with the concatenation. With static indexes, checking characters at each position is trivial.

// Let's say, that the number = 5
List<Signal> calculateHandshake(int number) {
    List<Signal> signals = new ArrayList<>();
    String binaryString = String.format("%5s", Integer.toBinaryString(number)).replaceAll(".+(.{5})", "$1");

    // 0010|1| = true, we have 1 in this position
    if (binaryString.charAt(4) == '1') {
        signals.add(Signal.WINK);
    }

    // 001|0|1 = false, we have 0 in this position
    if (binaryString.charAt(3) == '1') {
        signals.add(Signal.DOUBLE_BLINK);
    }

    // 00|1|01 = true, we have 1 in this position
    if (binaryString.charAt(2) == '1') {
        signals.add(Signal.CLOSE_YOUR_EYES);
    }

    // 0|0|101 = false, we have 0 in this position
    if (binaryString.charAt(1) == '1') {
        signals.add(Signal.JUMP);
    }

    // |0|0101 = false, we have 0 in this position
    if (binaryString.charAt(0) == '1') {
        Collections.reverse(signals);
    }

    // [WINK, CLOSE_YOUR_EYES]
    return signals;
}

Bitwise operators

On Exercism, you can see how others solved the same task in the community solutions section. That's where I found out about bitwise operators. This feature is not confined to Java, you can use it in Python, Rust, JavaScript, C#, and probably many other languages.

Behind the scenes, bitwise operators work with binary values, but we can apply them to integers and chars too. For this exercise, the AND (&) operator is often used. Unlike the regular AND (&&), its bitwise counterpart is expressed with a single ampersand, not two.

  1. Let's consider two values: v1=5 and v2=4.
  2. In the code, we can apply one of the bitwise operators to them: v1 & v2.
  3. Each bit will be compared to determine if both are equal to 1.
  4. It's similar to the regular AND (&&) operator applied to booleans:
    • true && true = true
    • true && false = false
    • false && false = false

Same values in form of a table:

| 16  | 8   | 4   | 2   | 1   | Description         |
| --- | --- | --- | --- | --- | ------------------- |
| 0   | 0   | 1   | 0   | 1   | v1=5                |
| 0   | 0   | 1   | 0   | 0   | v2=4                |
| 0   | 0   | 1   | 0   | 0   | output of `v1 & v2` |

Since 5 & 4 returns 4, we know for a fact that there's 1 in the third position, meaning that the action must added to the list.

| binary | decimal | action                              |
| ------ | ------- | ----------------------------------- |
| 00001  | 1       | wink                                |
| 00001  | 2       | double blink                        |
| 00100  | 4       | close your eyes                     |
| 01000  | 8       | jump                                |
| 10000  | 16      | reverse the order of the operations |

All this leads to the following solution, where we compare the input value to decimal numbers, associated with possible actions:

// Let's say, that the number = 5
List<Signal> calculateHandshake(int number) {
    List<Signal> signals = new ArrayList<>();

    // 5 = 0010|1|
    // 1 = 0000|1|
    //
    // The result of this comparison is 00001 or 1
    // The condition is true
    if ((number & 1) == 1) {
        signals.add(Signal.WINK);
    }

    // 5 = 001|0|1
    // 2 = 000|1|0
    //
    // The result of this comparison is 00000 or 0
    // The condition is false
    if ((number & 2) == 2) {
        signals.add(Signal.DOUBLE_BLINK);
    }

    // 5 = 00|1|01
    // 4 = 00|1|00
    //
    // The result of this comparison is 00100 or 4
    // The condition is true
    if ((number & 4) == 4) {
        signals.add(Signal.CLOSE_YOUR_EYES);
    }

    // 5 = 0|0|101
    // 8 = 0|1|000
    //
    // The result of this comparison is 00000 or 0
    // The condition is false
    if ((number & 8) == 8) {
        signals.add(Signal.JUMP);
    }

    // 05 = |0|0101
    // 16 = |1|0000
    //
    // The result of this comparison is 00000 or 0
    // The condition is false
    if ((number & 16) == 16) {
        Collections.reverse(signals);
    }

    // [WINK, CLOSE_YOUR_EYES]
    return signals;
}

Another way to solve this task would be to use the bitwise left shift operator (<<). It's based on the same idea, so I suggest figuring this out yourself.

List<Signal> calculateHandshake(int number) {
    List<Signal> signals = new ArrayList<>();

    if ((number & 1) == 1) {
        signals.add(Signal.WINK);
    }

    if ((number & 1 << 1) != 0) {
        signals.add(Signal.DOUBLE_BLINK);
    }

    if ((number & 1 << 2) != 0) {
        signals.add(Signal.CLOSE_YOUR_EYES);
    }

    if ((number & 1 << 3) != 0) {
        signals.add(Signal.JUMP);
    }

    if ((number & 1 << 4) != 0) {
        Collections.reverse(signals);
    }

    return signals;
}

Check out other possible solutions on Exercism.

Performance

Choosing between ArrayList and LinkedList is a great video that introduced me to the JMH benchmark. Arguing over which approach is better can be fun, but that's often based on our limited experience and subjective opinions. Let's collect some objective data instead!

I tested all three implementations described above with four values:n

  1. 1 - the minimal number according to the exercise.
  2. 31 - the maximal number according to the exercise.
  3. 1024 - an allegedly more realistic number that could serve as the input value.
  4. 998 - not a base 2 number as the opposition to 1024, we'll discuss this below.

I also included two solutions suggested on the Exercism website. Both are described in great detail here and here.

Results

| Method | MIN ops/s   | MAX ops/s   | REALISTIC ops/s | NOT_BASE_2 ops/s |
| ------ | ----------- | ----------- | --------------- | ---------------- |
| String | 2,887,108   | 2,910,968   | 2,040,287       | 2,068,403        |
| Bit &  | 310,184,337 | 125,008,401 | 2,320,036,065   | 302,718,931      |
| Bit << | 310,529,569 | 124,772,256 | 2,318,228,556   | 300,684,083      |
| Loop   | 181,952,427 | 78,555,464  | 3,818,534,904   | 125,523,998      |
| Stream | 21,260,678  | 14,653,600  | 27,503,337      | 19,653,348       |

Chart: Performance testing results

All results are rounded to the nearest one.

See also:

Observations

Unsurprisingly, the approach that involved string formatting and a regular expression is the slowest one. The graph illustrates this well. The bars representing the string method are barely visible.

The most surprising result is the performance of the IntStream method. It's still 5 to 14 times better than the string method, yet it's also 8 to 84 times slower than the bitwise methods.

Another noteworthy result is the amount of operations for the "realistic" number (1024). My assumption is that this is because 1024 can be represented by a single 1 (10000000000). I'm not sure why tests that used the MIN value (1) didn't produce similar numbers. Nevertheless, I re-executed tests with 998 (1111100110) as the input value to test my theory. This number is close to 1024, but its binary form isn't as simple. As expected, the score for this value was not abnormally high.

Perhaps, this could be caused by how data is stored in memory and shared with the CPU's cache. Besides, as a test engineer, I'm well aware that tests can produce incorrect results due to mistakes in tests themselves or other factors influencing test execution. That's why I shared my code above for you to double-check.

With that in mind, both bitwise implementations seem to have the best performance. For loop is 2 to 8 times slower with the IntStream and string methods trailing far behind. The only exception is the "realistic" number. If I were to implement this in some project, I'd ask myself what data my program can expect and test my hypothesis about base two numbers extensively. Who knows, maybe in a particular use-case the for loop method would be better suited?

Conclusion

A small exercise, marked as easy on Exercism, turned out to be very insightful. I learned a bit more about string formatting in Java, discovered bitwise operators, and tried running benchmark tests. Once visualized, this data showed tremendous gaps between different approaches. I guess that's why computer scientists are obsessed with algorithm efficiency!

15.11.2023