Bitwise Operations

14 Nov 2018

I was laughing to myself the other day realizing that the blog post on is and as operations is likely impossible to find using a search engine. So to will be today’s post on the bitwise operators of & and >>. A developer can go their whole career and never run across them but when we get into a problem that will benefit from them, they save us a lot of time. It’s a case of the right tool for the right job.

Quick Aside

I had always wondered why the logical, boolean operators are && and || for comparisons in programming languages I came across. When I studied logic in college we used and for logical “and” and “or”. Turns out that the bitwise operators of & and | exist in lower level languages so doubling up appears to be the next best thing. Now, suddenly the use of == for boolean equality is clear and adds a nice symmetry to the set of symbols. I’ll leave the inconvenient existence of things like := or === for another time.

Bit Masking

Most of the time, I do my work in a high level language, Swift. It is easy enough to forget that the computer is not storing all of my numeric values as base 10 decimals. Regardless of the base that I think of these numbers in, they are stored as binary digits. One of the exciting things we can do because they are binary digits is to use the ones and zeros to encode data and set flags. When we have two binary numbers and we use the & operator on them, only those digit places where both numbers have a 1 will come through as a 1. All other combinations will produce a 0 as the result.

0101101 + 0010011 = 1000000 //45 + 19 = 64
0101101 & 0010011 = 0000001

This is easiest to see when using binary digits. However, the place that many of us encouter it is with hexadecimal numbers and especially when working with RGB hex values for UIColor. The example below shows a hex RGB color with 23 as the red, 18 as the green and D2 as the blue. Sort of a royal blue

0x2318D2 & 0xFF = 0xD2 //The blue value

If we present the values as binary, we can perhaps better see the masking at work.

0b0010_0011_0001_1000_1101_0010 & 0b1111_1111 = 0b1101_0010 //The blue value

The 0xFF mask lets us extract the last eight binary digits from the original number. Note that the underscore is included for human readability only. The compiler ignores it.

An Example

Perhaps a character in my game can be wearing a necklace and sporting a hat and carrying a ball of yarn. The way that I draw the character will change based on which of these properties is true and any combination of the properties can be true. One way we might think of representing this would be to add a boolean var for each of the different accessories.

var isWearingAHat: Bool
var isWearingANecklace: Bool
var hasSomeYarn: Bool

This is readable, and as I generate the image, I can check each value to determine if we are going to show the accessory. However, with this approach I might sometimes run into some difficulty. If I am storing these values in a Core Data or other back end storage, I have to update the schema for that storage each time I decide to add a new accessory to the mix. So adding a toy mouse will require changes in our object and in the back end storage.

var isWearingAHat: Bool
var isWearingANecklace: Bool
var hasSomeYarn: Bool
var hasToyMouse: Bool

However, if we take a bitwise approach, then all of the accessories can be stored in a single Int variable and adding a new accessory is just a matter of adding another digit to the binary representation of the variable.

var accessories: Int

The perceptive reader will have already noted that we might want to do both: keep the booleans split apart in our object for readablity and encode them into an Int value for storage.

We can create a bitmask for each of the accessories and then use that to query the accessories variable to determine if that digit in the binary representation is a 1 or a 0.

let hatMask = 0b1
let necklaceMask = 0b10
let yarnMask = 0b100
let mouseMask = 0b1000

Now our code for determining what to draw might look like this:

var accessories = 0b1011 //hat, necklace and mouse; but not yarn
if accessories & mouseMask == mouseMask {
    //add the mouse to the image

if accessories & hatMask == hatMask {
    //add the hat to the image

if accessories & yarnMask == yarnMask {
    //add the yarn to the image

if accessories & necklaceMask == necklaceMask {
    //add the necklace to the image

Bit Shifting

Just as the & operator lets us deal with individual digits (or bits!) of the binary representation of a value, we can use the >> operator to alter the binary representation. The right shift operator will move all of the bits of a binary number to the right and allow some of them to be pushed off the end. The right shift operator takes a value to represent how many shifts to the right occur.

0b101010 >> 1 = 0b10101 //42 >> 1 = 21
0b101010 >> 2 = 0b1010  //42 >> 2 = 10

A nifty parlor trick is that >> 1 is the same as dividing the integer by two. If you ever need to obfuscate some code to annoy other members of the team, just use bit shifting instead of dividing by two (or multiples of two).

There is also a left shift operator << that shifts all of the bits in the binary number to the left by a specified number of digits and pads with zeros. Extending the parlor trick above, you can multiply by two.

0b101010 << 1 = 0b10101 //42 << 1 = 84
0b101010 << 2 = 0b1010  //42 << 2 = 168

Returning to our example with UIColor you might have noticed that we cannot simply use masking to get the red and green values out of the hex representation cleanly.

0x2318D2 & 0xFF00 = 0x1800 //Not the green value
0x2318D2 & 0xFF0000 = 0x230000 //Not the red value

But, combining bit masking and bit shifting will let us extract whatever digits we want from the original value.

(0x2318D2 >> 8) & 0xFF = 0x18 //The green value
(0x2318D2 >> 16) & 0xFF = 0x23 //The red value

Remember that each hexadecimal digit is represented by four bits; which is why we shift by 8 and 16 instead of by 2 and 4. I’ve experimented with representing the shift using a non decimal value (like 0b1000 or 0b10000 or 0x10) but I just wind up confusing myself.