In Progress
Unit 1, Lesson 21
In Progress

Bitwise Operations with Peter Cooper

Video transcript & code

Hi, this is Peter Cooper, editor of Ruby Weekly and numerous other email newsletters, you can find me on Twitter at @peterc. It’s an honor to be here with you today.

If you’re here solely for object oriented design, refactoring, design philosophy, or anything like that, you might want to give this video a swerve!

So binary. Here’s a quick refresher.

Normally we represent numbers using the digits 0 through 9, the decimal system, we all know what is.

In the binary system we can also represent numbers, but we have just two digits, 0 and 1. Any number can be represented using 0s and 1s, just as with decimal.

Let’s say we want to represent 0. That’s just 0. Easy.

And 1? 1. Easy.

What about 2? We have no digit two, but the number 2 can be represented as 10. That’s not ten, but one-zero. Instead of having tens, hundreds, thousands, and so forth as each column, we have twos, fours, eights, sixteens, thirty-twoths and so on.

Ruby let’s us work with binary representations and also convert between binary and decimal quite easily. Let’s say we want to know what 42 is in binary. We could work it out, but let’s get Ruby to do the work.

42.to_s(2)

What we do is tell Ruby to convert the decimal 42 to a string that represents the binary version.

It’s 101010 .. nothing suspicious about the meaning of life there then..!

We can also represent numbers directly in binary in Ruby as Avdi showed you in episode 1. We prefix with 0b, like so:

0b101010

Note that we can also convert back from a string representation of binary to decimal with to_s:

“101010”.to_i(2)   # => 42

The argument of 2 is just telling to_i that the representation is in base 2, a synonym for “binary”. Without it, Ruby assumes base 10, decimal, and we’d get this:

“101010”.to_i   # => 101010

Now, Ruby lets us perform special operations upon binary representations that we call “bitwise operations”. Bitwise operations just manipulate things at the level of each bit. What’s a bit, you say?

If you take 101010, each digit there is a bit. Each bit is the smallest unique portion of a computer’s memory, whether that’s regular memory, a register, or whatever.

Bit is a shortened version of “binary digit” by the way, and just to tie together some terminology, eight bits is now typically called a byte, although historically a byte has had no specific length and was simply the smallest addressable unit of memory upon a particular computer architecture.

Let’s start with some Ruby specific methods that aren’t exactly bitwise operations but get us going in the right direction.

Let’s take our 42, and then ask Ruby to tell us what individual bits of it are set to.

100[0] # => 0
100[1] # => 1
100[2] # => 0

Using the square brackets method on a number in Ruby lets us “address” individual bits of that number.

Another thing we can do is see the bit “length” of a number. That is, the minimum number of bits that would be required to represent that number. For example:

42.bit_length # => 6

Whereas, 255, the largest number that can be represented in 8 bits is..

255.bit_length # => 8

Note that just one digit higher, 256, we need 9 bits:

256.bit_length # => 9

As an aside, this can be used as an interesting and quick way to determine if a number is a power of two or not. Take a number x and if x’s bit length is not the same as the bit length of x - 1, it must be a power of 2, as the number of bits needed to represent it has just increased by 1:

x = 256
puts “#{x} is a power of 2!” if x.bit_length != (x-1).bit_length

So, now on to the true, primary bitwise operations. You may have heard of them before, they’re called AND, OR, XOR, and NOT.

The AND operation isn’t the same as the logical and operation you might use on an if statement. Instead, it’s an operation that takes two binary digits or even complete numbers and then compares each bit in each respective position, then only applies a 1 on the output if both respective bits on the input are 1 too. This is best shown visually using what’s called a truth table which shows all combinations of inputs and the outputs they result in.

Or in code, we can demonstrate:

(0b101 & 0b100).to_s(2)  # => “100”

Notice that the AND operator is just a single ampersand, unlike the logical and which is a double ampersand &&.

The OR operation is like the AND operation except the output bit is 1 if either of the input bits is a 1.

Or in code..

(0b101 | 0b110).to_s(2) # => “101"
(0b101 | 0b010).to_s(2) # => “111”

XOR is again a bit like OR but with the proviso that the output bit is only 1 if one and exclusively one of the input bits is a 1. So with OR, if both input bits are 1, the output is 1. But with XOR, the output would be 0 unless a single input bit is 1 and the other is 0.

(0b111 ^ 0b111).to_s(2) # => “0"

NOT is, in theory, the easiest, but in practice is a bit of a pain in Ruby. In theory, if you take a string of bits and flip any 1s to 0s and 0s to 1s, you’re good. The truth table is ridiculously simple.

The problem is that due to how numbers are represented internally in Ruby and other languages, flipping all of the bits has the interesting side effect of making them negative.

(~0b101).to_s(2)  # => “-110”

However, a compounding problem here is that Ruby isn’t really returning the internal representation of the number using to_s, as we can analyse here:

(~0b101)[0]  # => 0
(~0b101)[1]  # => 1
(~0b101)[2]  # => 0

This demonstrates the NOT is actually working properly, but due to the way negative numbers are stored and represented, things get complicated when it comes to rendering decimal equivalents. This could be the topic for an entire other video, however, so we will pause there.

Before I show a quick example of practical uses for these operators, I want to quickly touch on another operation that is commonly considered a bitwise operation, but isn’t the classical sense. It’s called shifting.

Take “101” and let’s “shift” it to the left. We can do this in Ruby with two less than signs.

((0b101) << 1).to_s(2)  # => “1010”

What’s happened is our 101 has shifted one position to the left and a 0 has been placed in the rightmost place. We can then shift is back again, by shifting to the right.

((0b1010) >> 1).to_s(2)  # => “101”

Due to how binary is built around powers of 2, this has the interesting side effect of doubling and halving numbers. Let’s try it on decimal:

24 << 1 # => 48
24 << 2 # => 96 (equivalent of 24 * 2 * 2)
24 << 3 # => 192 (equivalent of 24 * 2 * 2 * 2)
37 >> 1 # => 18

.. because we’re working with binary, we get no decimal places on the last one, we just lop off the odd bit.

Shifting is commonly used at the machine code level to optimise multiplications since shifting bits is a lot quicker than performing true multiplication.

If this intrigues you, you might also look up rotation, which is a bit like shifting, except instead of digits being lost off of either end, they get looped around to the other end of the value. Essentially the bits of a value get rotated rather than just shifted.

So how are bitwise operations useful in Ruby or even programming in general? This is mostly an exercise for you, Google “uses for bit wise operations” and you’ll actually find a lot of stuff, but here’s a quick fly through some ideas.

If you’re doing socket programming or interacting with low level C libraries, you’ll often encounter interesting ways data has been packed using binary. For example, in a single byte, we have 8 bits, but you could represent two 4 bit numbers within that.

Let’s say we have the numbers 6 and 9 and we want to represent those separately within a single byte. We could place one number in the lower 4 bits of the byte, and the other in the higher. But how?

Simply saying x = 9 gets us the number 9 into the lower 4 bits, so that was easy! The 6 will take more work.

So all we do is shift 6 left by 4 bits and add it on!

Now what about extracting both of them? One way is to use what’s called a bitmask. What you do is mark the area you want to extract using one number then AND it with the data to pull out only the marked part.

0b11110000 & 105  # => 96

Then shift that right 4 places:

96 >> 4 # => 6

And similarly for lowest 4 bits:

0b00001111 & 105 # => 9

This sort of stuff is very useful to know when working with things like colour values, IP addresses, file formats, or network packets at a low level.

A similar technique is often used in C to store simple on/off flags compactly. Let’s say we want to represent the flags of a blog post.. things like is it private or not, is it published or not, was it deleted or not?

PRIVATE = 1
PUBLISHED = 2
DELETED = 4

flags = 0

Now, to turn on and off bits, you’d just use OR for turning bits on:

flags |= PRIVATE
flags |= PUBLISHED

And then AND for checking if bits are set, a non-zero value represents true:

flags & PRIVATE # => 1
flags & DELETED # => 0

We could then use XOR to turn OFF a flag:

flags ^= PRIVATE
flags & PRIVATE # => 0
flags & PUBLISHED # => 1

Indeed, XOR actually would toggle the flag on and off if you kept using it.

Now if you thought ActiveRecord’s enums were clever, imagine having this on them!

OK, so this is becoming a feast rather than a tapas, but if you want to keep investigating, bitwise operations are also used in things like:

  • compression
  • checksums
  • hashing
  • graphics manipulation (think about doing these operations on colour values, such as overlaying two images on top of each other)
  • cryptography (you can XOR values with a key value and toggle them back and forth)
  • calculating valid network addresses for a subnet
  • swapping two variables without an intermediary

And more. But that’s it, so follow me @peterc, subscribe to Ruby Weekly, and goodbye and goodnight!

Responses