Two's complement – You beauty
everyogi.in
Two's complement – You beauty
1–10 of 92 posts
Re: Two's complement – You beauty
#2The python result should be expected. Python's integer type isn't sized, that is python will happily give you factorial(100), despite it being much larger than 64 bits. It can't then give you twos complement, because it can't know the size with which to complement the two.
Re: Two's complement – You beauty
#3The python result should be expected. Python's integer type isn't sized, that is python will happily give you factorial(100), despite it being much larger than 64 bits. It can't then give you twos complement, because it can't know the size with which to complement the two.
Thanks. Good to know this.
Re: Two's complement – You beauty
#4> There would be two ways to represent 0, as +0 and -0.
IEEE 754 floating point actually has this (due to having a dedicated sign bit). I think most code doesn't care (IIRC they are defined as equal for comparison purposes even though the bits are different in memory), but apparently it's sometimes handy to have for some functions that have a discontinuity at zero or otherwise need to preserve the sign through a multiplication by zero.
Re: Two's complement – You beauty
#5> There would be two ways to represent 0, as +0 and -0. IEEE 754 floating point actually has this (due to having a dedicated sign bit). I think most code doesn't care (IIRC they are defined as equal for comparison purposes even though the bits are different in memory), but apparently it's sometimes handy to have for some functions that have a discontinuity at zero or otherwise need to preserve the sign through a mult…
You sometimes want to be able to distinguish positive underflow from negative underflow. In the same way you sometimes want to distinguish positive overflow (infinity) from negative overflow (minus infinity).
Re: Two's complement – You beauty
#6This all is suddenly less surprising for people who learned some modulo arithmetics in school (or university). That is, calculating with the remainders of division. For example:
- Calculating "modulo 60" means calculating time with a round clock in mind, considering only minutes and ignoring hours (and seconds).
- Calculating with angles (in degrees) means just calculating "modulo 360".
- "modulo 1000" means calculating with the last 3 decimal digits of an integer, ignoring the front digits.
The fundamental result here is: No matter modulo which number you calculate: addition, negation, subtraction and multiplication work "out of the box". And you'll quickly notice that "two's complement" just means calculating modulo 2^n, where n=8,16,32,64 or 128. But this all really works for any m >= 2, not just m = 2^n.
(One drawback though: division doesn't work here, it works only if m is prime, and even then it is slightly different from what you'd expect, although completely logical.)
In short, the elegance comes from modulo arithmetics. It has nothing to do with "two" or "binary", it would e.g. work with 3-state logic machines the same way.
EDIT: To those who downvoted this: Do you care to elaborate? The author did't mention modulo arithmetics with a single word, although it is an essential part to truly understand how and why two's complement works.
Re: Two's complement – You beauty
#7This all is suddenly less surprising for people who learned some modulo arithmetics in school (or university). That is, calculating with the remainders of division. For example: - Calculating "modulo 60" means calculating time with a round clock in mind, considering only minutes and ignoring hours (and seconds). - Calculating with angles (in degrees) means just calculating "modulo 360". - "modulo 1000" means calculat…
You'd love finite fields.
Re: Two's complement – You beauty
#8This is halfway to p-adic numbers and quote notation.
Re: Two's complement – You beauty
#9I program a UNISYS 2200 mainframe at work. It uses 1's complement.
Yes, there are two zeros. Not a problem in practice because all arithmetic operations normalize -0 to +0 at no extra cost in execution time, so -0 practially doesn't happen. IIRC from Assembler class, addition is implemented as subtraction of the negative operand. Just in case anyone ever needs it, e.g. for bitmaps, the SZ (store zero) assembler instruction is complemented by a SNZ.
Programming in a high level language, the representation of negative numbers is all but transparent to the programmer. When reading dumps, not having to perform an extra addition (subtraction?) when changing a number's sign is pretty sweet! Also, abs(-MAXINT) == (+MAXINT), reliably. The asymmetry of number ranges always bothered me on 2's complement machines.
What _is_ annoying about the UNISYS boxes is the 36 bit word format, though. Characters are stored in 9 bit quarterwords that map pretty awkwardly to bytes containing 8-bit ASCII. Binary data formats are essentially incompatible with anything.
Re: Two's complement – You beauty
#10> There would be two ways to represent 0, as +0 and -0. IEEE 754 floating point actually has this (due to having a dedicated sign bit). I think most code doesn't care (IIRC they are defined as equal for comparison purposes even though the bits are different in memory), but apparently it's sometimes handy to have for some functions that have a discontinuity at zero or otherwise need to preserve the sign through a mult…
Because of this, javascript has a +0 and a -0. They make a fun trivia question because there are very few ways to distinguish them since most of the ways of checking equality (even ===) will report that they are equal.
In fact, I only know two ways to distinguish them: divide something by them, and you get positive infinity for +0 and negative infinity for -0, or you can use Object.is(-0, 0) which will return false.