This article was originally written by José M. Gilgado on the Honeybadger Developer Blog.
You could probably spend your whole life building Rails apps and never need to use any bitwise operators. If you're new to programming, you may not even know what "bitwise" means.
But the moment you take an interest in systems where efficiency is important and resources are limited, bitwise operations become crucial. They're used extensively with things like networks protocols, cryptography, Unix files permissions and embedded systems.
In addition, to really understand how the computer does things like add two numbers, you have to understand bitwise operations.
Since Ruby and many other languages have native support, they're a great tool to add to your toolbox, even if it's only to understand what's going on if you encounter them in the future.
In this article, we'll cover what bitwise operations are, some examples of where they can be applied and how we can best use them in Ruby. Let's begin.
What are bitwise operations?
At the lowest level in any computer, we only have 1s and 0s, also known as bits. Any other operation that we use in Ruby or any other programming language is eventually stored as 1s and 0s, but the software in our computers transforms them effectively back and forth between what we see and what's actually stored. For example, we store the string "hello" as a chain of 1s and 0s.
Bitwise operations allow us to access directly those bits, usually representing numbers, and do "something" with them. Some operations will help us in implementing features in our software in a more elegant and efficient way.
There are two important aspects to highlight about bitwise operations for now: they're extremely effective in storing information, since we're using bits directly, and they're very fast in execution.
The basic behavior is having a set of bits and applying the operator to it. You can also use the operators with two sets of bits. Let's see some operations:
NOT bitwise operation
This is a unary operation, which means that it only applies to a set of bits and it's as simple as replacing the 1s with 0s and vice versa. It's represented with the symbol:~.
~101000 = 010111
AND bitwise operation
AND is an operation that applies to two sets of bits; its symbol is & and it follows this logic:
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
So when we have two equal-length sets of bits, the result is just applying this logic to each individual pair:
0110 AND
0111
-----
0110
In Ruby:
25.to_s(2) # 11001
30.to_s(2) # 11110
(25 & 30).to_s(2) # 11000
OR bitwise operation
Similar to the AND operation, another operation that also applies to two sets of bits is the bitwise OR. Its symbol is | and follows this logic:
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
So if we have 1 on either side, the result is 1, otherwise it's 0. Very simple! Let's see an OR operation with more bits:
0110 OR
0111
-----
0111
And in Ruby:
25.to_s(2) # 11001
30.to_s(2) # 11110
(25 | 30).to_s(2) # 11111
Practical example 1: Permissions
At this point, you might be wondering why these operations are useful. After all, they seem pretty low-level. You may not have any plans to work directly with network protocols, graphics or cryptography.
But you've probably worked with permissions before. Permissions are one area where bitwise operations can be really useful. Imagine you have a permissions system where users can perform different actions in a document:
- View
- Edit
- Delete
- Invite other users
And now we want to model these actions into different roles:
- Assistant: can view and edit the document.
- Observer: can only view the document.
- Author: can perform all actions.
How could we model this? How do we know at any point if a user has one of these roles? One answer is to use bitwise operations.
We'd store only one set of bits for each user that represents the permissions they have:
(Starting from the right side)
1st bit: View
2nd bit: Edit
3rd bit: Delete
4th bit: Invite other users
For example:
0001 = Can only view the document.
0011 = Can view and edit the document.
1001 = Can view, can't edit, can't delete and can invite others.
Once we have these values set for some users, we could do some really fast comparisons with the permission we want. Let's imagine we're checking if a user can edit the document. We could use a bitwise AND operation:
# This is called a bit mask. It contains only the value we want to check, in this case the second bit for editing.
EDIT_PERMISSION_MASK = 0b0010
# We can define a quick method to check this:
def can_edit_document?(user_permisions)
(EDIT_PERMISSION_MASK & user_permisions) != 0
end
This means that if the bitwise AND operation gives us something different than 0, we have that bit set:
0010 AND
1101
----
0000 == 0 so we don't have the permission
0010 AND
1110
----
0010 != 0 so we have the permission
We could apply the same logic to any other permission by modifying the position of the bit that we want to check, so we'd end up with these constant and the corresponding methods:
VIEW_PERMISSION_MASK = 0b0001
EDIT_PERMISSION_MASK = 0b0010
DELETE_PERMISSION_MASK = 0b0100
INVITE_PERMISSION_MASK = 0b1000
In addition, we can dynamically define the permissions and store new permissions in the future with a quick bit check.
For example, we said earlier that an assistant can only view and edit the document, so the permissions for that user would be: 0011. We can store that value in our database and then we can easily check if an assistant can perform an action with the methods defined earlier.
ASSISTANT_MASK = VIEW_PERMISSION_MASK | EDIT_PERMISSION_MASK
# This will be: 0011
# Optionally, we could use this method to check if this user is an assistant. This method could be defined inside the User class.
def is_assistant?(user)
(user.permissions == ASSISTANT_MASK)
end
If all of this sounds familiar, that's because it's the same approach that is commonly used for file permissions in Unix-based systems.
Practical example 2: Positions in a team
Let's use bitwise operations a bit more 😉.
We can apply them in another case that's relatively common: different positions on a sports team or job positions in a company. Let's go with a basketball team to simplify.
In basketball, there are 5 positions when playing a game:
- Point guard
- Shooting guard
- Small forward
- Power forward
- Center
And we can assign a set of bits to each position:
00001 Point guard
00010 Shooting guard
00100 Small forward
01000 Power forward
10000 Center
The same in Ruby would be:
POINT_GUARD_POSITION = 0b00001
SHOOTING_GUARD_POSITION = 0b00010
SMALL_FORWARD_POSITION = 0b00100
POWER_FORWARD_POSITION = 0b01000
CENTER_POSITION = 0b10000
POINT_GUARD_POSITION | SHOOTING_GUARD_POSITION | SMALL_FORWARD_POSITION | POWER_FORWARD_POSITION | CENTER_POSITION # = 31
So now we could do some interesting things, like check if the whole team is present with:
# p1...p5 are the positions of each player
is_full_team_present = (p1 | p2 | p3 | p4 | p5 == 31)
Why? By doing the bitwise OR operation, if we had all the positions, we'd end up with: 11111.
# OR bitwise operation
00001 |
00010 |
00100 |
01000 |
10000
-----
11111
And 11111 is 31, because 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31.
This is not strictly related to bitwise operations, but with this data modeling we could also check if two players can be exchanged. This would be very simple:
def can_be_exchanged?(player1, player2)
player1.position == player2.position
end
XOR
Another operation we can do with two sets of bits is XOR, whose symbol is ^.
XOR means exclusive OR and it follows this logic:
1 | 1 = 0
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
So the result will be 1 only if one of the two bits is 1; if both are equal it'll be 0.
This operation is used in some algorithms to compare a number to itself, since x ^ x = 0.
Shifts
This is an interesting group of operations where we "move" bits to one side or the other within a set. Let me explain.
With a bit shift, we move or "shift" the bits in one direction, left or right:
00010111 left-shift
<-------
00101110
10010111 right-shift
------->
11001011
We can move or shift bits n times. Here's a left shift applied to the number 5 twice in Ruby:
5.to_s(2) # 101
(5 << 2).to_s(2) # 10100
As you can see, a left shift is represented by <<. A right shift uses >>:
5.to_s(2) # 101
(5 >> 2).to_s(2) # 1
In this case, we only get one, because the bits "0" and "1" from 1*01* have been discarded.
Divide by 2 with right shift
One interesting fact about bit shifts is that you can computate some mathematical operations with them. In the past, this was faster, but nowadays this is almost exclusively used by programmers who work with more constraints in resources like in game development.
If we apply a right shift to a number, we get the result of dividing it by 2:
10.to_s(2) # 1010
(10 >> 1).to_s(2) # 101
10 >> 1 # 5
Multiply by 2 with left shift
In the same fashion, we can multiply by 2 with a left shift:
10.to_s(2) # 1010
(10 << 1).to_s(2) # 10100
10 << 1 # 20
Quickly check if a number is odd or even
There's a very simple example of a bitwise operation that's really fast and easy to follow.
Imagine we do an AND operation with 1, just 1. So that'd be any number of 0s, depending on the computer we're in, and 1. Let's do it with 2:
2 = 00000010 &
00000001
-------------
00000000
Now with 4:
4 = 00000100 &
00000001
-------------
00000000
What about 5?
5 = 00000101 &
00000001
-------------
00000001
Now we got 1. Can you guess what this means?
By doing this AND with 1, if the number is even, we'll get 0. If it's odd, we'd get 1. We could easily use this fact to create a couple of methods in Ruby:
def is_odd?(number)
number & 1
end
def is_even?(number)
is_odd?(number) == 0
end
# Or:
def is_even?(number)
(number & 1) == 0
end
If you want to go further, or experience some mind-blowing moments with bits, check out this bitwise hacks collection for more tricks.
Conclusion
Bitwise operations are hard to follow if you've never encountered them, but once you're familiar with them you'll be better prepared to deal with existing or future projects that use them. Plus, you'll have a new tool when planning a solution for a problem in your code.
Top comments (0)