Bit manipulation in C# vs Elixir

I recently had the chance to add the Intergalactic Transmission exercise to Exercism's C# and Elixir tracks. The goal of the exercise is to practice bit manipulation, by inserting a parity bit after every 7 bits so that each resulting 8-bit byte has an even number 1s.

Let's walk through a quick example.

Consider the message 01101111 01101011 (or 6f 6b in hex).

We want to insert parity bits to each byte has an even number of 1s. To do this, we start by splitting the stream into 7-bit chunks and reserve the last bit of each byte for the parity:

0110111_ 1011010_ 11
       ^        ^     (parity bits)

The last byte has only two bits of data (`11`), so we append with 0s to make it a full byte when the parity bit is added:

0110111_ 1011010_ 1100000_
                    ^^^^^   (added 0s)

Now we calculate the parity bit in each byte:

• 0110111_ has five 1s → parity bit is 1 to make the count even

• 1011010_ has four → already an even number, so the parity bit is 0

• 1100000_ has two → also already an even number, so the parity bit is also 0

So the final result becomes 01101111 10110100 11000000 (or 6f b4 C0 in hex).

In C#…

One of the more interesting challenges is the extracting the data from the input to calculate the output. In C#, the data is given as a byte[], but the each byte in the output can carry only seven bits of data (the last bit is the parity bit). This means the input data is sometimes over two bytes.s

Here's how we might calculate the first byte:

byte[] inData = [0x6f, 0xb4];

// Get the first 7 bits from the first byte
byte firstInByte = (byte)(inData[0] & 0xFE);

// Count the number of ones in the byte to calculate the parity
int onesCount = byte.PopCount(firstInByte);

byte firstOutByte;
if (onesCount % 2 == 1)
{
    // Odd number of ones, parity bit is 1 to make the count even
    firstOutByte = (byte) (firstInByte | 0x01);
} 
else 
{
    // Even number of ones, parity bit is 0
    firstOutByte = firstInByte;
}

Calculating the second byte is a bit tricker because its data starts from last bit of the first input byte and continues into the next byte:

// There is still one bit of data from the first byte
byte leftOver = (byte)(inData[0] & 0x01);

// Then the rest from the second input byte
byte dataFromSecondByte = (byte)(inData[1] & 0xFC);

// Combine to get the input for next byte, remembering to the shift the bits
// into position.
byte secondInByte = (byte) (leftOver << 7 | (dataFromSecondByte >>> 1));

We've considered only the first two output bytes so far, but this illustrates the core ideas - apply bit masks, shifts and combine to pull the 7 bits of data from (possibly) two bytes, then append the parity bit using a bitwise OR.

In Elixir …

In Elixir, binary data can be represented as a bitstring. When combined with pattern matching, extracting and manipulating bits becomes incredibly elegant.

<_in::7, second_in::7, third_in::bitstring>> = <<0x6f, 0x6b>>

The right hand side tells Elixir what the data is. The left hand side has three parts:

• first_in::7 tells Elixir to match the first 7 bits of data. The variable first_in is will contain this first 7 bits.

• second_in::7 matches the next seven bits. The variable second_in will be set to it.

• The remaining is matched by third_in::bitstring and the content is stored in s`third_in`.

The nice thing about pattern on left hand side is how it resembles the structure that we are interested in. Constructing the output follows the same pattern. Assuming we have written a get_parity/1 function, it looks like this:

 <_in::7, get_parity(first_in)::1, second_in::7, get_parity(second_in)::1, third_in::bitstring, 0::5, get_parity(third_in)::1>>

Final thoughts

This was a fun little exercise in low-level data manipulation in two very different languages. In C#, we had to use bit wise operators to extract the input data across bytes. In Elixir, we use bitstrings and pattern matching to write code that more resembles the structure we want to extract - I think there's something quite nice and elegant about that approach!

If you want to give this exercise a go, check out the exercise on the Exercism C# or Elixir tracks.

(Cover image generated by Google Gemini)