Using Bitwise Operators

A cool thing I learned about a couple years ago in school is bitwise operators. I honestly mostly forgot about them until a coworker pointed out an implementation in our codebase the other day. I want to talk about a couple "practical" uses for them in that I've seen.

Before we begin, let's do a quick math recap. An operator is a tool that acts on the operands to produce another output. Famous operators are +, -, *, etc. It is both the element or tool that acts upon operands, and what we call the thing that denotes the action. An operand is the object of the mathematical operation. So in 2 + 2, the 2s are operands, the plus sign is the operator.

Introduction to Bitwise Operators

So what are Bitwise Operators? Well, an operator that operates on bits! Basically, they are operators that move around bits in patterns (like binary numerals) at the individual level. Because they operate at such a low level, they are general very speedy. Remember operators are just like +/plus and -/minus so they also have mathematical symbols and english names. The programmatic or mathematical denotation is going to be different across languages.

I'm going to go through and explain some really common ones. Sometimes I understand code better than English so I've also just coded out in ruby what the logic means, but this is my own pseudocode, not source code! Ok, here are the main bitwise operators:

NOT

Also known as a complement, this operation performs negation on each bit so 1111 would become 0000, 10101 becomes 01010, etc. In code:

def NOT(bit)
  output = ''
  bit.each_char do |char|
    output += char == '0' ? '1' : '0'
  end
  return output
end

AND

This takes two operands and multiplies each bit. So 1111 AND 0000 is 0000 (1*0 across all bits), 10101 AND 00111 is 00101, etc.

AND reminds me of a lot of languages Boolean || operators when false || true, true || true, false || false, the bitwise AND acts in an identical way, but with binary. In code:

def AND(bit_1, bit_2)
  output = ''
  bit_1.split('').zip(bit_2.split('')).each do |arr|
    output += (arr[0].to_i * arr[1].to_i).to_s
  end
  return output
end

OR

This also takes two operands. The OR takes two bit patterns and results in 0 if both bits are 0, or else 1. So, 1111 AND 0000 is 1111, 10101 and 00011 is 10111, etc.

def OR(bit_1, bit_2)
  output = ''
  bit_1.split('').zip(bit_2.split('')).each do |arr|
    if arr[0] == '0' && arr[1] == '0'
      output += '0'
    else
      output += '1'
    end
  end
  return output
end

XOR

This is our most complicated one yet. XOR also takes two operands where the result in is 1 if only the first bit is 1 or only the second bit is 1, but is 0 if both are 0 or both are 1. Ah, confusing. Let's code this.

def XOR(bit_1, bit_2)
  output = ''
  bit_1.split('').zip(bit_2.split('')).each do |arr|
    if arr[0] == arr[1]
      output += '0'
    else
      output += '1'
    end
  end
  return output
end

Ah, that's better.

So these operators are pretty cool! They do simple math on binary and we can kind of see how they might be useful on a theoretical level. Just like we couldn't image life without multiplication, addition, subtraction, and division, bitwise operators are essential to a computer's life. From these simple building blocks, we can make some pretty powerful math.

All programming languages I've seen have bitwise methods built it, but they look a little different than what we've defined here. For example, Ruby bitwise operators:

NOT: ~
AND: &
OR : |
XOR: ^

Then there are also really cool bit shifters in ruby as well: << and >>. These shift the integers bits to the left or right by a given number of positions like

(a >> 2).to_s(2)

where a is a decimal, to_s(2) means to_binary basically, and >> 2 means, shift bits right 2 places. Example in irb:

> a = 64
 => 64
> a.to_s(2) # the binary equivalent of a
 => "1000000"
> (a >> 2).to_s(2) # the binary equivalent of a shifted to the right
 => "10000"

Anyway, we could stay here all day talking about how cool shifting bits is but I want to go into a couple cool use cases or examples I've seen of using these practically.

Tic Tac Toe

Note: In researching for this post I found this brilliant description of using bitwise operators in tic-tac-toe by Joris Labie: Using bit-logic to keep track of a tic-tac-toe game. Make sure to check it out for a more detailed description of how this works!

Building a game of tic-tac-toe is often one of the first intro level tasks a new programmer will be asked to do. It comes up often in interviews or code challenges. When I was in Ada Academy, our introduction to JavaScript was building a tic-tac-toe game in the browser. I enjoyed the project but I had a hard time formulated a good way to make the logic for winning a game. There are a lot of different possibilities for how to win across 9 different squares. Fortunately for me, I was also first learning about bitwise operators at the time, and got to thinking that Xs and Os aren't all that different from 1s and 0s. Perhaps I could use bitwise operator logic to keep track of combinations across the board.

I knew I needed to check every move for a winning score to judge the outcome, so I wrote a method checkEnvironment that would call winningScore each turn which would determine if the player that went last successful created a winning pattern of Xs or Os.

So here's how the winningScore logic worked. It relied on an array of binaryWins or 8 unique ways to win (3 horizontal, 3 vertical, 2 diagonal). These are very special numbers and taking a look at them may help to figure out why.

These are the winning combination numbers in binary:

[111, 111000, 111000000, 1001001, 10010010, 100100100, 100010001, 1010100]

and in decimal:

[7, 56, 448, 73, 146, 292, 273, 84]

And then let me express them one final way, again, in binary, but with some extraneous 0s:

[['0', '0', '0'],
 ['0', '0', '0'],
 ['1', '1', '1']],
[['0', '0', '0'],
 ['1', '1', '1'],
 ['0', '0', '0']],
[['1', '1', '1'],
 ['0', '0', '0'],
 ['0', '0', '0']],
[['0', '0', '1'],
 ['0', '0', '1'],
 ['0', '0', '1']],
[['0', '1', '0'],
 ['0', '1', '0'],
 ['0', '1', '0']],
[['1', '0', '0'],
 ['1', '0', '0'],
 ['1', '0', '0']],
[['1', '0', '0'],
 ['0', '1', '0'],
 ['0', '0', '1']],
[['0', '0', '1'],
 ['0', '1', '0'],
 ['1', '0', '0']]

Look familiar? These binary numbers are an exact expression of the wins!

It might help at this point to revisit our bitwise AND operator, which takes two operands and returns multiplies each bit. This means if you compare any combination that a current player has across the board, with each of the binary wins, any 0 bit in the players combinations, cancels out and becomes 0, but any place where the win's combination is 1 and the player has that 1 will register as a hit. For example, look at me winning diagonally on this board represented as a multi-dimensional array (I'm X):

[['X', 'O', 'X'],
 ['O', 'X', 'O'],
 ['X', 'O', 'X']]

And here's one of the binary wins:

[['1', '0', '0'],
 ['0', '1', '0'],
 ['0', '0', '1']]

If we represent each of the X's on the game board as a 1, even though there are more than the three winning Xs, they'll be canceled out by the AND operator if compared with our binary win!

This is pretty cool! Now that we have our logic figured out, the code is simple (excuse my javascript, it's not my primary language, but this works!):

Early on, set our binary wins:

binaryWins = [7, 56, 448, 73, 146, 292, 273, 84];

Write our winningScore logic:

winningScore: function(score){
  var self = this;
  for (i = 0; i < self.binaryWins.length; i += 1) {
    if ((score & self.binaryWins[i]) === self.binaryWins[i]) {
      return true;
    }
  }
  return false;
}

Each check we iterate through the possible wins, and use our score and the win as operands in the AND operator, i.e.
score & self.binaryWins[i] and return a boolean for if a winning score has been found.

So this is really neat. We've just used a bitwise operator for real! But tic-tac-toe is not business logic (unless you have a really cool tic-tac-toe business, please let me know if you do). Let's explore some other ways we could use these smooth operators.

Boolean or Bitwise Logic?

So we often use boolean logic in conditionals, but bitwise logic is just as generally powerful! These conditionals are often used in assigning colors on the RGB spectrum, for example. We can also assign a range of random elements to different binary numbers and use bitwise operators to compare them. & and | do a good job comparing if two sets have an intersection. ^ can be used to see what is different between two sets. Anytime we have sets of relationships, they can be compared using bitwise logic.

Ruby's Secure Compare

This is the secure_compare method in Ruby:

def secure_compare(a, b)
  return false if a.empty? || b.empty? || a.bytesize != b.bytesize
  l = a.unpack "C#{a.bytesize}"

  res = 0
  b.each_byte { |byte| res |= byte ^ l.shift }
  res == 0
end

secure_compare is a super cool method that protects us from timing attacks, or attacks where an attacker can measure stuff about the response of a site by how long it takes to repsond. When string equality operators work left to right (i.e. user_input == 'string') and a user is inputting something that controls that logic, they can execute a timing attack.

So to prevent this, secure_compare takes hashes of the two strings and compares those instead like:

secure_compare(
  Digest::SHA256.hexigest('a'),
  Digest::SHA256.hexigest('b')
)

If we look at the code about for secure_compare, we can see that it steps through each letter, unpacking the byte size as it goes. It then iterates on those characters byte sizes and uses the XOR operator to compare them. We can see that if two of the bytes in the corresponding hashes mismatch,res is no longer zero and the compare returns false.

Each hash pasted in is of an equal length and XOR is used to compare and find any differences in their binary equivalents. This is not only more secure because it takes constant time to compare the hashes (no ability to measure the time differences with different inputs), but it's also really fast!

Rails bitfields gem

Finally, I want to talk about a really cool gem, bitfields. It's less directly related to the operators but it uses binary logic to store things in ActiveRecord.

Say you have a table, Puppy with multiples columns has_chew_toy, likes_pets, and good_walker, which are all Boolean values. That's a lot of trues and falses for one table that seems primarily based around Booleans. What if we could save one integer to represent all these fields? We can!

The Boolean values are organized like:

true false false => 1 0 0 => 1
false true false => 0 1 0 => 2
false false false => 0 0 0 => 0
true true true => 1 1 1 => 5

And when you instantiate a new dog, you just give it the values, like

class Puppy < ApplicationRecord
  include Bitfields
  bitfield :puppy_bits, 1 => :has_chew_toy, 2 => :good_walker, 4 => :likes_pets
end

puppy = Puppy.new(has_chew_toy: true, good_walker: true)
puppy.likes_toys # true
puppy.puppy_bits # 3

This is pretty cool use of binary logic! And under the surface it's using bitwise operators to create the relationships.

Final Note

I really love learning about bitwise operators because it takes something that seems really scary and illuminates it. Bitwise operators are just like the operators we learn in elementary school, but for a numeric system we aren't familiar with. While I love this implementations, for people less familiar with the operators, the syntax can be really confusing because it looks like Boolean logic but is really different. For that reason, I really like solutions that have comments and are well documented, at least recognizing the use of a bitwise operator in a codebase.

I learned a lot writing this post! If you'd like to explore these operators more in depth I've left some resources below.

Resources

Here's a collection of some helpful resources I used in forming this blog post and some code:

• Mozilla's wiki on Bitwise operators
• Bitwise Operators in Ruby
• my javascript tic-tac-toe
• really random helpful passage on tic-tac-toe in "Using Macromedia Flash MX" by Michael Hurwicz, Laura McCabe
• secure_compare docs
• Timing Attacks against String Comparison by Nick Malcolm
• bitfields rails gem