0
\$\begingroup\$

If we have a binary sequence that is \$x\$ bits long, what are the minimum and maximum that can be represented in two's complement form?

The maximum is \$2^{x-1}-1\$, and the minimum is \$-2^{x-1}\$.

But why? How can it be shown that this is the case?

\$\endgroup\$
  • \$\begingroup\$ Should probably go in computer science. Also this is incredibly easy to google. But just to answer you. b00 = 0 b01 = 1 b10 = -1 b11 = -2 \$\endgroup\$ – lm317 Dec 16 '14 at 21:09
  • 1
    \$\begingroup\$ umm... I think b11 is -1 \$\endgroup\$ – PkP Dec 16 '14 at 21:19
  • \$\begingroup\$ lm317 you are mistaken. b10 is -2, b11 is -1 b00 is 0, and b01 is 1 \$\endgroup\$ – Jotorious Dec 16 '14 at 21:21
  • 1
    \$\begingroup\$ +1 for such a fun and easy question for once, while at the same time being a bit philosophic also \$\endgroup\$ – PkP Dec 16 '14 at 21:22
  • 2
    \$\begingroup\$ @PkP Philosophic? Really? It would be if it had an42 inside.. \$\endgroup\$ – Eugene Sh. Dec 16 '14 at 21:35
1
\$\begingroup\$

Look at 3 bits representation:

000 = 0
001 = 1
010 = 2
011 = 3
100 = -4
101 = -3
110 = -2
111 = -1

Half of the numbers are starting with '1', which is the sign bit. So half of the numbers are negative. It means that we have \$(2^x)/2 = 2^{(x-1)}\$ negative numbers. The rest are positive and zero.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

For x bits, there are 2x values.

In one's complement system there are two zeros and 2x-1 - 1 positive and the same number of negative values.

In two's complement system those are assigned so that there is only one zero and one more negative value than there are positive values.

The two's complement system is in use, because it stems from how simple hardware naturally operates. Think for example you car's odometer, which you have resetted to zero. Then put the gear on reverse, and drive backwards for 1 mile (Please don't do this in reality). Your odometer (if it's mechanical) will roll from 0000 to 9999. The two's complement system behaves similarly.

enter image description here


Edit: Added the picture to harvest an amazing amount of points from this question

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Odometer usually don't work that way except perhaps on very old cars. Authoritative reference: Ferris Bueller's Day Off (and lots of internet posts). \$\endgroup\$ – Spehro Pefhany Dec 16 '14 at 22:00
  • \$\begingroup\$ @SpehroPefhany, Works like it in my 1994 Nissan :D \$\endgroup\$ – PkP Dec 16 '14 at 22:01
0
\$\begingroup\$

For a binary sequence of X bits there are 2^x possible values.

Using unsigned integers to represent these then, you have the set from 0, 1, ...(2^x)-1. If one wanted to effectively shift the values down to have half negative and half positive, you would subtract 2^(x-1) (which is half the range) from every value, this giving you 0 - 2^(x-1),....,(2^x)-1 - (2^(x-1)).

Reorganizing the later term into 2^x- 2^(x-1) - 1 and recognizing, that y^x - y^(x-1) = y^(x-1), you then have your range, -(2^(x-1))...2^(x-1)-1.

This is done in implementation by negating the MSB, which by virtue of it's place value is half the range.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I made a mistake. y^x-y^(x-1) = y^(x-1) only works when y=2. it cant be generalized to every integer. 2^4 - 2^3 = 2^3, but only because the base is 2. 3^3 = 3^2 != 3^2 \$\endgroup\$ – Jotorious Dec 16 '14 at 23:08
0
\$\begingroup\$

In two's compliment, the most significant bit (furthest left) is reserved for the sign of the number, so that's why it's x-1. The reason that it is \$2^{x-1} -1\$ for positive numbers is that one of these is used for zero, while in the negative numbers, we start right out at -1.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is not right. In twos complement the MSB holds the negative of the value of the highest place value. 1011 is -8 + 0 + 2 + 1 = -5. twos complement is identical to unsigned binary, except the MSB is negated. \$\endgroup\$ – Jotorious Dec 16 '14 at 21:18
  • \$\begingroup\$ Kypalmer, @Jotorious, You're both right, although kypalmer's explanation is a bit unusual (which I actually like a lot) :D \$\endgroup\$ – PkP Dec 16 '14 at 21:25
  • \$\begingroup\$ I think you're meaning \$2^{x-1}\$ there, aren't you? \$\endgroup\$ – user17592 Dec 16 '14 at 21:45
  • \$\begingroup\$ Thanks, Yes that should have been in the exponent. \$\endgroup\$ – kypalmer Jan 23 '15 at 1:26

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.