Bitwise operator in Elixir - need help understanding it

Questions / Help
1

I’m failing to grasp what the Bitwise module is doing. The documentation doesn’t have much (see for yourself). I have a decent understanding of binary already. Not sure what the &&& is doing though.

Any explanation to help me understand the following code (just a practice problem off Exercism) would be immensely helpful. I have 2 weeks to get off the ground and start an Elixir project at work so trying to learn as much as I can.

defmodule SecretHandshake do
  @doc """
  Determine the actions of a secret handshake based on the binary
  representation of the given `code`.

  If the following bits are set, include the corresponding action in your list
  of commands, in order from lowest to highest.

  1 = wink
  10 = double blink
  100 = close your eyes
  1000 = jump

  10000 = Reverse the order of the operations in the secret handshake
  """

  use Bitwise

  @spec commands(code :: integer) :: list(String.t())
  def commands(code) do
    []
    |> handshake(code &&& 0b00001)
    |> handshake(code &&& 0b00010)
    |> handshake(code &&& 0b00100)
    |> handshake(code &&& 0b01000)
    |> handshake(code &&& 0b10000)
  end

  def handshake(list, 0b00001), do: list ++ ["wink"]
  def handshake(list, 0b00010), do: list ++ ["double blink"]
  def handshake(list, 0b00100), do: list ++ ["close your eyes"]
  def handshake(list, 0b01000), do: list ++ ["jump"]
  def handshake(list, 0b10000), do: Enum.reverse(list)
  def handshake(list, _), do: list
end
3 Likes
2

You can get binary representation of an integer with Integer.to_string x, 2
&&& is and operation, which copy a bit if it exists in both bit representation of numbers

As an example, 5 &&& 6 returns 4, as expected.

iex> Integer.to_string 5, 2
"101"
iex> Integer.to_string 6, 2
"110"
iex> Integer.to_string 4, 2
"100"
iex> use Bitwise
Bitwise
iex> 5 &&& 6
4

BTW if You have a binary like this

0b01101

it will returns a list like that

["wink", "close your eyes", "jump"]
4 Likes
3

I find it easier to show it using bits

5 = 0b0101
6 = 0b0110

The Bitwise.band (&&&) is a bitwise and, meaning only if the bit is set on both sides it is kept.

5 = 0b0101
6 = 0b0110
# The position with both bit sets (1) results in the position being set (1).
4 = 0b0100 = 0b0110 &&& 0b0101

The ||| is the bitwise or where you get a 1 if there is a bit set in the same position on either or both side.
The ^^^is the xor (exclusive or) where you get a 1 only if the bit is set on either side. `

A simple demonstration:

iex(30)> [ 0 ^^^ 1, 1 ^^^ 0, 0 ^^^ 0, 1 ^^^ 1 ]
[1, 1, 0, 0]
iex(31)> [ 0 &&& 1, 1 &&& 0, 0 &&& 0, 1 &&& 1 ]
[0, 0, 0, 1]
iex(32)> [ 0 ||| 1, 1 ||| 0, 0 ||| 0, 1 ||| 1 ]
[1, 1, 0, 1]
12 Likes
4

I understand in retrospect, but still having trouble understanding how I would have arrived at the solution without looking at the answer. In particular, the instructions:

  If the following bits are set, include the corresponding action in your list
  of commands, in order from lowest to highest.

  1 = wink
  10 = double blink' 100 = close your eyes
  1000 = jump

What does it mean by ‘set’? Does it mean that there’s a one’s place, 10’s place, 1000’s place?

In other words, how would I know that I needed to use [‘wink’] if it matches base 1 and so forth?

cc @cmkarlsson @kokolegorille - thank you!

5

set in this context means == 1. And yes, there’s a one’s place, 10's place etc. But they are base 2 (binary) one's, not decimal one's.

As a historical note, the idea of set and unset comes from when memory would be set by actual physical switches toggled up and down. It starts out as “set bit 3 to 1” kind of thing. And then pretty quickly that gets verbose so it just becomes “set bit 3” and all the other bits as expected to be set to 0.

6

If a bit is set, it is 1. Otherwise 0.

In this case 1, 10, 100, 1000, 10000 are not decimal numbers. They are the bit position. If a bit is set you should include the specific action.

0b00001 = 'wink'
0b00010 = 'double blink'
0b00100 = 'close your eyes'
0b01000 = 'jump'
0b10000 = 'reverse'

This is a common way to deal with flags in a binary format.

Above you have 5 bits (0-31).

Lets take decimal number 10. This is 0b01010. The bits at position 2 and 4 are set. Which means double-wink and jump

So. you start by checking if the wink bit is set, and then go through all the other commands

I’ll do this imperatively.

## This is not good elixir! Don't do this
commands = []
commands = if (10 &&& 0b00001) == 1, do: commands ++ ["wink"], else: commands
commands = if (10 &&& 0b00010) == 2, do: commands ++ ["double blink"], else: commands
commands = if (10 &&& 0b00100) == 4, do: commands ++ [ "close your eyes"], else: commands
commands = if (10 &&& 0b01000) == 8, do: commands ++ ["jump"], else: commands
commands = if (10 &&& 0b10000) == 16, do: Enum.reverse(commands), else: commands

Basicially we check each individual bit to see if it is set with the Bitwise.&&& operator. If it is set we add the command the the command list or reverse it in case the most significant bit it set.

Your initial solution uses elixir pipes and function pattern matching to do the same thing.

2 Likes
7

There isn’t actually a need for bit operations here, in my opinoin they make the solution even hard to maintain…

Just a simple list of “steps”, mod/2, div/2 and a recursive function and you are ready to go.

This is my helper function:

defp commands(code, acc, []) when rem(code, 2) === 0, do: Enum.reverse(acc)
defp commands(_,    acc, []), do: acc
defp commands(code, acc, [h|t]) when rem(code, 2) === 1, do: commands(div(code, 2), [h|acc], t)
defp commands(code, acc, [h|t]), do: commands(div(code, 2), acc, t)

The first argument (code) is the number originally passed into the public function, which gets constantly divided by 2 on each recursion.

The second (acc) contains the individual steps of the final handshake.

The third argument is the initial list of steps, for which step I check individually by checking if its evenly divisble by 2. If its not, I add the current “step” to the final handshake.

"reverse" though is not part of the list of commands in this implementation. Here it is assumed, that we will always reverse the handshake when there is no step left to check for, but we still have the current number not beeing even. Though as a small side effect of the implementation of building the list of commands in reverse to not need to use ++/2 for well known reasons, I actually reverse when the “code” wants me to have the handshake forward and I do nothing, when the result is beeing expected as reversed.

2 Likes
8

Don’t forget you can also pattern match on bits, and that is often easier to read and understand.

1 Like
9

Yes, but the handshake exercise gets an integer passed in, not a binary. Even converting and then matchin on the bits in the binary would make the exercise very awkward to solve and hard to read.

10

I tried it in Erlang and this code works, with Two and Six grabbing 2 and 6 bits from the pattern,

> S = 255.
> <<Two:2, Six:6, _rest/bitstring>> = <<S>>. 
> Two.
3
> Six.
63
11

As I said, you’d need to have an extra step converting from the given integer to a binary, also, as I said, I does not necessarily make the code easier readable or maintainable.

12

Nice solution, more readable, IMHO. One question though, - what did you mean under

The second (acc ) contains the individual steps of the final handshake.

A simple example would be great.
Thank you :wink:

13

With that I mean that the accumulator accumulates the list of handshakes that have to be returned and found so far.

My submission from 7 years ago is still public, and even though I updated it today to pass the tests (a simple rename of files), I can not figure how to publish the latest version…

As you can see, the individual handshakes from the 3rd argument get incrementally added to the front of the acc in the recursive calls. So this list is build up in reverse. Therefore, if the secret code demands a “reversal” of the handshakes, I return the accumulator as is, and if no “reversal” is demanded, I reverse it, to get it forward.

This building in reverse is common when recursively buiding a list.

1 Like
14

Yep, seeing it all together clarifies the solution. Thank you!
As for re-submitting a new version, you can always do it by running
exercism submit lib/secret_handshake.ex from your terminal (excersism CLI should be installed first).