40
$\begingroup$

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

$\endgroup$
  • 95
    $\begingroup$ It's because $16$ is a power of $2$. $\endgroup$ – D Wiggles Dec 7 '13 at 17:09
  • 20
    $\begingroup$ Why should it be just plain English? We are dealing with mathematics. $\endgroup$ – abnry Dec 7 '13 at 17:26
  • 9
    $\begingroup$ And binary to Octal works just as well. But not Octal to Hex or vice versa. That's the cool puzzle here. $\endgroup$ – JoeTaxpayer Dec 7 '13 at 17:46
  • 10
    $\begingroup$ @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. $\endgroup$ – Asad Saeeduddin Dec 8 '13 at 2:42
  • 6
    $\begingroup$ "In plain English" can mean "Tell me the true underlying mechanism", something a bare-bones mathematical proof doesn't always reveal. $\endgroup$ – Rob Lyndon Dec 8 '13 at 11:18

12 Answers 12

46
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Darkhogg Dec 8 '13 at 16:28
  • 4
    $\begingroup$ it works for base $2^n$ using $n$ bit groups $\endgroup$ – Ant Dec 9 '13 at 13:34
97
$\begingroup$

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 the situation in base $10$ instead of base $2$, to avoid the scare. Say I want to write the number $12345678$ in base $100$. Of course we don't have $100$ familiar symbols available to express single digits in base $100$, so one easy solution is to write them using base $10$: $[0],[1],[2],\ldots,[99]$. Then $$ 12345678=[12][34][56][78]. $$

In more detail, \begin{align} 12345678&=1\times10^7+2\times10^6+3\times10^5+4\times10^4+5\times10^3+6\times10^2+7\times10^1+8\times10^0\\ \ \\ &=12\times10^6+34\times10^4+56\times10^2+78\\ \ \\ &=12\times100^3+34\times100^2+56\times100+78. \end{align} The key facts are that $$ 1\times10^7+2\times10^6=10\times10^6+2\times10^6=12\times10^6, $$ etc.

If we would do it in base $1000$, it would be $$ 12345678_{10}=[12][345][678]_{1000}. $$

Now, when the bases are $16$ and $2$, the game is the same: since $16=2^4$, groups of four binary digits (starting from the right) will form a single hexadecimal digit. So for instance $$ 11110010_2=[1111][0010]_{16}=F2_{16}=15\times 16^1+2\times16^0=242. $$ Or, for example in base $8$, $$ 11110010_2=2^7+2^6+2^5+2^4+2^1=(2+1)2^6+(4+2+0)2^3+(0+2+0)=362_8, $$ $$ 11110010_2=[11][110][010]_8=362_8. $$

$\endgroup$
  • $\begingroup$ This one. This untangles the seeming mystery. $\endgroup$ – bright-star Dec 7 '13 at 22:52
  • $\begingroup$ 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. $\endgroup$ – Drazen Bjelovuk Nov 16 '14 at 3:02
  • $\begingroup$ Correct me if I'm wrong, but I believe for the last example, the last term in the binary representation should be $2^1$, not $2^2$, since the first $1$ from the right is in the $2^1$ position. $\endgroup$ – AleksandrH May 31 '18 at 16:40
  • $\begingroup$ Indeed. Thanks for noticing! $\endgroup$ – Martin Argerami May 31 '18 at 17:46
34
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As very much not a mathematician, this helped me a lot more than the other answers. It helped me notice that each digit of a binary number moves us by 2, and therefore four binary digits move us by sixteen, or one base-sixteen digit. Thanks, Ben! $\endgroup$ – CalendarJ Aug 11 '17 at 3:18
  • $\begingroup$ Thanks Julian. I have revisited this today and written an even simpler explanation as another answer below. $\endgroup$ – Ben Aug 11 '17 at 7:42
10
$\begingroup$

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

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

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

$\endgroup$
  • 8
    $\begingroup$ Except the word after "exactly". $\endgroup$ – Did Dec 8 '13 at 9:33
  • $\begingroup$ I meant 4. $ $ $ $ $\endgroup$ – Did Dec 8 '13 at 13:16
  • $\begingroup$ @Did Sorry, in that case you have lost me! Is your comment about writing "4" instead of "four"? $\endgroup$ – Darren Cook Dec 8 '13 at 23:07
  • $\begingroup$ 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...). $\endgroup$ – Did Dec 8 '13 at 23:22
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Coming in well after the fact, and as a non-mathematician, I think I have an easy and algebraic way of explaining this:

111111112 = 27 + 26 + 25 + 24 + 23 + 22 + 21 + 20

So let's take this and factor it

Put on em parathenses (27 * 26 * 25 * 24) + (23 * 22 * 21 * 20)

Factor out a 2 to the fourth24 * (27 * 26 * 25 * 24) + (23 * 22 * 21 * 20)

2 to the fourth is just sixteen 16 1 * (23 * 22 * 21 * 20) + (23 * 22 * 21 * 20)

And really, that second term is multiplied by 16^0:

16 1 (23 * 22 * 21 * 20) + 16 0 (23 * 22 * 21 * 20)

And that's just about the definition of base 16, right there: a number times 16n until n gets down to zero.

(161 * 15) + (160 * 15) = FF16


(More involved example)

Proof of concept with the following binary number: 1001010101010101

(1* 216 * 0 * 215 * 0 * 214 * 1 * 213) + (0 * 212 * 1* 211 * 0 * 29 * 1 * 28) + (0*27 * 1*26 * 0*25 * 1*24) +(0*23 * 1*22 * 0*21 * 1*20) =

163 * (1* 23 * 0 * 22 * 0 * 21 * 1 * 20) +

162 (0 * 23 * 1* 22 * 0 * 21 * 1 * 20) +

16 1 (0 * 23 * 1* 22 * 0* 21 * 1* 20) +

16 0 (0*23 * 1*22 * 0*21 * 1*20) =

(163 * 9) + (162 * 6) + (161 * 6) + (160 * 6) = 966616


I hope that this is helpful to someone coming along!

$\endgroup$
0
$\begingroup$

Numbers are an encoding system for quantities.

Currently humans use a positional numbering system. Positional numbering is a technology developed around 2000BC. It means that "orders of magnitude" are encoded in the position of digits in a number. Each additional digit, from right to left is one additional "order". In base 10 this is ones, tens, hundreds etc. In base 2 this is the ones, twos, fours, eights, sixteens etc. In base 16 it is the ones, sixteens, two-hundred-and-fifty-sixes, four-thousand-and-ninety-sixes etc.

Imagine a quantity of grain as a heap on the ground.

Now imagine two rows of buckets for the grain.

The first row has buckets that get smaller left to right. Each bucket is two times smaller than its predecessor (ie. the sizes halve). This represents binary (base 2).

The second row also has buckets that get smaller left to right. In this row each bucket is sixteen times smaller than its predecessor. This represents hexadecimal (base 16).

Each bucket corresponds to a position - an order - in the respective base.

We notice a relationship between the numbers 16 and 2.

16 is 2×2×2×2. 16 is 2 to the power of four.

This means that if we start filling the buckets of grain in the first row starting from the right hand side, then for every four buckets we fill we will be able to fill exactly one bucket in the second row.

This pattern continues indefinitely if we fill right-to-left. Four buckets from the top row will fill the next position in the bottom row.

The rate of increase in bucket size for the second row from right to left is consistently four times that of the top row.

Four buckets from top fills one bucket from bottom. The next four buckets from the top fill the next one bucket from the bottom.

Four binary digits fill one hexadecimal digit. The next four binary digits fill the next one hexadecimal digit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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