Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Why does the trick of taking the binary representation of each digit and simply concatenating them work?

e.g. 0x4E == 0100 concatenated with 1110, making 01001110

share|improve this question
88  
It's because $16$ is a power of $2$. –  IBWiglin Dec 7 '13 at 17:09
16  
Why should it be just plain English? We are dealing with mathematics. –  nayrb Dec 7 '13 at 17:26
9  
And binary to Octal works just as well. But not Octal to Hex or vice versa. That's the cool puzzle here. –  JoeTaxpayer Dec 7 '13 at 17:46
6  
@JoeTaxpayer That's no puzzle at all. 8 is a power of 2. 16 is a power of 2. 16 is not a power of 8. –  Asad Dec 8 '13 at 2:42
6  
"In plain English" can mean "Tell me the true underlying mechanism", something a bare-bones mathematical proof doesn't always reveal. –  Rob Lyndon Dec 8 '13 at 11:18

10 Answers 10

up vote 34 down vote accepted

Let's define a notation for "base 1000" where the every "base 1000 digit" consist of a three-base10-digits group.

Thus, the base-10 number 123456789 would read 123 456 789 in base 1000.

As you can see, conversion between these is really, really simple. The reason is that a certain number of digits in the lower base exactly represent a digit in the higher base. This is true for all bases where the higher base is a power of the lower one. For example, base 3 and base 9 could be easily converted, while base 10 and base 20 could not.

For base 2 and base 16, the same applies, only that we decided to write "8" instead of 1000. It's just a different symbol, though...

share|improve this answer
3  
Note that this worksfor base 8 also (octal) but using 3-bit groups. e.g., the base-8 number 561 is 101 110 001 in binary. –  Darkhogg Dec 8 '13 at 16:28
4  
it works for base $2^n$ using $n$ bit groups –  Ant Dec 9 '13 at 13:34

This works not only for $16$, but also for any other power of $2$. Maybe an easy way to see it is to look at base $10$ instead of base $2$. Say I want to write the number $12345678$ in base $100$. Of course we don't have $100$ symbols to express single digits in base $100$, so we can write them using base $10$: $[0],[1],[2],\ldots,[99]$. Then $$ 12345678=[12][34][56][78]. $$

share|improve this answer
    
This one. This untangles the seeming mystery. –  Trevor Alexander Dec 7 '13 at 22:52
    
This may go without saying, but it could help to note that every digit in base 100 must always be represented by two in base 10 to preserve magnitude. So a number like [12][55][8] would be represented in base 10 as 125508. Likewise, every digit in hexadecimal must be represented by four in binary. This is directly proportional to the exponential difference between the bases. –  Josh Bjelovuk Nov 16 at 3:02

A preliminary observation: in base $10,$ multiplying a number by a power of $10$ amounts to shifting the digits leftward: $$ 10^3\cdot148=1000\cdot148=148000. $$ The analogous statement is true in any base. In what follows, numbers without a subscript are base-$10;$ otherwise, the subscript indicates the base: $$ \begin{aligned} 256\cdot A8_{16}&=16^2\cdot A8_{16}=10_{16}^2\cdot A8_{16}=100_{16}\cdot A8_{16}=A800_{16},\\ 16\cdot B_{16}&=16^1\cdot B_{16}=10_{16}B_{16}=B0_{16},\\ 16\cdot1011_2&=2^4\cdot1011_2=10000_2\cdot1011_2=10110000_2. \end{aligned} $$

Now let's look at your question. The second and third lines above represent the same multiplication, $16\cdot11.$ Multiplication by $16$ shifts hexadecimal numbers left by one digit and binary numbers left by four digits.

With this in mind, consider the hexadecimal number, $$ \begin{aligned} A83_{16}&=16^2\cdot10+16^1\cdot8+16^0\cdot3\\ &=16^2\cdot1010_2+16^1\cdot1000_2+16^0\cdot0011_2\\ &=2^8\cdot1010_2+2^4\cdot1000_2+2^0\cdot0011_2. \end{aligned} $$ Write each of the three terms separately, using the shift idea: $$ \begin{aligned} 1010_2\cdot2^8&=1010\,0000\,0000_2\\ 1000_2\cdot2^4&=0000\,1000\,0000_2\\ 0011_2\cdot2^0&=0000\,0000\,0011_2.\\ \end{aligned} $$ The sum is the concatenation of the digits since in each block of four binary digits, only one of the three terms is non-zero.

share|improve this answer

If you look at the "column headings" for binary, they are $\dots 256, 128, 64, 32, 16, 8, 4, 2, 1.$

Compare these with those for base $16$: $\dots, 256, 16, 1.$

The crucial thing is that all the base 16 headings are present in the base 2 case.

Similarly, converting between base 9 and base 3 would be really easy for the same reasons.

share|improve this answer

That works as $16 = 2^4$ is a power of $2$. We have for a number $n\in \mathbb N$ written in hexidecimal digits as $n = (s_k\ldots s_0)_{16}$, that is $$ n = \sum_{i=0}^n s_i 16^i $$ writing $s_i \in \{0,\ldots, 15\}$ in binary as $s_i = (b^i_3\ldots b^i_0)_2$ that is $$ s_i = \sum_{j=0}^3 b^i_j 2^j $$ that $$ n = \sum_{i=0}^n s_i 16^i = \sum_{i=0}^n \sum_{j=0}^3 b^i_j 2^j 2^{4i} = \sum_{i=0}^n \sum_{j=0}^3 b_i^j 2^{4i+j} $$ that $n = (b_n^3 \ldots b_n^0 \ldots b_0^3 \ldots b_0^0)_2$. So the binary represention of $n$ consists of the concatenation of the representations of the hexadecimal digits of $n$.

share|improve this answer
    
The downvoter: What exactly is your problem? A comment would be enlightning... –  martini Dec 7 '13 at 22:51
2  
It wasn't me, but the question did ask 'in plain english' .... –  iandotkelly Dec 8 '13 at 3:29
8  
This is anything but "plain English" –  FerretallicA Dec 8 '13 at 6:57
    
I downvoted by mistake and now I can't remove it unless you edit the question. –  Alistair Buxton Dec 9 '13 at 14:17

FACT ONE: Each position in positional number systems is an increment-by-one in power of the base. Take the decimal number "one-hundred and twenty-three":

Base-10:

           1 2 3
           | |  \
           | |   "ones" (10^0)
           | "tens" (10^1)
           "hundreds" (10^2)

Base-16:

             7 A
             |  \
             |   "ones" (16^0)
             "sixteens" (16^1)

Base-2 (binary), this same number would be:

   1 1 1 1 0 1 1    
   | | | | | |  \
   | | | | | |   "ones" (2^0)
   | | | | | "twos" (2^1)
   | | | | "fours" (2^2)
   | | | "eights" (2^3)
   | | "sixteens" (2^4)
   | "thirty-twos" (2^5)
   "sixty-fours" (2^6)

FACT TWO: 16 is a power of 2. Or in other words, there is an integer that 2 can be raised to, to get 16.

FACT THREE: Four binary digits are needed per hexadecimal digit because four binary digits are required to move along the number-line the same distance as a single hexadecimal "F" (the maximum individual hexadecimal value).

Because of the above facts, you can take each of the digits in a hexadecimal number, convert them to their equivalent binary digits in a group-of-four and simply place them one after the other (i.e. concatenate them).

In other words: because sixteen is a power of two, base-two has all the positional powers that base 16 has. We can find the maximum number of digits in base-two required to represent a single digit in base-sixteen, convert to binary and then simply concatenate them. 7A16 can be represented as "01112 sixteens, plus 10112 ones", or 01111011.

share|improve this answer

Because each hex digit is exactly 4 binary digits. It is the exactly-ness that allows the trick to work.

(Yes, I know this has already been answered and accepted, but my answer is special: No equations, and all the words are plain English!) ;-)

share|improve this answer
8  
Except the word after "exactly". –  Did Dec 8 '13 at 9:33
    
@Did 4? (yeah, okay, I know, you meant "-ness": any human speaker of English knows exactly what that means. Not every speaker of English knows what a "factor", a "shift", or even a "power" is!) –  Darren Cook Dec 8 '13 at 12:55
    
I meant 4. $ $ $ $ –  Did Dec 8 '13 at 13:16
    
@Did Sorry, in that case you have lost me! Is your comment about writing "4" instead of "four"? –  Darren Cook Dec 8 '13 at 23:07
    
Not really, rather about claiming that an answer contains only words in plain English while it contains a number written in digits (but really this is no big deal and I am beginning to regret my initial comment...). –  Did Dec 8 '13 at 23:22

Let's make the number in the binary representation step by step.

I start with 4, it is 100, but I should multiply it by 16, so I should do 4 left shifts, then I'll get 1000000, now I should add E, getting 1001110. Note that because 0-F need at most 4 binary digit, so adding is quite easy because I have 4 zeros in the right most digits of my binary number after the 4 left shifts.

Let's try another number F71.

F ->1111

4 Left shifts:

11110000

Adding 7:

11110111

4 Left shifts:

111101110000

Adding 1:

111101110001

The concatenation is equivalent to 4 left shifts and adding.

share|improve this answer

The Bins were a peaceful race, successfully categorizing their universe in terms of twos:

The Good Bins

While waddling along on their single-toed feet, they counted things as one, two, or many.

One day, the evil Hexes invaded:

The Evil Hexes

Due to their superior technology, they quickly dominated the peaceful bins and forced them to start doing their taxes. The Evil Hexes grew perplexed as they learned that when dealing with such basic concepts as "fourteen", the bins were completely unequipped to grasp the concept.

One day, the leading Bin Anthropologist realized that there was a huge cultural rift due to the amount of digits, and the inability of the bins to actually count beyond two (well, four if they used their feet, but that didn't get help them with the fourteen concept unfortunately).

So he set out to teach the bins how to count to Hex (that would be the Hex word for 16, which is an entire hand). He started them off easy.

Professor Hexander the Great: "Use your left hand to count to one."
Ambassador Binjamin Frankling: "We've been doing that since before you came."
Hexander: "Now instead of raising your right digit to count to two, lower the first digit, and use your right hand to indicate how many pairs of digits you have."
Binjamin: "So you're saying right-one is really two? Isn't that complicated?"
Hexander: "Yes, but you'll appreciate the effort when you are able to do my taxes. Now what comes after two?"
Binjamin reluctantly holds up both his right and left digits.
Hexander: "Very good! You have two-right and one-left, that's three! Now how would you count to four?"
Binjamin sticks out his left foot and puts down his hands.
Hexander: "Excellent! Your foot represents the fours! Now can you do 14?"
Binjamin sticks out his right and left foot, and his right hand.
Hexander: "Now get to work on those taxes!"

What happens if a freak of nature with two limbs with 5-digits each pops in to the equation? How will he count to fourteen? How will the Bins easily count to ten?

This is a roundabout way of saying that it works because 2^4 = 16, but thinking about it in terms of fingers and how we count may add a unique angle. You never know.

share|improve this answer

In binary only two digits 1 & 0 are used to represent numbers. Since 16 (the base for hexadecimal numbers) is a quad of 2 (2^4 = 16), the conversion between the two doesn't lead to any errors. They're factors of each other.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.