MadSci Network: Other |

Posted By:

Area of science:

ID:

Hi Robert, Interesting question. I asked some of my engineering friends from college to help with this question. Here are the answers I got from them: From Len: Draw a dot. Put two lines at about 30 degrees from straight down (two leaves) Draw dots at the end and draw two more from each dot, and repeat. At each level, going down, you have 1,2,4,8,16, etc. dots. This is a binary "tree" and the final row is filled with "leaves" Explain that each extra digit multiplies the maximum by two, and the final level may have zero or one or two or 2 to the number of levels leaves. -------------------------------- From Victor: Sure, have the student write out all the possible combinations that a single bit can yield (2: 0,1), then all the combinations that two bits can yield (4: 00,01,10,11) then all the combinations that three bits can yield (8: 000, 001, 010, 011, 100, 101, 110, 111) and so on until you're bored. It should become pretty obvious that with every bit you add, you get twice as many total possibilities. Restated, with N bits you get 2^N combinations. Why does the first bit (on the right) always stand for 1 and then next (to the left) for 2 and the third for 4 and so on? For the same reason we write left to right; Its just convention. Our numbers get bigger to the left, like 7 becomes 27 (and not 72) when you add 20, and binary works the same way. The smallest "one's place" is on the right and they grow leftward. But why can you only count to 2^N-1?? Basically, it's because of 0. You have 2^N combinations (because each bit you add gives you twice as many possibilities) and you can use the right to left system to put the combinations in a "smallest to largest" order. BUT, like the fingers on your hands (10 of them) which can count to 10 or 9 depending on whether you make the first finger 1 or 0, binary can go to 2^N (the number of combinations) if the first combination is 1, or 2^N-1 if you make the first combination 0. The first combination is always all 0 and it would be SO ugly to call it 1 that we call it 0 and reserve 1 for 00001. And if THAT doesn't work, make the student keep writing out all the combinations until it PAINFULLY obvious that there's twice as many with each added bit. --------------------------- From Yev: The only additional idea I can come up with is a "tree" because it's pretty easy to visualize how the number of "possibilities" increases with each level (although the analogy is better suited to probably and statistics than plain binary counting). So you start off with 2^1: | / \ 0 1 The two possibilities are 0 and 1 so you have two values that you can represent with 1 bit. Now you move to two bits (2^2): | / \ 0 1 / \ / \ 0 1 0 1 If you "read" the tree from the root to the leaf you see that you have four values that can be represented (00 01 10 11) If you just assign each a decimal value you can see that you can represent numbers 0-3 this way. Now as you keep adding more levels to the tree, you will see that you double the number of leaves each time, and that the number of values you can represent doubles as well. | / \ 0 1 / \ / \ 0 1 0 1 /\ /\ /\ /\ 0 1 0 1 0 1 0 1 (000 001 010 011 100 101 110 111) -> (0 1 2 3 4 5 6 7) This is really more appropriate to describing outcomes in probability and statistics classes, but it may help in this application as well. ------------------- From Arun: Robert K. may have tried this already, but I have found that clearly explaining the relationship between digit position and value as powers of 10 in a decimal digit helps in understanding the same relationship in binary digits. Since that last sentence reads pretty incomprehensibly, let me try an example: 10^3 10^2 10^1 10^0 2 3 1 5 = 2 * 10^3 + 3 * 10^2 + 1 * 10^1 + 5 * 10^0 = 2315 In the same way.... 2^3 2^2 2^1 2^0 1 1 0 1 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 1101 binary = 13 decimal The second part of this explanation involves explaining why decimal has 10 digits and binary has only two. This is probably best done by asking and answering the following questions.... In base 10: Q: How many 10^0s does it take to have 1 10^1: A: 10 (counting through these is usually helpful) Q: How many 10^1s does it take to have 1 10^2: A: 10 (counting through these is usually helpful) ... Q: How many 10^2s does it take to have 1 10^3: A: 10 (counting through these is usually helpful) In base 2: Q: How many 2^0s does it take to have 1 2^1: A: 2 (counting through these is usually helpful) Q: How many 2^1s does it take to have 1 2^2: A: 2 (counting through these is usually helpful) ... Q: How many 2^2s does it take to have 1 2^3: A: 2 (counting through these is usually helpf So you need 1 (digit representing 0) plus one less than the number of units to equal the next place. --------------- From Jeff: Binary counter --------------- From Sarah: So I'm not an engineer, but the first thing I though of was the tree analogy that a couple people have suggested. I also really liked Arun's question and answer thing. That seemed to help me a bunch. Please let me know if you need some other suggestions. I'm sure I (we) could come up with others. Good luck! -Sarah

Try the links in the MadSci Library for more information on Other.

MadSci Network, webadmin@www.madsci.org

© 1995-2000. All rights reserved.