Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two's complement – You beauty

everyogi.in

Post reply on HN
Print view View original

81–90 of 92 posts

Re: Two's complement – You beauty

#81

Post by paulddraper »

jonsen wrote: post #76
paulddraper wrote: post #69

If you're looking for true beauty, look no further than negabinary. ( 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. Maybee conversion to/from character code is easier. Notice the conversion code in the linked article.

> 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 >= 1;    
        }
that's the exact same for a negabinary machine.

Re: Two's complement – You beauty

#82

Post by [deleted] »

paulddraper wrote: post #69

If you're looking for true beauty, look no further than negabinary. ( 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…

[deleted]

Re: Two's complement – You beauty

#83

Post by jonsen »

paulddraper wrote: post #81
jonsen wrote: post #76

Earlier quoted context omitted.

...why 2's-complement won. Maybee conversion to/from character code is easier. Notice the conversion code in the linked article.

> 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 >= 1; } that's the exact same for a negabinary machine.

I meant to/from numbers in text form. Usually decimal.

Re: Two's complement – You beauty

#84

Post by 1010111 »

wahern wrote: post #78
1010111 wrote: post #17

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'); }

This code (`x & m`) promotes x to unsigned, which means you're not actually printing the bit representation of a signed integer. You'd get the wrong bit pattern for a negative number on ones' complement machines, as signed-to-unsigned conversions are well defined in C and obey modulo semantics. So, for example, `-1` would print as `1 ... 111` instead of `1 ... 110`.

Thanks, i was not aware of that. What is a possible fix?

Re: Two's complement – You beauty

#85

Post by Double_Cast »

vog wrote: post #56
gizmo686 wrote: post #22

Earlier quoted context omitted.

I didn't downvote you. However, I am a math person and your post feels wrong for some reason. It isn't wrong, but it feels like it should be; and I am not entirely sure why. CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement. The insight with two's complement is that we can interperet the "upper" half of numbers as negative. As…

> CPUs use modular arithmetic for both signed (two's complement) and unsigned values, so that cannot be the defining feature of twos complement I disgree, because this still fits nicely into modulo arithmetics. Signed versus unsigned just means that we choose a different set of representants for certain operations (such as). For unsigned, we use the smalles non-negative representant. For signed, we use the representa…

"Two's Compliment represents a linear automorphism over a cyclic group" is what I think you're trying to say. russdill & co are hinting that Modular Arithmetics are cyclic groups.

I think for most people, the aha-moment comes when they realize One's Compliment double-counts the zero. In contrast, linearity is simply assumed. Otherwise, why would anyone make a number system out of it?

Re: Two's complement – You beauty

#86

Post by [deleted] »

jonsen wrote: post #83
paulddraper wrote: post #81

Earlier quoted context omitted.

> 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 >= 1; } that's the exact same for a negabinary machine.

I meant to/from numbers in text form. Usually decimal.

[deleted]

Re: Two's complement – You beauty

#87

Post by bsder »

bogomipz wrote: post #59
bsder wrote: post #12

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

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

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

Re: Two's complement – You beauty

#88

Post by gpvos »

brandonbloom wrote: post #79
AstralStorm wrote: post #50

Earlier quoted context omitted.

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.

Just prefix a + or - just like you do for base 10.

So then it would not make much of a difference anymore with what Python does. Which was what they wanted to avoid.

Re: Two's complement – You beauty

#89

Post by Zardoz84 »

throwawayish wrote: post #49
gumby wrote: post #19

Earlier quoted context omitted.

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

There are also other interesting uses for odd word lengths. For example, many UARTs support word lengths from 5 to 9-ish bits (some do more). This is commonly used to implement out of band signalling for protocols running over these, eg. using 9 bit words, where the ninth bit tells whether this is the start of a command frame. More handily even, in most MCUs this is already correctly separated, ie. there is a byte re…

Or using the 9th bit to indicate that the rest of the byte is an address . Some PICs UARTS had an interruption that is triggered when the 9th bit is on.

Re: Two's complement – You beauty

#90

Post by wahern »

1010111 wrote: post #84
wahern wrote: post #78

Earlier quoted context omitted.

This code (`x & m`) promotes x to unsigned, which means you're not actually printing the bit representation of a signed integer. You'd get the wrong bit pattern for a negative number on ones' complement machines, as signed-to-unsigned conversions are well defined in C and obey modulo semantics. So, for example, `-1` would print as `1 ... 111` instead of `1 ... 110`.

Thanks, i was not aware of that. What is a possible fix?

I was going to say that you just need to change m to int and fix the mask derivation to avoid directly or indirectly manipulating or reading the sign bit. And to do that you _only_ need to know the number of value bits. It turned out more complicated than that.

You can't reliably derive the number of value bits from the unsigned type on evil implementations. Using the range limits like INT_MIN and INT_MAX, though, you can deduce the number of value bits. It's useful that the definition of precision and width in 6.2.6.2p6 of C11 effectively precludes, I think, a range which doesn't make full use of the available value bits. Also that the standard effectively only permits ones' complement, two's complement, and sign magnitude. Being able to reliably determine the number of value bits means you could carefully shift a masking bit through the set of value bits.

But confirming with the standard I was reminded that shifts of negative values are undefined. But I think we could use arithmetic to shift the bit. Preferably multiplication because I'm not quite grokking the requirements for signed division, and I _just_ learned that INT_MIN / -1 will cause a floating point exception on x86. Cool!

Also, with this general approach we'd never be able to peek at all the representation bits for the value and sign bits. We wouldn't see the high bit on two's and ones' complement implementations to show our hypothetical skeptic how it changes.

We could inspect all the representation bits by inspecting the int object as an unsigned char. But I don't think we could reliably differentiate the padding bits from the value and sign bits, especially on an evil implementation where the value bits weren't all contiguous or which toggled the padding bits semi-randomly just to screw with us.

Post reply on HN