## 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.

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
``````

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

``````var accessories = 0b1011 //hat, necklace and mouse; but not yarn
//add the mouse to the image
}

//add the hat to the image
}

//add the yarn to the image
}

//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.