8 ms·

Two's complement – You beauty

123 points by yogeswarant 10y ago

zardeh 10y ago
The 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.
- yogeswarant 10y ago
  Thanks. Good to know this.
  - d0mine 10y ago
    Bitwise opetations assume an infinite number of 1s on the left for negative numbers (2s compliment) e.g., ~-1 == 0 (-1 is an infinite number of 1s that are converted to 0 by ~ (invert) operator ). 3 == 011 2 == 010 1 == 001 0 == 000 -1 == ..111 -2 == ..110 -3 == ..101
- brandonbloom 10y ago
  That's a reasonable tradeoff for Python, but it's worth noting that there is a way to deal with this. Quoting from http://reference.wolfram.com/language/tutorial/IntegerAndNumberTheoreticalFunctions.html http://reference.wolfram.com/language/tutorial/IntegerAndNum... Bitwise operations are used in various combinatorial algorithms. They are also commonly used in manipulating bitfields in low‐level computer languages. In such languages, however, integers normally have a limited number of digits, typically a multiple of 8. Bitwise operations in the Wolfram Language in effect allow integers to have an unlimited number of digits. When an integer is negative, it is taken to be represented in two's complement form, with an infinite sequence of ones on the left. This allows BitNot[n] to be equivalent simply to (-1 - n).
  - gpvos 10y ago
    Yes, but how would you print that infinite sequence of 1s?
    - ema 10y ago
      same as the infinite number of zeros in front of a positive number.
      - AstralStorm 10y ago
        Just trimming 1s would be ambiguous. Is b11 3 or -2? You would have to add a 0 prefix to all positive numbers or some other to negative.
        brandonbloom 10y ago
        Just prefix a + or - just like you do for base 10.
        gpvos 10y ago
        So then it would not make much of a difference anymore with what Python does. Which was what they wanted to avoid.
- throwawayish 10y ago
  Indeed. For this use case to_bytes would be correct (writing this in the most verbose way possible :) >>> (-352).to_bytes(length=4, byteorder='big', signed=True).hex() 'fffffea0' >>> (352).to_bytes(length=4, byteorder='big', signed=True).hex() '00000160' Note how well-defined and independent of the actual machine this conversion is. Since you define everything - length, byte order and whether to get two's complement or not - you'll get the same output everywhere.
0xcde4c3db 10y ago
> 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.
- jacobolus 10y ago
  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).
- kybernetikos 10y ago
  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.
  - AstralStorm 10y ago
    No Signum function is a bane in many languages.
  - SamBam 10y ago
    Weird. I just tried it out. So in Javascript you can have two variables, `a` and `b`, such that `a === b` and `1/a !== 1/b`.
- phire 10y ago
  By the time you have implemented enough silicon for floating point addition and multiplication, the amount of extra transistors you would need to special case the compare operator's zero case is realtivily tiny. The same can not be said for an interger alu (especially one without hardware multipliers or even arbitrary bit shifts), where twos complement representation can save a much larger percentage of silicon.
vog 10y ago
This 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.
- russdill 10y ago
  You'd love finite fields.
  - joatmon-snoo 10y ago
    And groups!
    - gizmo686 10y ago
      Don't forget about rings.
      - jmartinpetersen 10y ago
        I always found those ideal.
BuuQu9hu 10y ago
This is halfway to p-adic numbers and quote notation.
- deleted 10y ago
  [deleted]
Elrac 10y ago
I 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.
- gumby 10y ago
  > 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. This is why the FTP protocol has a byte size command. If all you have is 8-bit bytes then that seems strange. But at the time FTP was designed the most common machines on the ARPANET had 36-bit words (mostly PDP-10s and their derivatives) and bytes (the term was used in the more general sense) were just bit strings of 1-36 bits. 7-bit ascii was common (5 characters would fit in a word, like my username GUMBY), as were six bit bytes (pack six characters into a word). I never used 9-bit characters though arrays of nine-bit bytes were not unreasonable. BTW the PDP-10 had 18-bit addresses so each word of memory held a Lisp cons; CAR, CDR, RPLACA etc were machine instructions. Gordon Bell and Alan Kotok designed the -10 (and its predecessor the PDP-6) with Lisp in mind. The first Lisp Machines. > Binary data formats are essentially incompatible with anything. Well, that's true today, but look at it the other way around: Unix was really developed for an 8/16-bit machine. It was a reimplementation of Multics that ran on a 36-bit machine (GE 645 & Honeywell 6180) written in PL/1. Unix was famously written for the PDP-7 (an 18-bit machine) but it was written in assembly. The famous PDP-11 version was written in a BCPL derivative you might have heard of called "C" and, since PL/1's level of machine abstraction was still new, the derivative modeled the PDP-11 architecture. So nowadays all CPUs are C machines and C runs well on them. Probably the most common non-PDP-11-like machine most programmers will program these days is a GPU.
gumby 10y ago
> I was not curious to ask what is the need for one's complement or two's complement. A problem with school, not the student (a common problem IMHO). Good write up!
bsder 10y ago
While two's complement is quite clever, it's not an obvious choice when you are building things out of tubes or relays. One's complement has two very nice properties: 1) the range is symmetric 2) "end-around carry" makes all the bits look identical in terms of implementation
- bogomipz 10y ago
  But isn't that drawback of 1's complement that 0 in an 8 bit number can be represented two different ways? 0000 0000 and 1111 1111
  - bsder 10y ago
    Is it a drawback? If your "compare to 0" is "are all bits the same", then it would be an advantage. An asymmetric range is a "drawback" of two's complement. Is that a drawback? It depends upon what your building blocks in the technology are. For example, we don't use J-K flip flops anymore because they are a pain to make and use when MOSFET's are your building blocks (J-K wants bipolars).
eps 10y ago
It's an elegant construct, but this used to be a part of an entry-level course in every computer school I know of. Have things changed now?
- grendelt 10y ago
  "Why, when I was your age..."
- metaphor 10y ago
  US universities with ABET-accredited programs teach 1's/2's complement to freshman EE/CpE majors in a first course on digital logic, which typical doesn't have any prerequisites.
- Coincoin 10y ago
  My thought exactly when I read this kind of articles. Am I that old that they don't teach those simple concepts anymore?
- TillE 10y ago
  I suspect lots of people here have little or no higher education. Mine was 10+ years ago, so an occasional refresher can be nice; I remember the general concepts, but not necessarily the details.
  - ashark 10y ago
    The category of Things I Once Knew but Have Since Forgotten because I Don't Them Often Enough probably includes 95+% of everything I've ever learned about both mathematics and computers/programming. The people on here who rattle off the names of various mathematical theorems like it's nothing and act like it's weird not to remember how intro-level algorithms work without thinking really hard and doing some trial-and-error for a while or consulting a reference must have much more interesting jobs than I ever have. :-/
1010111 10y ago
Shitty C code: the binary printing function is needlessly complicated. void print_bin(int x){ for(unsigned m=~(~0u>>1); m ; m>>=1) putchar(x&m?'1':'0'); putchar('\n'); }
- FoolForCS 10y ago
  On the contrary I'd say. When you're talking about low level (and basic CS101 details like 2's complement) I think it makes sense to be lucid rather than "needlessly complicated short" code that does too much in a single line.
- yellowapple 10y ago
  Shitty C code: I've seen Perl golfs more readable than this. The article's code is more explicit and verbose, which makes it easier for non-C-programmers (like myself) to actually understand what's going on.
  - 1010111 10y ago
    It uses a bit mask from the leftmost bit to the rightmost and prints the respective bits in x. Is that more complicated than allocating memory on the heap, storing the bits, and then printing them in reverse? Also the code above does not contain anything C specific, with the exception of 'putchar' let's say.
  - todd8 10y ago
    Understandably confusing for a non-C-programmer, but it is idiomatic C. It's not code golf; it's just the way one does machine independent bit twiddling. A mask is used to test each bit position in turn. The tests look like this if written using binary literals: 0b1000 & x 0b0100 & x 0b0010 & x 0b0001 & x The '&' is the bitwise AND opperator in C. Of course, we'd have to do as many of these as the word size so 1010111 uses a for loop that starts with the first mask, a 1 in the leftmost position, and shifts it right one position every time through the loop (using the C right shift operator >> on an unsigned mask value). When the one bit is eventually shifted out the right side of the mask, the mask is all zeros so the loop terminates because zero acts like false in the for loop test. The only other tricky thing is initializing the mask. To set only the leftmost bit in a word the code uses the bit complement operator ~ of C. Breaking it down for a four bit example looks like: 0u == 0b0000 ~0u == 0b1111 ~0u >> 1 == 0b0111 ~(~0u >> 1) == 0b1000 This is the expression that appears in the for loop initializing the mask value, and it works for any word size. The original article's code was definitely not idiomatic, efficient, or safe (the memory allocation for an array of characters could fail and segfault). The book Hacker's Delight is a great reference for those wanting to understand how to do low level coding, a requirement for close to the hardware work like writing device drivers.
chii 10y ago
the https://en.wikipedia.org/wiki/Method_of_complements https://en.wikipedia.org/wiki/Method_of_complements article explains a more fundamental piece of information about this operation - i often see articles explaining two's complement, but doesn't say anything about this general 'complement' method (which works for all bases, not just binary).
- bogomipz 10y ago
  Thanks for the link, the article mentions usage of complements in machines going back to mechanical calculators and the first example uses 9's complement. Neat!
- ramshorns 10y ago
  > In the decimal numbering system, the radix complement is called the ten's complement and the diminished radix complement the nines' complement. In binary, the radix complement is called the two's complement and the diminished radix complement the ones' complement. The naming of complements in other bases is similar. Some people, notably Donald Knuth, recommend using the placement of the apostrophe to distinguish between the radix complement and the diminished radix complement. In this usage, the four's complement refers to the radix complement of a number in base four while fours' complement is the diminished radix complement of a number in base 5. That makes sense. The names one's complement and two's complement are kind of confusing otherwise, since they actually refer to totally different things, and it's not clear how they would generalize to higher bases.
crawfordcomeaux 10y ago
Would it be possible to use - 0 & +0 in useful ways, like determining "direction" of previous operation? No clue how that could be useful, but I'm betting there's a use case out there.
- cmrx64 10y ago
  Yes! Although I'm not sure if it would ever be useful for integers, it's vital in floating point: https://people.freebsd.org/~das/kahan86branch.pdf https://people.freebsd.org/~das/kahan86branch.pdf
signa11 10y ago
you could as well provide an explicit mask to help (how far does the sign extend) python f.e a 'bin(-5 & 0b1111)' gives '0b1011' which is what you want
laszlokorte 10y ago
A widget I built last year for interactively visualizing a number circle with various binary interpretations: https://thesis.laszlokorte.de/demo/number-circle.html https://thesis.laszlokorte.de/demo/number-circle.html
- colejohnson66 10y ago
  That's really cool! However, I can drag the SVG's viewbox around; something I wouldn't expect to be able to do. EDIT: It makes sense when you zoom in (like you would with 7 bits), but if I'm zoomed out all the way, I wouldn't' expect to be able to pan around. I'd expect it to prevent panning past the edge.
  - laszlokorte 10y ago
    Makes sense - thanks for the suggestion :)
morecoffee 10y ago
Probably the most interesting part of 2's complement is how to negate numbers. Flip all the bits and add 1. Which is strange, because to negate the number again, flip all the bits and add 1. It feels like accidentally adding 2 doesn't it?
dnautics 10y ago
There is that wierd number 100000...0000 which is that extra negative number with no positive analog. I'm currently working with a noninteger value representation system that hijacks this value and assigns it as +/- infinity (negation is two's complement)
vanderZwan 10y ago
One thing that I find very fascinating about Gustavson's Unum work is that he proposes a lot of interesting ideas - not all new, as he is happy to remind you of himself - for encoding numbers: > Type 2 unums are a direct map of signed integers to the projective real number line. The projective reals map the reals onto a circle, so positive and negative infinity meet at the top. http://deliveryimages.acm.org/10.1145/3010000/3001758/ins01.gif http://deliveryimages.acm.org/10.1145/3010000/3001758/ins01.... He also proposes to include the reciprocal of every included number in this projection, leading to a very nice property: > To negate a unum, you negate the integer associated with the bit string, as if that integer was a standard two's complement number. Flip the bits and add one, ignoring any overflow; that gives you the negative of an integer. It works with no exceptions. But get this: To reciprocate a unum, you ignore the first bit and negate what remains! Geometrically, negating is like revolving the circle about the vertical axis and reciprocating is revolving it about the horizontal axis. And yes, the reciprocal of zero is ±∞ and vice versa. http://ubiquity.acm.org/article.cfm?id=3001758 http://ubiquity.acm.org/article.cfm?id=3001758 http://www.johngustafson.net/presentations/Unums2.0.pdf http://www.johngustafson.net/presentations/Unums2.0.pdf
gravypod 10y ago
int bitlen = sizeof(i) * 8; I wish life was this simple.
deleted 10y ago
[deleted]
white-flame 10y ago
Looking at limited-digit odometer style devices gives the best example of why 2's complement is saner. ... or ... 9998 1110 9999 1111 0000 0000 0001 0001 0002 0010 ... What number is before 0 in binary? 1111. So that's where -1 is. The number before that? 1110, so that's -2. The whole XOR + 1 thing can be derived from this shape. That, and simple addition of both signed and unsigned numbers actually works. :) The only question is where you draw the line between underflowing negatives and overflowing positives, and going halfsies on the top bit seems to make sense. For an 8-bit number, there are 128 numbers on each of the negative/non-negative split, but zero mucks it up by being not mathematically positive. 1's complement evens it out by having 127 numbers on each side plus two zeros, but messes up signed math.
user51442 10y ago
The Universe is two's complement. Item 154 of HAKMEM: http://catb.org/jargon/html/H/HAKMEM.html http://catb.org/jargon/html/H/HAKMEM.html
paulddraper 10y ago
If you're looking for true beauty, look no further than negabinary. (http://mathworld.wolfram.com/Negabinary.html http://mathworld.wolfram.com/Negabinary.html) E.g. 3 = (-2)^2 + (-2)^1 + (-2)^0 = 0110_-2 -3 = (-2)^3 + (-2)^2 + (-2)^0 = 1101_-2 There is no signed bit, you don't have to worry about sign; everything just works like "normal" numbers because that in fact is what it is. A pity it was never used except a few times in early computing. I'm never sure why 2's-complement won.
- jonsen 10y ago
  ...why 2's-complement won. Maybee conversion to/from character code is easier. Notice the conversion code in the linked article.
  - paulddraper 10y ago
    > conversion to/from character code is easier (1) How often do you convert from machine integers to binary character representations? (2) If you're referring to for(j = 0; j < bitlen; j++) { bin[j] = (i & 1) ? '1': '0'; i >>= 1; } that's the exact same for a negabinary machine.
    - jonsen 10y ago
      I meant to/from numbers in text form. Usually decimal.
      - deleted 10y ago
        [deleted]
- deleted 10y ago
  [deleted]

123 points by yogeswarant 10y ago

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

yogeswarant 10y ago
Thanks. Good to know this.
- d0mine 10y ago
  Bitwise opetations assume an infinite number of 1s on the left for negative numbers (2s compliment) e.g., ~-1 == 0 (-1 is an infinite number of 1s that are converted to 0 by ~ (invert) operator ). 3 == 011 2 == 010 1 == 001 0 == 000 -1 == ..111 -2 == ..110 -3 == ..101
brandonbloom 10y ago
That's a reasonable tradeoff for Python, but it's worth noting that there is a way to deal with this. Quoting from http://reference.wolfram.com/language/tutorial/IntegerAndNumberTheoreticalFunctions.html http://reference.wolfram.com/language/tutorial/IntegerAndNum... Bitwise operations are used in various combinatorial algorithms. They are also commonly used in manipulating bitfields in low‐level computer languages. In such languages, however, integers normally have a limited number of digits, typically a multiple of 8. Bitwise operations in the Wolfram Language in effect allow integers to have an unlimited number of digits. When an integer is negative, it is taken to be represented in two's complement form, with an infinite sequence of ones on the left. This allows BitNot[n] to be equivalent simply to (-1 - n).
- gpvos 10y ago
  Yes, but how would you print that infinite sequence of 1s?
  - ema 10y ago
    same as the infinite number of zeros in front of a positive number.
    - AstralStorm 10y ago
      Just trimming 1s would be ambiguous. Is b11 3 or -2? You would have to add a 0 prefix to all positive numbers or some other to negative.
      - brandonbloom 10y ago
        Just prefix a + or - just like you do for base 10.
        gpvos 10y ago
        So then it would not make much of a difference anymore with what Python does. Which was what they wanted to avoid.
throwawayish 10y ago
Indeed. For this use case to_bytes would be correct (writing this in the most verbose way possible :) >>> (-352).to_bytes(length=4, byteorder='big', signed=True).hex() 'fffffea0' >>> (352).to_bytes(length=4, byteorder='big', signed=True).hex() '00000160' Note how well-defined and independent of the actual machine this conversion is. Since you define everything - length, byte order and whether to get two's complement or not - you'll get the same output everywhere.

0xcde4c3db 10y ago

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

jacobolus 10y ago
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).
kybernetikos 10y ago
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.
- AstralStorm 10y ago
  No Signum function is a bane in many languages.
- SamBam 10y ago
  Weird. I just tried it out. So in Javascript you can have two variables, `a` and `b`, such that `a === b` and `1/a !== 1/b`.
phire 10y ago
By the time you have implemented enough silicon for floating point addition and multiplication, the amount of extra transistors you would need to special case the compare operator's zero case is realtivily tiny. The same can not be said for an interger alu (especially one without hardware multipliers or even arbitrary bit shifts), where twos complement representation can save a much larger percentage of silicon.

vog 10y ago

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

russdill 10y ago
You'd love finite fields.
- joatmon-snoo 10y ago
  And groups!
  - gizmo686 10y ago
    Don't forget about rings.
    - jmartinpetersen 10y ago
      I always found those ideal.

BuuQu9hu 10y ago

This is halfway to p-adic numbers and quote notation.

deleted 10y ago
[deleted]

Elrac 10y ago

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

gumby 10y ago
> 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. This is why the FTP protocol has a byte size command. If all you have is 8-bit bytes then that seems strange. But at the time FTP was designed the most common machines on the ARPANET had 36-bit words (mostly PDP-10s and their derivatives) and bytes (the term was used in the more general sense) were just bit strings of 1-36 bits. 7-bit ascii was common (5 characters would fit in a word, like my username GUMBY), as were six bit bytes (pack six characters into a word). I never used 9-bit characters though arrays of nine-bit bytes were not unreasonable. BTW the PDP-10 had 18-bit addresses so each word of memory held a Lisp cons; CAR, CDR, RPLACA etc were machine instructions. Gordon Bell and Alan Kotok designed the -10 (and its predecessor the PDP-6) with Lisp in mind. The first Lisp Machines. > Binary data formats are essentially incompatible with anything. Well, that's true today, but look at it the other way around: Unix was really developed for an 8/16-bit machine. It was a reimplementation of Multics that ran on a 36-bit machine (GE 645 & Honeywell 6180) written in PL/1. Unix was famously written for the PDP-7 (an 18-bit machine) but it was written in assembly. The famous PDP-11 version was written in a BCPL derivative you might have heard of called "C" and, since PL/1's level of machine abstraction was still new, the derivative modeled the PDP-11 architecture. So nowadays all CPUs are C machines and C runs well on them. Probably the most common non-PDP-11-like machine most programmers will program these days is a GPU.

gumby 10y ago

> I was not curious to ask what is the need for one's complement or two's complement. A problem with school, not the student (a common problem IMHO). Good write up!

bsder 10y ago

While two's complement is quite clever, it's not an obvious choice when you are building things out of tubes or relays. One's complement has two very nice properties: 1) the range is symmetric 2) "end-around carry" makes all the bits look identical in terms of implementation

bogomipz 10y ago
But isn't that drawback of 1's complement that 0 in an 8 bit number can be represented two different ways? 0000 0000 and 1111 1111
- bsder 10y ago
  Is it a drawback? If your "compare to 0" is "are all bits the same", then it would be an advantage. An asymmetric range is a "drawback" of two's complement. Is that a drawback? It depends upon what your building blocks in the technology are. For example, we don't use J-K flip flops anymore because they are a pain to make and use when MOSFET's are your building blocks (J-K wants bipolars).

eps 10y ago

It's an elegant construct, but this used to be a part of an entry-level course in every computer school I know of. Have things changed now?

grendelt 10y ago
"Why, when I was your age..."
metaphor 10y ago
US universities with ABET-accredited programs teach 1's/2's complement to freshman EE/CpE majors in a first course on digital logic, which typical doesn't have any prerequisites.
Coincoin 10y ago
My thought exactly when I read this kind of articles. Am I that old that they don't teach those simple concepts anymore?
TillE 10y ago
I suspect lots of people here have little or no higher education. Mine was 10+ years ago, so an occasional refresher can be nice; I remember the general concepts, but not necessarily the details.
- ashark 10y ago
  The category of Things I Once Knew but Have Since Forgotten because I Don't Them Often Enough probably includes 95+% of everything I've ever learned about both mathematics and computers/programming. The people on here who rattle off the names of various mathematical theorems like it's nothing and act like it's weird not to remember how intro-level algorithms work without thinking really hard and doing some trial-and-error for a while or consulting a reference must have much more interesting jobs than I ever have. :-/

1010111 10y ago

Shitty C code: the binary printing function is needlessly complicated. void print_bin(int x){ for(unsigned m=~(~0u>>1); m ; m>>=1) putchar(x&m?'1':'0'); putchar('\n'); }

FoolForCS 10y ago
On the contrary I'd say. When you're talking about low level (and basic CS101 details like 2's complement) I think it makes sense to be lucid rather than "needlessly complicated short" code that does too much in a single line.
yellowapple 10y ago
Shitty C code: I've seen Perl golfs more readable than this. The article's code is more explicit and verbose, which makes it easier for non-C-programmers (like myself) to actually understand what's going on.
- 1010111 10y ago
  It uses a bit mask from the leftmost bit to the rightmost and prints the respective bits in x. Is that more complicated than allocating memory on the heap, storing the bits, and then printing them in reverse? Also the code above does not contain anything C specific, with the exception of 'putchar' let's say.
- todd8 10y ago
  Understandably confusing for a non-C-programmer, but it is idiomatic C. It's not code golf; it's just the way one does machine independent bit twiddling. A mask is used to test each bit position in turn. The tests look like this if written using binary literals: 0b1000 & x 0b0100 & x 0b0010 & x 0b0001 & x The '&' is the bitwise AND opperator in C. Of course, we'd have to do as many of these as the word size so 1010111 uses a for loop that starts with the first mask, a 1 in the leftmost position, and shifts it right one position every time through the loop (using the C right shift operator >> on an unsigned mask value). When the one bit is eventually shifted out the right side of the mask, the mask is all zeros so the loop terminates because zero acts like false in the for loop test. The only other tricky thing is initializing the mask. To set only the leftmost bit in a word the code uses the bit complement operator ~ of C. Breaking it down for a four bit example looks like: 0u == 0b0000 ~0u == 0b1111 ~0u >> 1 == 0b0111 ~(~0u >> 1) == 0b1000 This is the expression that appears in the for loop initializing the mask value, and it works for any word size. The original article's code was definitely not idiomatic, efficient, or safe (the memory allocation for an array of characters could fail and segfault). The book Hacker's Delight is a great reference for those wanting to understand how to do low level coding, a requirement for close to the hardware work like writing device drivers.

chii 10y ago

the https://en.wikipedia.org/wiki/Method_of_complements https://en.wikipedia.org/wiki/Method_of_complements article explains a more fundamental piece of information about this operation - i often see articles explaining two's complement, but doesn't say anything about this general 'complement' method (which works for all bases, not just binary).

bogomipz 10y ago
Thanks for the link, the article mentions usage of complements in machines going back to mechanical calculators and the first example uses 9's complement. Neat!
ramshorns 10y ago
> In the decimal numbering system, the radix complement is called the ten's complement and the diminished radix complement the nines' complement. In binary, the radix complement is called the two's complement and the diminished radix complement the ones' complement. The naming of complements in other bases is similar. Some people, notably Donald Knuth, recommend using the placement of the apostrophe to distinguish between the radix complement and the diminished radix complement. In this usage, the four's complement refers to the radix complement of a number in base four while fours' complement is the diminished radix complement of a number in base 5. That makes sense. The names one's complement and two's complement are kind of confusing otherwise, since they actually refer to totally different things, and it's not clear how they would generalize to higher bases.

crawfordcomeaux 10y ago

Would it be possible to use - 0 & +0 in useful ways, like determining "direction" of previous operation? No clue how that could be useful, but I'm betting there's a use case out there.

cmrx64 10y ago
Yes! Although I'm not sure if it would ever be useful for integers, it's vital in floating point: https://people.freebsd.org/~das/kahan86branch.pdf https://people.freebsd.org/~das/kahan86branch.pdf

signa11 10y ago

you could as well provide an explicit mask to help (how far does the sign extend) python f.e a 'bin(-5 & 0b1111)' gives '0b1011' which is what you want

laszlokorte 10y ago

A widget I built last year for interactively visualizing a number circle with various binary interpretations: https://thesis.laszlokorte.de/demo/number-circle.html https://thesis.laszlokorte.de/demo/number-circle.html

colejohnson66 10y ago
That's really cool! However, I can drag the SVG's viewbox around; something I wouldn't expect to be able to do. EDIT: It makes sense when you zoom in (like you would with 7 bits), but if I'm zoomed out all the way, I wouldn't' expect to be able to pan around. I'd expect it to prevent panning past the edge.
- laszlokorte 10y ago
  Makes sense - thanks for the suggestion :)

morecoffee 10y ago

Probably the most interesting part of 2's complement is how to negate numbers. Flip all the bits and add 1. Which is strange, because to negate the number again, flip all the bits and add 1. It feels like accidentally adding 2 doesn't it?

dnautics 10y ago

There is that wierd number 100000...0000 which is that extra negative number with no positive analog. I'm currently working with a noninteger value representation system that hijacks this value and assigns it as +/- infinity (negation is two's complement)

vanderZwan 10y ago

One thing that I find very fascinating about Gustavson's Unum work is that he proposes a lot of interesting ideas - not all new, as he is happy to remind you of himself - for encoding numbers: > Type 2 unums are a direct map of signed integers to the projective real number line. The projective reals map the reals onto a circle, so positive and negative infinity meet at the top. http://deliveryimages.acm.org/10.1145/3010000/3001758/ins01.gif http://deliveryimages.acm.org/10.1145/3010000/3001758/ins01.... He also proposes to include the reciprocal of every included number in this projection, leading to a very nice property: > To negate a unum, you negate the integer associated with the bit string, as if that integer was a standard two's complement number. Flip the bits and add one, ignoring any overflow; that gives you the negative of an integer. It works with no exceptions. But get this: To reciprocate a unum, you ignore the first bit and negate what remains! Geometrically, negating is like revolving the circle about the vertical axis and reciprocating is revolving it about the horizontal axis. And yes, the reciprocal of zero is ±∞ and vice versa. http://ubiquity.acm.org/article.cfm?id=3001758 http://ubiquity.acm.org/article.cfm?id=3001758 http://www.johngustafson.net/presentations/Unums2.0.pdf http://www.johngustafson.net/presentations/Unums2.0.pdf

gravypod 10y ago

int bitlen = sizeof(i) * 8; I wish life was this simple.

deleted 10y ago

[deleted]

white-flame 10y ago

Looking at limited-digit odometer style devices gives the best example of why 2's complement is saner. ... or ... 9998 1110 9999 1111 0000 0000 0001 0001 0002 0010 ... What number is before 0 in binary? 1111. So that's where -1 is. The number before that? 1110, so that's -2. The whole XOR + 1 thing can be derived from this shape. That, and simple addition of both signed and unsigned numbers actually works. :) The only question is where you draw the line between underflowing negatives and overflowing positives, and going halfsies on the top bit seems to make sense. For an 8-bit number, there are 128 numbers on each of the negative/non-negative split, but zero mucks it up by being not mathematically positive. 1's complement evens it out by having 127 numbers on each side plus two zeros, but messes up signed math.

user51442 10y ago

The Universe is two's complement. Item 154 of HAKMEM: http://catb.org/jargon/html/H/HAKMEM.html http://catb.org/jargon/html/H/HAKMEM.html

paulddraper 10y ago

If you're looking for true beauty, look no further than negabinary. (http://mathworld.wolfram.com/Negabinary.html http://mathworld.wolfram.com/Negabinary.html) E.g. 3 = (-2)^2 + (-2)^1 + (-2)^0 = 0110_-2 -3 = (-2)^3 + (-2)^2 + (-2)^0 = 1101_-2 There is no signed bit, you don't have to worry about sign; everything just works like "normal" numbers because that in fact is what it is. A pity it was never used except a few times in early computing. I'm never sure why 2's-complement won.

jonsen 10y ago
...why 2's-complement won. Maybee conversion to/from character code is easier. Notice the conversion code in the linked article.
- paulddraper 10y ago
  > conversion to/from character code is easier (1) How often do you convert from machine integers to binary character representations? (2) If you're referring to for(j = 0; j < bitlen; j++) { bin[j] = (i & 1) ? '1': '0'; i >>= 1; } that's the exact same for a negabinary machine.
  - jonsen 10y ago
    I meant to/from numbers in text form. Usually decimal.
    - deleted 10y ago
      [deleted]
deleted 10y ago
[deleted]