Binary representation. Any number can be written as the sum of distinct powers of 2.

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
jacksmack
Posts: 83
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

Binary representation. Any number can be written as the sum of distinct powers of 2.

Postby jacksmack » Fri Feb 03, 2017 12:17 pm UTC

Hi,

I have the following sentence:

Any number a can be written as the sum of distinct powers of 2.
i.e. we can write:
a = 2k1 + 2k2 + ... + 2kn,
where k1 < k2 < ... < kn.
This is the binary representation of a.

For example, the binary representation of 57 is 111001, since we can write 57 = 2^0 + 2^3 + 2^4 + 2^5
.

It's clear that 57 is 111001 because using repeated divisions we have:
57 = 2(28) + 1
28 = 2(14) + 0
14 = 2(7) + 0
7 = 2(3) + 1
3 = 2(1) + 1
1 = 2(0) + 1
and if we take the remainders from end to begin we obtain 111001.

But I don't understand the following part:
<< ... since we can write 57 = 2^0 + 2^3 + 2^4 + 2^5 >>
if I understand, the statement says that we can write 57 in that binary form, because 57 = 2^0 + 2^3 + 2^4 + 2^5.
But why it says that?

Please, can you help me? Many thanks!!

User avatar
Flumble
Yes Man
Posts: 1780
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Binary representation. Any number can be written as the sum of distinct powers of 2.

Postby Flumble » Fri Feb 03, 2017 1:15 pm UTC

jacksmack wrote:But why it says that?

Why does it say what?

It says we can write 57 as a sum of powers because of the previous statement that any number can be written as a sum of distinct powers of 2. What the statement doesn't say, though, is that it's restricted to non-negative numbers (and for non-integer numbers you nearly always need an infinite series) and that the sum is unique.

It says we can get the binary representation given a sum of powers of 2 (and this is what it doesn't say: ) because binary is also a sum of distinct powers of 2: the rightmost digit of binary counts ones (2^0), the digit to the left counts twos (2^1), the digit to the left counts fours (2^2) and so on. So whenever the digit value occurs in your sum of powers, you write a 1 at that position and otherwise a 0.

Code: Select all

power sum 57: 2^5 + 2^4 + 2^3       +       2^0
digit values: 2^5   2^4   2^3   2^2   2^1   2^0
binary of 57:  1     1     1     0     0     1


I hope others can come up with a better explanation, because this feels more like a reference than an explanation.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 1842
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Binary representation. Any number can be written as the sum of distinct powers of 2.

Postby Soupspoon » Fri Feb 03, 2017 2:02 pm UTC

I don't necessarily understand what isn't being understood, but let's try this...

Binary (of non-negative whole numbers) has each power of two represented 0 or 1 times. Because for any power of two, you may not need it to be part of the number or you may need it once to be part of that number.

If you try to use a power twice, then you're using 2*2n, which is 2n+1. (That's redundant. Either just use 2n+1 to start with, or if you already have 2n+1 then you're talking about 2*2n+1 which is 2n+2. Continue until you don't need to 'carry' the sum. Or just work top-down and avoid it.)

Binary is just a case like with every (positive, whole-number) base, including decimal.

A decimal number is (0..9) times each power of ten, just as binary is (0..1) times each power of two and hexadecimal is (0..15) times each power of sixteen. "2017" is seven "ten to the zero"s (7*1) one "ten to the one" (1*10) plus two "ten to the three" (2*1000). There are no "ten to the two"s. Unless you say there are twenty of them, but 20*102 is more than the 0..9 of them, and is 2*10 * 102, or 2 * 103, as already suggested.

Obviously if we could pack "2017" so as not to mention the zero number of hundreds, then we can miss that element out, and in a bk1+bk2+bk3+... type of format, we're listing the powers explicitly (like in Roman numeral version "MMXVII", we're stating "MM"+"X"+"VII" and skipping over the lack of "C"s), but because we use the otherwise efficient place-contexted numerals (no need to invent ways of depicting the value that is two handfuls more of Ms, or two handfuls of those or on as long as you want, just prepend the already known digits as many times as you need, at least until you find it better to go with a related system that has a power-of-ten offset) we need to note 2017 as distinct from 217.

But it can be uniquely recorded as 7*100 + 1*101 + 2*103, in longhand, with 0<1<3if you do the k1<k2<k3 thing. And binary just doesn't need the place-by-place multiple of the power because it either isn't there (0*) or is there (1*) whilst decimal can be absent (0*) or from one to nine times present ([1..9]*). Thus binary expansion is slightly simpler.


Is that useful? Or not the misunderstanding you were having?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25400
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Binary representation. Any number can be written as the sum of distinct powers of 2.

Postby gmalivuk » Fri Feb 03, 2017 3:25 pm UTC

jacksmack wrote:But I don't understand the following part:
<< ... since we can write 57 = 2^0 + 2^3 + 2^4 + 2^5 >>
if I understand, the statement says that we can write 57 in that binary form, because 57 = 2^0 + 2^3 + 2^4 + 2^5.
But why it says that?

Your repeated division is a quick way to calculate the binary form of any integer, and it corresponds to the fact that 57 = 2^0 + 2^3 + 2^4 + 2^5 = 1 + 8 + 16 + 32

Expressed another way, 57 = 1*2^5 + 1*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0.
That is exactly what it means for a number to have "111001" as its binary representation.
In the same way, 2*10^3 + 0*10^2 + 1*10^1 + 7*10^2 means a number has "2017" as its decimal representation.

Let's take a different number, for example 44

44 = 2(22) + 0, so you know the one's place (2^0) will have a 0 in it. (It's even, so it ends in 0 just like numbers divisible by ten end in 0 in the decimal system.)
22 = 2(11) + 0, so you know the two's place (2^1) will also have a 0 in it. (It's even when you divide by 2, which means the original number is divisible by 4, so it ends in 00 just like numbers divisible by a hundred end in 00 in the decimal system.)
11 = 2(5) + 1, so you know the four's place (2^2) will have a 1 in it. (It's odd when you divide by 4, which means it's not divisible by 8, so it ends in n00 for some n that isn't 0. In the decimal system, this is like how numbers that aren't divisible by 1000 end with two 0's, but not three. In binary, the only n that isn't 0 is 1)
5 = 2(2) + 1, so you know the eight's place (2^3) will have a 1 in it.
2 = 2(1) + 0, so you know the sixteen's place (2^4) will have a 0 in it.
1 = 2(0) + 1, so you know the thirty-two's place (2^5) will have a 1 in it.

This tells you that 44 = 32 + 8 + 4 and has a binary representation of 101100.

Do you understand why the repeated division algorithm tells you about the powers of two you need to add together to make a number?
In binary,
44 = 101100
22 = 10110
11 = 1011
5 = 101
2 = 10
1 = 1
The operations you do in the division algorithm just remove the last binary digit at each step. Noticing whether a number is even or odd is the same as noticing whether it has a 0 or 1 at the end of its binary form.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 2478
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Binary representation. Any number can be written as the sum of distinct powers of 2.

Postby Eebster the Great » Sat Feb 04, 2017 1:30 am UTC

Flumble wrote:It says we can write 57 as a sum of powers because of the previous statement that any number can be written as a sum of distinct powers of 2. What the statement doesn't say, though, is that it's restricted to non-negative numbers (and for non-integer numbers you nearly always need an infinite series) and that the sum is unique.

Not sure if you meant to put the last clause in the parenthetical, but the binary representation is not unique for 57. 57 = 0b111001 = 0b111000.111.... Similarly, in decimal notation, 57 = 56.999....


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests