5 And 3 Is 1

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.

binary_welcome_mat.jpg

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
binary equivalent:

 

1            0001
2            0010
3            0011
4            0100
5            0101
6            0110
7            0111
8            1000
9            1001

 

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:

 

0101
0011
0001

 

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:

 

0101
0011
0111

 

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:

00000000
11111111

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:

=MOD(INT(dec_val/2^(bin_place_val-1)),2)

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:

11011110
01111111

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:

01011110

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:

={1;2;4;8;16;32;64;128}

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:

LED RSS News Ticker

Unbreakable Cypher

Formula Based Sudoku Solver

Enhanced by Zemanta

89 thoughts on “5 And 3 Is 1”

  1. I’m fairly new to SQL. Recently I built a convoluted SQL query that relied on a customer only having one subscrition to a catalogue. Then the design team changed the business rules to allow the customer to subscribe to more than one catalogue. But I didn’t want to rework through my query.
    So I think I used bitwise operators to capture all the different catalogues a customer had and encode them into one integer. Fun, fun, fun.
    thanks for another great post

  2. Hi Daniel
    Great post…
    However cant seem to download the following sample files:
    Unbreakable Cypher
    Formula Based Sudoku Solver
    Rgds

  3. @KZ –
    Sorry, those files are not posted yet. The text is just a place holder until I get the time.
    Regards,
    Daniel Ferry
    excelhero.com

  4. This was by far the best advanced tutorial on SUMPRODUCT that I’ve ever come across.
    I’ve often grappled with the best way of setting up the SUMPRODUCT formulas in my models, using –() and even IF’s (which I now understand is flawed), but after reading your post there is absolutely no doubt which method I will use going forward.
    I really love how you likened it to SQL to make it really crystal clear, at least in my head.
    Thanks! I look forward to enjoying future posts!!!

  5. Excel Hero Academy Homework
    Jose Alberto Carranza
    Nice post. I liked the operations using binary numbers although I really fail to see any real application in my every day work, don’t get me wrong, as an exercise this is quite good but if you could enlighten me with some real world use I would really appreciate it!
    Thanks!

  6. Having read this article some months back I failed to understand a lot of it, now further down the line I understand more but still feel like there is more to grasp. I think I will reread this after completion of the EHA when I feel I will truly and fully unstand this and MUCH more :)
    Oli (EHA student)

  7. I think this is a great example of the unbieveable depth and power of Excel. When you consider some people are blown away when they learn about IF() this is… amazing. Would love to see some practical applications of the above method.

  8. Im with @music43 on this one. I can’t wait for when i can really appreciate this one, as right now it definitely sails right over my head.
    I understand how it works, but i dont yet quite see why its so valuable. But i have faith that will come in time.
    Jesse Warburg (EHA student)

  9. I get the first part up to “In decimal: 5 OR 3 = 7″ then I get totally lost. Is there any background material or other links I can read to help fill in the gaps?

  10. With cell A1:A3 formatted 00000000 and
    11011110
    01111111
    in cell A1:A2
    In A3 put the formula =A1+A2 to get:
    12122221
    so it seems that the following (with binary digits in A1 and A2) can be used for Bit AND:
    =SUBSTITUTE(SUBSTITUTE(A1+A2,1,0),2,1)
    Wonder if that is good for anything, but it is fun.

  11. I’m going to be cleaning brain bits off my monitor for the next hour because you caused my head to explode. This was a bit much.
    The RSS news reader was an awesome demonstration, but as others have said, finding a practical use for this kind of code is lost on me atm.

  12. Hello EHA students.
    Reading this article is OPTIONAL. You do not need to understand exactly how bit manipulation works. The point of this optional exercise is to demonstrate how capable Excel really is, AND to stimulate ideas.
    To be sure the applicability of bit manipulation is stronger in the fields of science and engineering than in business. But being exposed to this lateral thinking certainly helps stimulate creative solutions to business problems.
    Thanks for taking the time to read this.
    Regards,
    Daniel Ferry
    Excel Hero Academy

  13. Lateral thinking is right. Very interesting, but getting to the point of being able to use this will take some work.

  14. There 10 types of people in the world – those who know binary and those who don’t.
    Some very interesting uses of sumproduct and range formula.
    Some food for thought there.
    Neale Blackwood EHA

  15. Brilliant article…….
    Must admit I have not got my head around the sumproduct formula but appreciate the theory.
    NB:There are two conversion functions Dec2Bin and Bin2Dec.
    I had the situation where instead of having around 10 nested if statements I was able to use the theory from this article and the two conversion functions to solve the problem in a simple way.
    Cheers,
    Michael
    Excel Hero Academy Student

  16. Ha. I haven’t looked at binary in 20 years. I don’t see any practical purpose in what I’m doing these days to use this nugget of knowledge … but it’s good to know it’s there in case something comes up.
    Janice (EHA)

  17. Interesting but can’t say I understood 100% of it or can see where this might be applied.
    Scott Wiltshire – Academy homework

  18. Bits are a very efficient way of storing yes no data about say a user. Being able to extract and manipulate the positions adds extra power

  19. This is fascinating. These articles are sparking a new interest in math for me. While I don’t see an immediate application for bitwise operations in my line of work, I definitely see the benefit of stretching my understanding of the capabilities of Excel. The more comfortable I am in Excel, the more capable I become.

  20. I ended up in a web site in Egypt. Must go there for holiday soon.
    Back to excel – No idea how I will use this but I will in a few weeks time I hope.
    A few questions.
    In your binary spreadsheet you have
    =MOD(INT($E$35/I$7),2)
    =1 – MOD(I30+I31,2)
    =SIGN(I15+I16)
    The SUMPRODUCT formulas use a Defined Name, b, for a quick reference to the conversion constants.
    ‘=2^(32-ROW(INDIRECT(“1:32″)))
    can you explain:- MOD; INT; SIGN; ROW; INDIRECT and the logic of all the formula.
    also b – can you explain how to set up this defined name as I could not see it in the spreadsheet and it appears to be a critical piece of knowledge.
    Again the logic is very well explained just need help with the short cuts so I can move towards herohood.
    thanks

  21. @MMS: Excel itself has exhaustive help files on these topics, and Google has thousands of articles on each topic. So as a first step, you should fire up excel, click on the fx button to the right of the formula bar (this has a tooltip that says insert function if you hover over it), then type the name of the function you want to find out more about in the Search for a function box.
    If the excel help files don’t have enough context for you to follow along (and granted, they often don’t) then a good second step would be to perform a Google search…there are thousands upon thousands of articles already written on these subjects. If Daniel had to replicate them all to get all levels of reader up to speed, then he wouldn’t get time to write cutting edge stuff like this, let alone run an amazing online excel hero course.
    Sorry to be coming across negative here, but you already have the tools right at your fingertips to answer the questions you’ve listed here.
    You might want to check the Mr Excel podcasts, or pick up a John Walkenbach book on excel. I also heartily endorce Chandoo’s blog on excel (google Chandoo and you should find it). These worked wonders for me.

  22. This is a very creative solution to a problem that I’ve encountered too many times. The solution here really simplifies implementing bit masks in Excel. In extending this to 32 bits, however, there seems to be a problem with the MOD function. Implementing MOD with the more awkward and explicit MOD(n,d)=n-d*int(n/d) as shown in the help system resolves the issue. Thanks for sharing such a detailed solution!

  23. I was following and following, but got lost and the use of sumproduct. I used the formula in a spreadsheet and it works. I don’t know what that means, but it works. My head hurts now, so it must have turned some gears up stairs. Thanks for the mental workout!

  24. While I can’t think of any applications either, I feel like I just unlocked a new door in my head. Awesome stuff!
    Bijoy Mathew

  25. This gave me a flashback to some Assembly programs a previous employer used to generate invoices for a government contract. In those days, I think I finally figured out how to properly use the Or Immediate (OI) Assembler instruction … now looking forward to thinking about how I can use it in VBA … challenging, but also very interesting!
    Bryan
    EHA2

  26. I understand boolean math but the hoops you have to go through in Excel make my head hurt.
    Guess I need to read the article about SumProduct

  27. EHA2 Student watsonm05
    Another good article.
    And I though I was good with bit operations;-)

  28. I follow the mechanics, Daniel, but I’m struggling with the application. I think if I spend a lot more time with Sudoku and the RSS Ticker I might just gleen what’s going on, but short of time for that right noe.
    EHA2 Student
    Geoff Beals

  29. I followed the maths and the mechanics OK, Daniel, but really struggling with the application. Will continue looking at Sudoku and RSS Ticker, and hope for some dawning reality.
    EHA2 Student
    Geoff Beals

  30. Daniel,
    Like Geoff I follow the logic of what is happening but I am struggling to see what I would use the technique for. I will check out the Sodoku sheet to see if that inspires an answer. Thanks
    David – EHA2

  31. Excel has several base-conversion functions, particularly BIN2DEC and DEC2BIN. Are these just for display purposes, or is there a way to perform bitwise operations using these functions?

  32. Hello simchck.
    Unfortunately those built-in functions are not useful for bitops.
    DEC2BIN returns a real number, but BIN2DEC returns TEXT!
    So these are good fro display purposes, but not bitops.

  33. Scienceguy here with EHA 2 – good article, but a little dense for my brain without going through the examples (which I will do). I was going to ask about the built in excel functions, but see that you already answered – thanks.
    I find example problems that simulate real-world scenarios are often the most enlightening method of learning (for me anyway).
    Regards,
    Kevin

  34. Fascinating & will be perusing the linked files for how this technique could possibly be applied…
    Thanks once again
    John – EHA2

  35. Hi Daniel!
    Binary number system is not that easy to understand at a glance, although I have learned basic principles at university. Let´s review your links and understand how it can work at excel.
    Tks.,
    Rodrigo Bertin – EHA2

  36. Binary logic is very powerful and fast: I am definitely not used to implement in my Excel work so far.
    Going to try it ;)

  37. EHA3 Homework: Re-reading (and enjoying) this article.
    I have played about before with passing multiple parameters in a single value, i.e. similar to the way you can add VBA’s MsgBox constants, e.g. vbOKOnly + vbCritical.
    But I’m still to take it to the next level. I’ve previously downloaded and had a quick look at the RSS News Ticker and Sudoku Solver but will need to spend some time (sometime) on these.
    Stephen Crump

  38. Hi Daniel,
    Very good article, I was able to produce the same results using EHA UDFs as so:
    =JOIN((MOD(INT(F3/2^(VECTOR(8)-1)),2)*MOD(INT(F4/2^(VECTOR(8)-1)),2)))
    -Brent

  39. I really want to master this one! I have used a much less elegant method of doing this in VBA in the past to pass a whole list of options as a single parameter. This opens a world of possibilities.
    KenU, EHA3

  40. I must confess binary is almost Greek for a non-Greek lawyer. However it is very interesting to learn a little. EHA3_HW.

  41. EHA Student
    This is a a little hard to grasp. I think I am grasping it slowly. Time to read it again.
    Bryan B

  42. Looking forward to learning more and getting a better understanding of this. Or possibly applying it to a business related example.
    Thanks
    EHA3 Student

  43. I’ve read this (as most other of your posts) before, yet it will still take a bit (ha, ha) before I can incorporate this knowledge into building spreadsheets

  44. Maybe I shouldn’t have read this late at night, because I am having a difficult time wrapping my mind around this and also how I will apply it to the things I do in Excel for my work.
    John
    EHA3 – ndarmyserver

  45. EHA3 homework done. Very interesting stuff. Now I just need some time to digest the content and see actual applications since it went a little abstract for me. Examples in action will help.
    Pablo

  46. Read it, understood some of it – but wondering how I can use it (because right now it seems to fly in the face of keeping things transparent and simple! lol)

  47. I have always been in awe about how computers only use 0 and 1.
    I will reel on this info and try to think about how it applies during this course.
    I am looking forward to trying out SUMPRODUCT.

  48. I agree with many others…kind of a brain tease. Conceptually it makes sense, but the conversion certainly isn’t something I’ll be doing for fun anytime soon.
    Michelle

  49. I had read this before enrolling in EHA, and I have done a lot of mainframe assembler and PL1 programming where you can do the same type of magic with bitwise operations. Excellent blog.

  50. This is part of Module 5’s homework. I can understand it but it will help to see how it’s used.
    For now, it just makes my head hurt

  51. Lol, Dennis! My son uses sumproduct all the time. For instance, he solved our Challenge #1 with sumproduct. I’m still not totally sure how (why?) it works and am looking forward to seeing more about it.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>