5 ms·
A gentle introduction to two's complement
- kr0bat 3y agoTo find the two’s complement of 5, we invert all the bits (changing 0s to 1s and 1s to 0s) and then add one to the result. I am embarrassed by the fact that I wasn't aware of this. I always interpreted the two's complement as the difference between the all the numbers before the high bit, minus the high bit. Aka 10000000 – 01111011 = 0101
- KMag 3y agoOne of the advantages of two's compliment (particularly relevant in early hardware that really needed to minimize gate count) is that you can use an adder to perform subtraction: just flip all of the bits of the argument to subtract, and have an extra carry input to pretend you have a carry-in bit to be added to the least significant bit. If you want your CPU to efficiently support multi-precision addition, you can have an overflow machine state flag and have an instruction that uses that overflow flag as the carry-in to the least significant bit during addition.
- YiraldyGuber 3y agoI find it much easier to think of everything in unsigned terms. If I want 8bit -5, I really want 256-5=251. I've done plenty of that in my time but I don't think I've once consciously inverted bits and added 1.
- svat 3y agoThat it's the same thing may be more familiar in base 10: for example with 3-digit numbers, the 10's complement of (say) 428 is 1000-428 = 572, and you get the same result if you "invert" each digit (subtract from 9) and add 1: 571 + 1 = 572. This is just because (999-x)+1 = 1000-x.
- dperrin 3y agoWhen I first learned two's complement I sort of accepted it as something to memorise for a test and didn't really understand (or care) why it worked. What really made it click for me was thinking of it as modular arithmetic. If you consider 8-bit integers, they range from 0-255 and you're actually working modulo 256. So you can think of 0-127 as your non-negative numbers. The numbers from 128-255 behave as negatives modulo 256 (e.g. -1 mod 256 = 255).
- mrdoornbos 3y agoGood point; I wish I'd added that.
- o11c 3y agoApplying the unary "negate" operation isn't particularly useful test. For reference (and note the apostrophe locations): * sign-magnitude is slightly easier for multiplication/division but makes addition/subtraction marginally harder. It's widely used in bigint libraries, and IEEE binary floats use a variant of it (unlike IEEE decimal floats, which are not at all sane). * two's complement is optimal for addition/subtraction, but has a weird "most negative" value. Fixed-width multiplication and division have a couple warts but . * ones' complement is not particularly useful compared to the above two choices, though I suppose it's marginally easier to sort than sign-magnitude * offset-binary is useful for naive sorting, but casting to/from unsigned is not a nop. For two's complement at least, to avoid the UB you can just cast to/from unsigned around most operations. Division has to be done with some kind of branches, however. I rather wish we had an integer `NaN` instead of the most-negative value. Also, there are several useful overflow behaviors: trap, wrap, saturate, unspecified, and undefined. "unspecified" is particularly useful if you're sometimes transpiling to a JS-like language that doesn't actually support integers.
- tialaramex 3y agoI don't think an integer NaN would be a good idea. People's intuition around the existing float NaNs is not good. I want to make user defined types like BalancedI32 (32bit signed integer but the magnitude of MAX and MIN are the same) possible in Rust. Today the stdlib is allowed to make NonZeroI32 which as its name suggests lacks zero but you can't make such types yourself except via wrapping these NonZero types with xor or similar. (In nightly Rust you can just break the rules and do the same thing the stdlib does, but there's no obligation to keep that working and it will never be stabilized) Because of the Guaranteed Niche Optimisation this means Option<BalancedI32> would have identical size to i32. So you get the same practicality as a normal signed integer with a sentinel value, but the same programming ergonomics as an expensive high level type.
- lifthrasiir 3y ago> People's intuition around the existing float NaNs is not good. I think that, if NaN was defined to be an unconditional trap but can be deferred for efficiency, then it could have worked much better. NaN surprises people because it was exposed in the first place, while it should really have been hidden behind the scene (because the presence of NaN means you are already wrong somewhere, and you are expected to be notified about that fact). In terms of Rust, say, every f32 operation could have returned `Result<f32, FloatError>` (mostly likely to be aliased though) that has the exactly same layout as the current f32. The current split between qNaN and sNaN (among others) is unnecessarily complex with little benefit.
- CSSer 3y agoTo be honest, I feel pretty insecure about bitwise operations. I was really psyched for the primer link, but it 404ed :(
- nayuki 3y agoIt's spelled ones' complement. https://en.wikipedia.org/wiki/Ones%27_complement https://en.wikipedia.org/wiki/Ones%27_complement
- mrdoornbos 3y agoI fixed it. Spell check was no help there, and I didn't see that I was spelling it both ways despite knowing better. Thanks for the catch.
- Narishma 3y agoYou fixed the text but not the images.
- deleted 3y ago[deleted]
- adammarples 3y agoThe important bit The decimal value of 11111011 is -5 Is not really explained? I would have thought this was -123
- RedNifre 3y agoIt's -5 because if you add 5 to it, you get 0: 11111011 + 00000101 -------- (1)00000000 Two's complement is just like those spinning number wheel counters, like the km counter in old cars: If you drove more than 999999 km, it would look like you drove 000000. Now, if you had a funny car where driving backwards would subtract from the km counter, starting at 000000 and driving backwards 1 km would result in 999999, therefor 999999 means -1 (you could say 000000 to 499999 is positive, 500000 to 999999 is negative).
- ughitsaaron 3y agoVery well explained.
- cousin_it 3y agoRephrasing: Let's say x=000110 for example Invert all bits of x, call that number inv(x)=111001 If we add them together, "the gears mesh together" and we get x+inv(x)=111111 Adding 1 to that, let the carry just drop off the left side, we get x+inv(x)+1=000000 So it's natural to take inv(x)+1 as a representation of -x.
- arun-mani-j 3y agoThank you, I wish I saw this an year ago when I was learning 2's complement for digital systems subject. Many articles I read said that 2's complement helps in arithmetic, but I was not able to understand "how". The naive me was like - why do they complement and set a sign bit? We can just use a sign bit right? So if 0010 means +2, then why not represent -2 as 1010. What's the need for the complement part at all?! Then only I realized that we are able to retain x + (-x) = 0 using this 2's complement representation. :)
- thaumasiotes 3y agoHere's a very brief description of two's complement that also happens to be a complete description: Two's complement is ordinary integer arithmetic. There is no difference between two's complement arithmetic and unsigned arithmetic. All calculations are literally identical. Unsigned integer arithmetic is modular arithmetic with equivalence classes having labels between 0 (inclusive) and 2^n (exclusive), while two's complement arithmetic is the same thing, but the equivalence classes have labels between negative 2^{n-1} (inclusive) and 2^{n-1} (exclusive). Here's a table of three-bit values with "unsigned" and "two's complement" labels: 100 4 -4 101 5 -3 110 6 -2 111 7 -1 000 0 0 001 1 1 010 2 2 011 3 3 100 4 -4 101 5 -3 110 6 -2 111 7 -1 Note that when you're working in mod 8, 5 and -3 are the same value, so this is nothing but a labeling difference.
- laszlokorte 3y agoYou might find it useful to play around with this: https://thesis.laszlokorte.de/demo/number-circle.html https://thesis.laszlokorte.de/demo/number-circle.html And notice how „just using the sign bit“ and the 2compl are just different ways to align interepretations with bit patterns. But using the 2compl is the alignment that does not require special cases for handling the negative numbers as opposed to the positive numbers.
- ughitsaaron 3y agoSo does this mean that whenever one is working in 8 bits that it’s taken for granted that the upper bounds represent negative integers? Or does it rather depend on the context?
- fluoridation 3y agoI'm not sure what you're asking. If you're working with n-bit integers and you interpret the value as unsigned, then all values >= 2^(n-1) (i.e. the upper half of the range) represent negative two's complement values. Or put another way, bit n-1 is on iff the value is negative.
- makeworld 3y agoIt depends on context. Sometimes the bits or bytes represent a signed number, sometimes an unsigned number, sometimes a float, sometimes a string, etc. It's all up to how you choose to interpret it.
- wkjagt 3y agoFor me two’s complement started making sense when I realized that for example when you subtract 1 from 0, regardless of using signed or unsigned, you get 11111111 (assuming 8 bits). Using two’s complement, we just interpret it as -1, but the binary arithmetic is the same.
- wkjagt 3y agoThe author briefly talks about the HP-16C. I’ve been looking at buying one for a while, but never managed to convince myself I need it enough to spend a couple of hundreds of dollars on a used calculator. I do a lot of 6502 assembly, so it would certainly be nice to have. I did, ironically, spend about the same amount in total on various other calculators that I thought might do the same job. I am now using a Casio CM-100, which is actually quite nice. I see the author has a 16C clone. I got a different clone of the 16C, a PX-16C, which is an impressive project, but ended up not enjoying using it.