Ok. So I haven’t lost it. In arithmetic 5 and 3 is 8, but in
bitwise operations 5 And 3 is 1.
Bitwise operations manipulate the individual bits within a
number. An easy way to visualize this is to use the binary number system.
Humans are not designed to process binary efficiently (we prefer the decimal
system), but computers are. In fact, all information is stored and processed on
your computer in binary.
This door mat says, “welcome” in binary if you take it 8 digits at a time and convert those chunks into ASCII.
Binary is a number system composed entirely of just 0 and 1.
Any number conceivable can be expressed in binary; large numbers will have a
lot of digits, many times more so that in decimal.
Here’s a chart of some normal decimal numbers and their
In bitwise operations the AND operator compares the bits
(the 1s and 0s) of two input numbers and produces a 1 in the output for a given
digit, if and only if both of the input numbers have a 1 in the same digit.
That’s a mouthful. Visually it’s simple:
Do you see how the only digit that satisfies the AND
operator is in the ones place. It just so happens that this example while
expressed in binary, was in fact in decimal: 5 AND 3 = 1.
There are several other bitwise operators. In addition to
AND, there are OR, XOR, IMP, EQ, and NOT. Each has a different affect on the
bits and thus produces a different output. For example, the OR operator
produces a 1 in the output for a given digit, if either (or both) of the input
numbers have a 1 in the same digit. Visually:
In decimal: 5 OR 3 = 7.
Being able to perform these types of manipulations from
Excel worksheet formulas would be very useful. Oddly, Microsoft has never
included these functions in Excel. But we can synthetically reproduce this functionality by combining several native functions.
We will be inputing decimal numbers and our formulas will be converting them to binary, manipulating the bits, and finally returning to us a decimal result. Nice and clean, so how’s it done?
The first thing we need to do is determine the maximum size number that we wish to manipulate. For this post, we want to work with numbers between decimal 0 and 255. This requires 8 bits (8 digits) in binary. Under this scheme here are the binary representations of 0 and 255:
It turns out that we can get the binary bit (0 or 1) of each place of a decimal number by a fairly simple formula. Since we are talking the conversion to binary here, it is no great surprise that the number 2 plays a significant role. Starting with the first place value (the binary digit to the extreme right) and working to the left, the binary digits are found by simply taking our decimal number and dividing it by 2 raised to the power of that place position, minus 1. We then convert the result to an integer to remove any decimal point places. Finally, we return the remainder after dividing the integer result by 2. Again that’s a mouthful, but the process can be concisely described with this formula:
We are working with 8 bit numbers in this post, so we would need to perform this calculation 8 times to get all of the binary digits for the decimal number.
Applying this to the two decimal numbers 222 and 127, we would have used the above formula 16 times and produced these two binary numbers:
Now let’s say we wanted to perform the bitwise AND operation. Just by looking at them we can see the binary answer should be:
To find the AND of two place inputs, all we need to do is multiply the two together. So the first place (right to left) is 0 * 1, the second place is 1 * 1, etc. Continuing the process for 8 digits does in fact produce the same output as we found by just looking (directly above).
So that’s it. We have our AND of 222 and 127. The only thing left to do is to convert it to decimal. To do this we just multiply each digit of our result by 2 raised to that digit’s binary place value minus one, and then sum all of the products.
Wait a minute. Sum all of the products? Where have we heard that before? Oh yes, our friend the SUMPRODUCT function. So with one SUMPRODUCT formula we can accomplish all of these steps, including converting the two decimal inputs into 8 bit binary numbers, multiplying them together to get the bitwise AND result and converting this result back to a decimal number.
To make the formula manageable, we should first create a Named Formula in the workbook that will be used to represent the 8 bit conversions. The first place value uses 2^(1-1). The second place value uses 2^(2-1). The third uses 2^(3-1). Doing this for each of the 8 bits, we get the following array of conversion constants to hold in a Named Formula:
Let’s name this formula: b
to stand for BITS.
So here is our SUMPRODUCT formula to do the bitwise AND manipulation of two decimal numbers (dec1 and dec2):
=SUMPRODUCT( b * MOD(INT(dec1/b),2) * MOD(INT(dec2/b),2) )
I like to put the b as the first term as a sort of heads up that this is a bitwise calculation. Then scanning further into the formula I can clearly see the multiplication symbol separating the next two terms, and I can see instantly that this is a bitwise AND formula.
Doing the bitwise OR is nearly the same. Instead of multiplying the bits, we add them. And then we use the SIGN of those sums so that digit values cannot be larger than one. It looks like this:
=SUMPRODUCT( b * SIGN(MOD(INT(dec1/b),2) + MOD(INT(dec2/b),2)) )
Again, the b at the beginning tells me this is a bitwise calc. The SIGN tells me this is a bitwise OR.
A supercharged method of table lookups is to use bitwise AND, and a bitmask to decode multiple values from one decimal number. Here is a post on that.
The attached spreadsheet details all of this for AND, OR, XOR, IMP, EQ, and NOT.
Bitwise operations can be used to solve many challenging problems is spreadsheet design.
Here are some posts and sample workbooks that make use of bitwise operations: