5 And 3 Is 1

| 89 Comments | 0 TrackBacks

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
If you liked this article, please share it!



Your Ad Here

No TrackBacks

TrackBack URL: http://www.excelhero.com/cgi-bin/mt/mt-tb.cgi/7

89 Comments

I've checked out your articles before, and I'm glad I came about.

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

Fantastic article !

I really think that this blog can help people. Well done :)

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

@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

Daniel - Thanks for the Excel info this is a great resource. I also like to explore what Excel can do and I have an interest in cryptography and bit manipulations in Excel. There are some crypto related Excel spreadsheet examples on my blog and also some specifics about bit rotate no carry and other stuff.

http://ottobelden.blogspot.com/2010/06/ms-excel-dec2bin-32-bit-rotate-no-carry.html

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

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!

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)

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.

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)

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?

Excel Hero Academy Homework
Hans Knudsen

I completely agree in what Jose Alberto Carranza
wrote on November 2, 2010 6:29 AM.

Daniel , you certainly are in a different league when it comes to Excel.
thanks Bruce (EHA student)

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.

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.

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

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

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

Assembly language is all about bitwise manipulations - this takes me back. And I like the way you write.
Ed EHA

0101010001101000011000010110111001101011011100110010110000100000010001000110000101101110011010010110010101101100


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

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)

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

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

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.

I can't resist

There are 10 types of people who understand binary...

Yes, I look forward to laughing maniacally the first time I can put this to good use. -JC (EHA)

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

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

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!

OK Let's see how to get this to work for some data mining!

Marcin

EHA2 student

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!

Cool article! I haven't used this type of thing much, but it looks useful.

Bob N.
EHA2 student

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

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

Over my head, but interesting nonetheless.

jnoble
EHA2

Most certainly a way to speed up Excel lookups. To me the readability is gliding a bit towards the black-box stuff.
Simon, EHA2

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

EHA2 Student watsonm05

Another good article.

And I though I was good with bit operations;-)

EHA2.
homework done.
Tim McCollough

Wow - ok, now i need to figure out where to use it. :)

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

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

I was here! Very interesting!

Good stuff, Daniel.

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

Difficult post, but hopefully the meaning will get to me in later EHA modules.

Lorette
EHA2

Had to sit with this one awhile, but after awhile, it made sense.

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?

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.

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

Fascinating & will be perusing the linked files for how this technique could possibly be applied...

Thanks once again

John - EHA2

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

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

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

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

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

Very interesting.

CHol, EHA3

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

EHA Student

This is a a little hard to grasp. I think I am grasping it slowly. Time to read it again.

Bryan B

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

Thanks
EHA3 Student

EHA 3 HW

Done!

Vito Jr

Interesting. Thanks, Daniel.
Dan Leverett, EH3

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

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

EHA3 homework

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

well I read it... 'nuff said!

John EHA3-student

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)

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.

I think this article needs to be read a few times!!

Very cool.

Yeah, that one went over my head. Leia

Will need to re-read this blog post again as it seems to over-complicate things a little.

I feel like I"m in the Matrix. Very interesting stuff that I will most certainly have to read through again.

this one's gonna take me a little time to wrap my head around.

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

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.

Very interesting.

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

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.

EHA5 check in - I'm not sure I'm following it but hope it becomes clear as I proceed

EHA5 Check in - having issues following this one

EHA5 - I am glad this one is not essential right now, but good stuff.

EHA5 - I am sure I will have to digest this info when it comes the time. But for now, just saving the article.

Leave a comment

About this Entry

This page contains a single entry by Daniel Ferry published on January 31, 2010 2:29 PM.

The Venerable SUMPRODUCT was the previous entry in this blog.

Excel 2007 NFL Drive Chart is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.