[JW] representations of signed integer and unsigned integer
Jun Woong
Questions about relation between the representation of signed integral
types and of unsigned integral types.
[1]
N869 says:
"The range of nonnegative values of a signed integer type is a
subrange of the corresponding unsigned integer type, and the
representation of the same value in each type is the same."
But the Standard allows more than one representations for one value,
thus should I interpret "the representation" above as "the value
representation"?
[2]
The citation above,
"Each bit that is a value bit shall have the same value as the same
bit in the object representation of the corresponding unsigned type
(if there are M value bits in the signed type and N in the unsigned
type, then M <= N)." [called "citation A" hereafter]
and
"A valid (non-trap) object representation of a signed integer type
where the sign bit is zero is a valid object representation of the
corresponding unsigned type, and shall represent the same value."
Is there more wording to describe the relation between the signed
integral types' representation and the unsigned integral types' other
than the above? If yes, what are they?
I think that the citation A impiles:
1) all value bits of an unsigned integral type (which have padding)
whose orders are equal to or less than value bits of the
corresponding signed integral type, must have the same positions
as corresponding value bits of the signed type.
Therefore, (In this example, one character means one bit.
s, V and p indicate sign bit, value bit and padding bit respectively.
The leftmost bit is MSB, and the rightmost bit LSB)
signed: pVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVs
unsigned: pVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVp is conforming.
signed: psVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
unsigned: VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVp is not conforming.
signed: sVpVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV
unsigned: VVpVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV is conforming.
signed: pVsVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV
unsigned: pVVVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV is not conforming.
Right?
If there is other strange example which need attention (I mean what
is conforming but people are easy to think it not conforming or
vice versa), please let me know it.
2) the value which value bits of a signed type have is interpreted
in the same way as the value which corresponding value bits of the
corresponding unsigned type have is interpreted in, which is called
"pure binary numeration system".
Is there any other thing which the citation A implies?
Thanks in advance..
--
Jun Woong (myco...@hanmail.net)
Dept. of Physics, Univ. of Seoul
--
Jun Woong (myco...@hanmail.net)
Dept. of Physics, Univ. of Seoul
Douglas A. Gwyn
ones-complement; or sign-magnitude; the sign bit must be at
the high-order end. There can be padding bits (except for
unsigned char) that are not included in the value representation;
we permit this because sometimes there have been architectural or
compatibility constraints that need that flexibility, although
such circumstances are seldom encountered these days.
> But the Standard allows more than one representations for one value,
> thus should I interpret "the representation" above as "the value
> representation"?
No! The multiple representation can occur only for -0 vs. +0.
The unsigned representation of 0 matches that for +0, not -0.
You shouldn't have to worry about any of this, because it fits
the natural architecture in almost every case. One possibly
interesting example of padding is:
s............... (signed)
0............... (unsigned)
where s=sign, .=variable(1_or_0), 0=must_be_zero. This can
arise when the native arithmetic supports only signed operations.
Another example of padding occurs on the same machine when there
is no native support for doubleword (long) operations:
s............... 0............... (signed long)
0............... 0............... (unsigned long)
The "internal" sign bit must be left out of the value representation
because it is too hard and slow to use it as a value bit in the
multiple-word arithmetic algorithms.
James Kuyper Jr.
...
> "Each bit that is a value bit shall have the same value as the same
> bit in the object representation of the corresponding unsigned type
> (if there are M value bits in the signed type and N in the unsigned
> type, then M <= N)." [called "citation A" hereafter]
>
> and
>
> "A valid (non-trap) object representation of a signed integer type
> where the sign bit is zero is a valid object representation of the
> corresponding unsigned type, and shall represent the same value."
>
> Is there more wording to describe the relation between the signed
> integral types' representation and the unsigned integral types' other
> than the above? If yes, what are they?
Yes - Section 6.2.6.2p2 (your "citation A") continues with some very
important material that you dropped:
"... If the sign bit is zero, it shall not affect the resulting value.
If the sign bit is one, the value shall be modified in one of the
following ways:
— the corresponding value with sign bit 0 is negated (sign and
magnitude);
— the sign bit has the value -(2 N )(two’s complement);
— the sign bit has the value -(2 N - 1) (one’s complement).
Which of these applies is implementation-defined, as is whether the
value with sign bit 1
and all value bits zero (for the first two), or with sign bit and all
value bits 1 (for one’s
complement), is a trap representation or a normal value. In the case of
sign and
magnitude and one’s complement, if this representation is a normal value
it is called a
negative zero."
> I think that the citation A impiles:
>
> 1) all value bits of an unsigned integral type (which have padding)
> whose orders are equal to or less than value bits of the
> corresponding signed integral type, must have the same positions
> as corresponding value bits of the signed type.
Correct. I've inserted spaces below in your examples, to make the bits
line up with each other.
> Therefore, (In this example, one character means one bit.
> s, V and p indicate sign bit, value bit and padding bit respectively.
> The leftmost bit is MSB, and the rightmost bit LSB)
>
> signed: pVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVs
> unsigned: pVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVp is conforming.
Correct.
> signed: psVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
> unsigned: VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVp is not conforming.
Correct.
> signed: sVpVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV
> unsigned: VVpVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV is conforming.
Correct.
> signed: pVsVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV
> unsigned: pVVVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV is not conforming.
Correct.
> If there is other strange example which need attention (I mean what
> is conforming but people are easy to think it not conforming or
> vice versa), please let me know it.
Don't forget:
signed: pVsVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV
unsigned: VVpVpVVVVVVVVVVVVVVVVVVVVVVVVVVVV is conforming.
> 2) the value which value bits of a signed type have is interpreted
> in the same way as the value which corresponding value bits of the
> corresponding unsigned type have is interpreted in, which is called
> "pure binary numeration system".
> Is there any other thing which the citation A implies?
Yes; that signed types can have trap representations.
Jun Woong
>
>The value representation must be one of: twos-complement;
>ones-complement; or sign-magnitude; the sign bit must be at
>the high-order end.
Does the Standard require that?
I can find nothing for it to say about that. To the best of my
knowledge, the position of the sign bit is arbitrary, even if most
architectures place it at the high-order.
>There can be padding bits (except for
>unsigned char) that are not included in the value representation;
>we permit this because sometimes there have been architectural or
>compatibility constraints that need that flexibility, although
>such circumstances are seldom encountered these days.
>
>> But the Standard allows more than one representations for one value,
>> thus should I interpret "the representation" above as "the value
>> representation"?
>
>No! The multiple representation can occur only for -0 vs. +0.
You misinterpreted my point.
11100000...000000011 [representation A]
10100000...000000011 [representation B]
In these examples, the first three bits are padding, and the remainder
are value bits. This type does not have any trap representation.
Thus, representation A and B all represent number 3, but they have
different representations. This can be understood as this type has
eight (2^3) multiple representation which all represent same value.
>The unsigned representation of 0 matches that for +0, not -0.
>
>You shouldn't have to worry about any of this, because it fits
>the natural architecture in almost every case. One possibly
>interesting example of padding is:
> s............... (signed)
> 0............... (unsigned)
>where s=sign, .=variable(1_or_0), 0=must_be_zero. This can
>arise when the native arithmetic supports only signed operations.
>Another example of padding occurs on the same machine when there
>is no native support for doubleword (long) operations:
> s............... 0............... (signed long)
> 0............... 0............... (unsigned long)
>The "internal" sign bit must be left out of the value representation
>because it is too hard and slow to use it as a value bit in the
>multiple-word arithmetic algorithms.
Yes, this is interesting example. Thanks.
James Kuyper Jr.
>
> In article <3ADD3FFA...@null.net>, Douglas A. Gwyn says...
> >
> >The value representation must be one of: twos-complement;
> >ones-complement; or sign-magnitude; the sign bit must be at
> >the high-order end.
>
> Does the Standard require that?
Yes. Almost. See 6.2.6.2p2.
> I can find nothing for it to say about that. To the best of my
> knowledge, the position of the sign bit is arbitrary, even if most
> architectures place it at the high-order.
The standard doesn't specify the physical location of the sign bit, but
it does require that any positive number that can be represented by the
signed type have the same representation in both types. Therefore, the
sign bit in the signed representation has to correspond either to a
padding bit, or to one of the bits in the signed representation that has
a value too large to be stored in the signed type.
Jun Woong
>Jun Woong wrote:
>>
>> In article <3ADD3FFA...@null.net>, Douglas A. Gwyn says...
>> >
>> >The value representation must be one of: twos-complement;
>> >ones-complement; or sign-magnitude; the sign bit must be at
>> >the high-order end.
>>
>> Does the Standard require that?
>
>Yes. Almost. See 6.2.6.2p2.
Is your "Yes" to "must bo one of: twos- ... or sign-magntude;"
or to "the sign bit must be at the high-order end"? (I surmise the
former - My question asked if the Standard requires that the sign bit
must be at the high-order end)
And, what do you mean with "almost"?
Is it for possibility that an implementation places the sign bit at
arbitrary location other than the high-order end, that the negative
zero is trap representation in one's complement and sign-maginitude,
and that the max negative number is trap representation in two's
complement?
James Kuyper Jr.
>
> In article <3AE21C7F...@wizard.net>, James Kuyper Jr. says...
> >Jun Woong wrote:
> >>
> >> In article <3ADD3FFA...@null.net>, Douglas A. Gwyn says...
> >> >
> >> >The value representation must be one of: twos-complement;
> >> >ones-complement; or sign-magnitude; the sign bit must be at
> >> >the high-order end.
> >>
> >> Does the Standard require that?
> >
> >Yes. Almost. See 6.2.6.2p2.
>
> Is your "Yes" to "must bo one of: twos- ... or sign-magntude;"
> or to "the sign bit must be at the high-order end"? (I surmise the
> former - My question asked if the Standard requires that the sign bit
> must be at the high-order end)
>
> And, what do you mean with "almost"?
That's what I tried to explain in the rest of the message. I believe
that "one's complement", "two's complement", and "sign-magnitude" all
carry the implication that the sign bit is at a particular end of the
number, and that there are no padding bits. The standard allows padding
bits, and doesn't specify where the sign bit is, beyond prohibiting it
from being the same as any bit which, in the unsigned type, represents a
value that can be stored in the signed type.
> Is it for possibility that an implementation places the sign bit at
> arbitrary location other than the high-order end, ...
No - any bit that is used by the unsigned type to represent a value that
can be stored in the signed type is off-limits; it must be used to store
that same value in the signed type.
> ... that the negative
> zero is trap representation in one's complement and sign-maginitude,
The standard explicitly says in 6.2.6.2p2: "Which of these applies is
implementation-defined, as is whether the value with sign bit 1 and all
value bits zero (for the first two), or with sign bit and all value bits
1 (for one’s complement), is a trap representation or a normal value. In
the case of sign and magnitude and one’s complement, if this
representation is a normal value it is called a negative zero."
Keep in mind that the standard guarantees that it's hard to accidentally
make a negative 0; "-0" isn't sufficient. See 6.2.6.2p3 for details.
> and that the max negative number is trap representation in two's
> complement?
I believe that's legal, except of course, for the int*_t types, which
are required to use 2's complement, and prohibited from having padding
bits; the only place it's legal to put the sign bit for those types is
the same place as the corresponding unsigned type's high order bit.
Douglas A. Gwyn
> ... "one's complement", "two's complement", and "sign-magnitude" all
> carry the implication that the sign bit is at a particular end of the
> number, and that there are no padding bits.
Presence or absence of padding bits is not part of those concepts.
The intent was certainly that the sign bit be at the "high" end of
the representation, as witnessed by specs for the shift operators.
James Kuyper Jr.
>
> "James Kuyper Jr." wrote:
> > ... "one's complement", "two's complement", and "sign-magnitude" all
> > carry the implication that the sign bit is at a particular end of the
> > number, and that there are no padding bits.
>
> Presence or absence of padding bits is not part of those concepts.
I think the absence of padding is assumed, at least as a matter of
conventional use. I agree, the standard does not make any such
assumptions.
> The intent was certainly that the sign bit be at the "high" end of
> the representation, as witnessed by specs for the shift operators.
What aspect of those specs implies that? A left shift on a negative
value, or on a positive value that would push a bit into the sign bit,
both necessarily allow undefined behavior. For a right shift on a
negative value the resulting value is implementation-defined.
The sign bit can't be affected by shifting of any positive value that
doesn't have it's highest value bit set. So in that sense, the sign bit
is the highest bit of the signed representation. Furthermore, the lower
bits must share the same locations as the bits with the same value in
the unsigned representation. However, that doesn't mean it has to
correspond to the high end of the corresponding unsigned type:
1. The sign bit doesn't have to correspond to any of the value bits in
the unsigned representation. If it corresponds to a padding bit, it
could be anywhere. Of course, this requires a padding bit in the signed
type, there can't be more value bits in the signed type than the
unsigned one.
int: pbbbbbbbbbbbbbbbs
unsigned: bbbbbbbbbbbbbbbbp
msb lsb
Shifts of signed values are implemented to treat the sign bit as if it
were in the position of the padding bit. That would expensive and
pointless, but I believe it would be legal.
2. There can be two or more value bits in the unsigned type that
represent values too large to fit in the signed type. Even if there are
no padding bits in the unsigned type, the sign bit doesn't have to be
stored in the highest such bit. Of course, whichever higher bit is not
used, must be a padding bit in the signed type:
int: psbbbbbbbbbbbbbbb
unsigned: bbbbbbbbbbbbbbbbb
What requirements would be violated by either of those two
implementations?
Jun Woong
I think that he meant to say that placing the sign bit at the location
other than the high-order bit is too expensive to perform arithmetic
operations like bitwise shift efficiently, so most implementations
place it at the high-order bit. And I know that the Committee have
had the high-order sign bit in their mind during writing the Standard
though they did not require it in the Standard for some reason.
[...]
James Kuyper Jr.
...
> doesn't have it's highest value bit set. So in that sense, the sign bit
Correction: replace "shifting" with "a 1-bit shift".
Jun Woong
> ... Of course, this requires a padding bit in the signed
>type, there can't be more value bits in the signed type than the
>unsigned one.
>
> int: pbbbbbbbbbbbbbbbs
> unsigned: bbbbbbbbbbbbbbbbp
> msb lsb
>
int: bbbbbbbbbbbbbbbbs
unsigned: bbbbbbbbbbbbbbbbp
msb lsb
Isn't this conforming?
6.2.5p9:
"The range of nonnegative values of a signed integer type is a
subrange of the corresponding unsigned integer type, ..."
6.2.6.2p2:
"(if there are M value bits in the signed type and N in the unsigned
type, then M <= N)."
James Kuyper Jr.
>
> In article <3AE2F0A7...@wizard.net>, James Kuyper Jr. says...
> > ... Of course, this requires a padding bit in the signed
> >type, there can't be more value bits in the signed type than the
> >unsigned one.
> >
> > int: pbbbbbbbbbbbbbbbs
> > unsigned: bbbbbbbbbbbbbbbbp
> > msb lsb
> >
>
> int: bbbbbbbbbbbbbbbbs
> unsigned: bbbbbbbbbbbbbbbbp
> msb lsb
>
> Isn't this conforming?
>
> 6.2.5p9:
> "The range of nonnegative values of a signed integer type is a
> subrange of the corresponding unsigned integer type, ..."
>
> 6.2.6.2p2:
> "(if there are M value bits in the signed type and N in the unsigned
> type, then M <= N)."
You're correct; I keep remembering that as M<N. Sorry!
Douglas A. Gwyn
> int: bbbbbbbbbbbbbbbbs
> unsigned: bbbbbbbbbbbbbbbbp
> msb lsb
> Isn't this conforming?
Not in my opinion. The sign bit needs to be at the high end.
Clive D. W. Feather
<myco...@hanmail.net> writes
>N869 says:
>"The range of nonnegative values of a signed integer type is a
>subrange of the corresponding unsigned integer type, and the
>representation of the same value in each type is the same."
>
>But the Standard allows more than one representations for one value,
>thus should I interpret "the representation" above as "the value
>representation"?
No, the object representation.
[...]
The intention behind these rules is that:
signed int si;
unsigned int ui;
// ... place some legitimate value into ui
if (ui <= INT_MAX)
{
memcpy ((void *)&si, (void *)&ui, sizeof int);
assert (si == ui); // No undefined behaviour, always succeeds
}
// ... place some legitimate value into si
if (si >= 0)
{
memcpy ((void *)&ui, (void *)&si, sizeof int);
assert (si == ui); // No undefined behaviour, always succeeds
}
for *all* possible legitimate values of the two types. And similarly for
any other pair of signed/unsigned integer types.
--
Clive D.W. Feather, writing for himself | Home: <cl...@davros.org>
Tel: +44 20 8371 1138 (work) | Web: <http://www.davros.org>
Fax: +44 20 8371 4037 (D-fax) | Work: <cl...@demon.net>
Written on my laptop; please observe the Reply-To address
Clive D. W. Feather
<kuy...@wizard.net> writes
>That's what I tried to explain in the rest of the message. I believe
>that "one's complement", "two's complement", and "sign-magnitude" all
>carry the implication that the sign bit is at a particular end of the
>number, and that there are no padding bits.
Sorry, but that just isn't the case. There is no rule about where the
sign bit fits into the representation, and padding bits are specifically
allowed.
For example, the following implementation is allowed:
signed: sppppvvvvvvvvvvvvv ... vvvv
unsigned: pvvvvvvvvvvvvvvvvv ... vvvv
and so is this:
signed: vvvvvvvvvvvvvvvvvv ... vvvs
unsigned: vvvvvvvvvvvvvvvvvv ... vvvp
In the latter case, << could be implemented naively, though >> would
have to deliberately clear the sign bit if it was previously clear and
set by the shift. AFAICT the other bitwise operators would work just
fine.
James Kuyper
Citation, please?
James Kuyper
>
> In article <3AE2F0A7...@wizard.net>, James Kuyper Jr. says...
> > ... Of course, this requires a padding bit in the signed
> >type, there can't be more value bits in the signed type than the
> >unsigned one.
> >
> > int: pbbbbbbbbbbbbbbbs
> > unsigned: bbbbbbbbbbbbbbbbp
> > msb lsb
> >
>
> int: bbbbbbbbbbbbbbbbs
> unsigned: bbbbbbbbbbbbbbbbp
> msb lsb
>
> Isn't this conforming?
There's one critical issue I just noticed; consider the bit that you and
I have labelled 'lsb' in the our examples. In what sense is it the least
significant bit? The sign bit is arguably the most significant bit in
the signed representation. The standard doesn't say anything about the
physical ordering of the bits, only the logical ordering, the ordering
in terms of how the shift, comparison, and bitwise logical operators
operate on the values.
You can't get around that issue by arguing in terms of what you'd find
by accessing the data byte by byte using unsigned char; the standard
places no requirements on the relative ordering of the bits in integer
types of different ranks. For example, the following would be a legal
implementation:
(bits are numbered using hexadecimal digits):
unsigned: 0345DEFC BA987621
unsigned char[sizeof(unsigned)]: 01234567 01234567
Therefore, that was a bad example. My second example was more relevant,
because all of the bits are value bits of the unsigned type, which
provides an unambiguous logical ordering of those bits (regardless of
what the physical ordering is).
Douglas A. Gwyn
> Sorry, but that just isn't the case. There is no rule about where the
> sign bit fits into the representation, and padding bits are specifically
> allowed.
Padding bits are allowed, subject to certain constraints, but
I believe the intent of the three-way choice for representing
the value apart from padding was to have *only* three ways
apart from the padding. Certainly one's-complement and two's-
complement offer *no* choice about a "sign bit" since they
don't *have* a sign bit. As to signed-magnitude representation,
I think that the specification of the shift operators makes it
clear that the sign bit has to be at the "left" end.
James Kuyper
>
> <kuy...@wizard.net> writes
> >That's what I tried to explain in the rest of the message. I believe
> >that "one's complement", "two's complement", and "sign-magnitude" all
> >carry the implication that the sign bit is at a particular end of the
> >number, and that there are no padding bits.
>
> Sorry, but that just isn't the case. There is no rule about where the
> sign bit fits into the representation, and padding bits are specifically
> allowed.
I agree that the standard specifically allows these things; what I was
trying to say is that conventional usage is far less lenient than the
standard in this regard. I could be mistaken; "conventional usage" is a
hard thing to pin down.
James Kuyper Jr.
>
> "Clive D. W. Feather" wrote:
> > Sorry, but that just isn't the case. There is no rule about where the
> > sign bit fits into the representation, and padding bits are specifically
> > allowed.
>
> Padding bits are allowed, subject to certain constraints, but
> I believe the intent of the three-way choice for representing
> the value apart from padding was to have *only* three ways
> apart from the padding. Certainly one's-complement and two's-
> complement offer *no* choice about a "sign bit" since they
> don't *have* a sign bit. As to signed-magnitude representation,
The standard is pretty clear about requiring sign bits for all three
types. See 6.2.6.2p2:
" If the sign bit is one, the value shall be modified in one of the
following ways:
— the corresponding value with sign bit 0 is negated (_sign and
magnitude_);
— the sign bit has the value -(2 N )(_two’s complement_);
— the sign bit has the value -(2 N - 1) (_one’s complement_)."
Clive D. W. Feather
<gw...@arl.army.mil> writes
Provided that right shift of a signed value greater than zero does not
set the sign bit (trivial to arrange in the code generator), what
requirement does this fail to meet ?
Niklas Matthies
[毽愍
> I think that the specification of the shift operators makes it
> clear that the sign bit has to be at the "left" end.
Could you elaborate on this bit? I don't quite see how you draw this
conclusion.
-- Niklas Matthies
Douglas A. Gwyn
> > ... Certainly one's-complement and two's-
> > complement offer *no* choice about a "sign bit" since they
> > don't *have* a sign bit.
> The standard is pretty clear about requiring sign bits ...
You missed my point. One's-complement and two's-complement
allow *no latitude* in placement of what the C standard
refers to as their "sign bit", because there is *not* a
separate entity acting as a sign bit -- the whole value is
involved in the complementation. For these representations,
what the C standard refers to as their "sign bit" *must*
be at the high-order end; it's forced by the definition of
these terms.
James Kuyper
Yes, it is the high-order end in terms of any operations that can be
performed on it using signed arithmetic. For instance, the sign bit of a
positive number can only be affected by a 1 bit shifts if that number
has it's highest value bit set. However, the sign bit needn't correspond
to the highest value bit of the corresponding unsigned type - it can
correspond to a bit with a lower value, as long as that value is too
high to be represented in the signed integer type. It can also be stored
in the same location as a padding bit in the unsigned representation,
and the physical (as opposed to logical) location of that bit would then
be completely arbitrary.
Clive D. W. Feather
<gw...@arl.army.mil> writes
>You missed my point. One's-complement and two's-complement
>allow *no latitude* in placement of what the C standard
>refers to as their "sign bit", because there is *not* a
>separate entity acting as a sign bit -- the whole value is
>involved in the complementation. For these representations,
>what the C standard refers to as their "sign bit" *must*
>be at the high-order end; it's forced by the definition of
>these terms.
No it isn't.
If x << 1 is implemented by shifting the sign bit into the least
significant bit, and x >> 1 shifts in a zero and retains the sign bit
unchanged, what is not conforming ? That has the sign bit at the
low-order end.
Douglas A. Gwyn
> <gw...@arl.army.mil> writes
> >You missed my point. One's-complement and two's-complement
> >allow *no latitude* in placement of what the C standard
> >refers to as their "sign bit", because there is *not* a
> >separate entity acting as a sign bit -- the whole value is
> >involved in the complementation. For these representations,
> >what the C standard refers to as their "sign bit" *must*
> >be at the high-order end; it's forced by the definition of
> >these terms.
> No it isn't.
> If x << 1 is implemented by shifting the sign bit into the least
> significant bit, and x >> 1 shifts in a zero and retains the sign bit
> unchanged, what is not conforming ? That has the sign bit at the
> low-order end.
Please re-read what I said. It has nothing to do with shifting
(that is a separate argument pertinent to sign-magnitude only).
It is the very definition of ones-complement or twos-complement
that determines the meaning of bits in those representations,
and there is no special bit designating the sign in those
representations; rather, there is a special interpretation
for a certain range of numerical values. One can tell whether
or not the special interpretation must be used by a simple bit
test using what the C standard has called the "sign bit", but
having determined that, the *whole* value ("sign" bit included)
is subject to complementation to produce the numerical result.
Jun Woong
[...]
>
>and so is this:
>
> signed: vvvvvvvvvvvvvvvvvv ... vvvs
> unsigned: vvvvvvvvvvvvvvvvvv ... vvvp
>
>In the latter case, << could be implemented naively,
Of course, with some treatment in the case where the padding bit is
set in unsigned representation.
Jun Woong
>>thus should I interpret "the representation" above as "the value
>>representation"?
>
>No, the object representation.
>
>[...]
>
>The intention behind these rules is that:
>
> signed int si;
> unsigned int ui;
> // ... place some legitimate value into ui
> if (ui <= INT_MAX)
> {
> memcpy ((void *)&si, (void *)&ui, sizeof int);
> assert (si == ui); // No undefined behaviour, always succeeds
> }
> // ... place some legitimate value into si
> if (si >= 0)
> {
> memcpy ((void *)&ui, (void *)&si, sizeof int);
> assert (si == ui); // No undefined behaviour, always succeeds
> }
>
>for *all* possible legitimate values of the two types. And similarly for
>any other pair of signed/unsigned integer types.
>
But,
signed int si = 4;
unsigned int ui = si; // or unsigned int ui = 4;
int result = memcmp((void *)&si, (void *)&ui, sizeof(int));
the value of "result" can be other than 0.
For any pair of signed/unsigned integer types, provided that the value
is in the legitimate range, the same object representation must
represent the same value as you said above. But the same (legitimate)
value need not have the same object representation. What I meant to
say is this.
The current wording of the Standard, "..., and the representation of
the same value in each type is the same" can be understood as to mean
that the same (legitimate) value must have the same object
representation if the term "representation" in that citation means
"object representation."
Clive D. W. Feather
<myco...@hanmail.net> writes
>But,
>
>signed int si = 4;
>unsigned int ui = si; // or unsigned int ui = 4;
>int result = memcmp((void *)&si, (void *)&ui, sizeof(int));
>
>the value of "result" can be other than 0.
Correct.
>For any pair of signed/unsigned integer types, provided that the value
>is in the legitimate range, the same object representation must
>represent the same value as you said above. But the same (legitimate)
>value need not have the same object representation.
Also correct.
>The current wording of the Standard, "..., and the representation of
>the same value in each type is the same" can be understood as to mean
>that the same (legitimate) value must have the same object
>representation if the term "representation" in that citation means
>"object representation."
Must have *a* same object representation.
In fact, that wording is overly simplistic, and 6.2.6.2 better explains
the situation.
David Thompson
> You missed my point. One's-complement and two's-complement
> allow *no latitude* in placement of what the C standard
> refers to as their "sign bit", because there is *not* a
> separate entity acting as a sign bit -- the whole value is
I have to differ. 1sC propagates carry from the top magnitude bit
to the sign bit and from the sign bit to the bottom magnitude bit;
I see no inherent reason the sign bit must be to the left, although
it is arguably more natural and there is the practical advantage
that it can be (re)used as an additional unsigned magnitude bit.
This is even more beneficial for 2sC where identical logic,
including carry, can be shared with unsigned.
But I don't think it is required by the definition.
--
- David.Thompson 1 now at worldnet.att.net
Douglas A. Gwyn
> I have to differ. 1sC propagates carry from the top magnitude bit
NO, it doesn't. The top magnitude bit *is* what you're calling
the sign bit. Should I send you the schematics for the 1784 ALU?
Keith Thompson
So there's no such thing as a "sign bit" in 1's-complement and
2's-complement?
In the sense of "a bit that negates the value when you flip it", there
isn't. In the sense of "a bit that tells you whether the value is
negative", there is. I'm not convinced that the latter is an
unreasonable definition. It's also the definition used in the C
standard, and it seems as reasonable as the C standard's somewhat
unusual definition of "byte".
And I know that you know that 1784 ALU schematics are off-topic. 8-)}
--
Keith Thompson (The_Other_Keith) k...@cts.com <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Cxiuj via bazo apartenas ni.
Douglas A. Gwyn
> So there's no such thing as a "sign bit" in 1's-complement and
> 2's-complement?
> In the sense of "a bit that negates the value when you flip it", there
> isn't. In the sense of "a bit that tells you whether the value is
> negative", there is. I'm not convinced that the latter is an
> unreasonable definition. It's also the definition used in the C
> standard, and it seems as reasonable as the C standard's somewhat
> unusual definition of "byte".
There is also an "even" bit (which for a ones-complement
implementation has to be interpreted in conjunction with the
"sign" bit when the representation is interpreted as a signed
type), but I don't think you'd argue that the "even" bit can
be other than at the least-significant end of the word for
ones-complement,.twos-complement, or sign-magnitude
representation. For the first two forms, similarly the
"sign" bit is part of the successive-powers-of-two radix
scheme used in the representation, so it has to be at the
most-significant end of the word. For sign-magnitude, the
sign bit could be anywhere in the word, but of course is
usually at the most-significant end.
> And I know that you know that 1784 ALU schematics are off-topic. 8-)}
Not when it comes to understanding what the terminology meant to
the actual designers and users of ones-complement hardware.
James Kuyper
>
> Keith Thompson wrote:
> > So there's no such thing as a "sign bit" in 1's-complement and
> > 2's-complement?
> > In the sense of "a bit that negates the value when you flip it", there
> > isn't. In the sense of "a bit that tells you whether the value is
> > negative", there is. I'm not convinced that the latter is an
> > unreasonable definition. It's also the definition used in the C
> > standard, and it seems as reasonable as the C standard's somewhat
> > unusual definition of "byte".
>
> There is also an "even" bit (which for a ones-complement
> implementation has to be interpreted in conjunction with the
> "sign" bit when the representation is interpreted as a signed
> type), but I don't think you'd argue that the "even" bit can
> be other than at the least-significant end of the word for
> ones-complement,.twos-complement, or sign-magnitude
The "even" bit is, by definition, the least-significant bit of a number,
just as the sign bit is, in a somewhat different sense, the most
significant bit, but there's nothing in the standard that specifies the
location of either one, except in terms of what the shift operators do
to it. In that sense, those bits are indeed at opposite ends of the
representation. However, that definition cares nothing about "words",
and in particular it doesn't care where either physical end of a word
is.
Douglas A. Gwyn
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
"Douglas A. Gwyn" wrote:
> ... aliaing ...
That was supposed to be aliasing. My hands are numb due to
the office being way too cold.
Douglas A. Gwyn
> ... In that sense, those bits are indeed at opposite ends of the
> representation. However, that definition cares nothing about "words",
> and in particular it doesn't care where either physical end of a word
> is.
All along, I have taken for granted that we're talking about
software-testable properties, e.g. by aliaing to the unsigned
variety and performing bit tests. The *physical* bits are
just flip-flop states scattered across several ICs, typically.
From there onward, we're dealing with various grouping and
numbering conventions.
Jun Woong
> Douglas A. Gwyn <gw...@arl.army.mil> wrote :
> ...
> > You missed my point. One's-complement and two's-complement
> > allow *no latitude* in placement of what the C standard
> > refers to as their "sign bit", because there is *not* a
> > separate entity acting as a sign bit -- the whole value is
> > involved in the complementation. ...
>
> I have to differ. 1sC propagates carry from the top magnitude bit
> to the sign bit and from the sign bit to the bottom magnitude bit;
Could anyone show me more detailed example about what he said?
Thanks in advance...
David Thompson
...
> Could anyone show me more detailed example about what he said?
>
>>(OE didn't want to quote your text properly, sorry)
It's hard for me to understand the following in your posting:
"1sC propagates carry from the top magnitude bit to the sign
bit and from the sign bit to the bottom magnitude bit; I see
no inherent reason the sign bit must be to the left ..."
Could you show me concrete example about that (1sC's carry
propagating)?
<<
1 1 1 0 0 -3
0 0 1 0 1 +5
1 1 1 0 1 1
0 0 0 1 0 +2
1 1 1 0 0 -3
1 1 1 0 1 -2
1 1 1 0 1 1
1 1 0 1 0 -5
Notice that the magnitude sum must be incremented iff
adding two negative numbers (leaving sign bit set=negative)
or a positive number whose absolute value exceeds that of the
other, negative one (with the sign bit clear=positive).
With straightforward ripple-cary logic, this is easily done
by treating carry-out of the high magnitude bit as carry-in
to the sign bit, which is binary-added just like data, with
its carry-out treated as carry-in to the low magnitude bit
(which has no carry-in in unsigned or 2sC).
I think lookahead carry is hard if not impossible in 1sC,
probably another reason 2sC is more popular,
although carry-save should work.
Douglas A. Gwyn
> I think lookahead carry is hard if not impossible in 1sC,
> probably another reason 2sC is more popular,
> although carry-save should work.
The CDC 1700 used a ones-complement subtractive adder and
did not require extra clock cycles for the carries, due to
the stability of the basic operation (no indeterminate
states, see one of Lamport's papers about this issue).
Note that your model for addition does not carry over to
other operations such as multiplication and division.
The *definition* of ones-complement representation is that
each bit represents an additive contribution of a successive
power of 2 (positional notation, binary numeration system);
this includes the high-order bit, which is relevant when
representing *unsigned* values. Negative values are
represented as the bit-by-bit complement of the already-
specified representation of the absolute value (magnitude)
of the number, including the high-order bit. Obviously,
half the range of (unsigned) positive values do not have
corresponding negative values, just as with twos-complement.
The definition of twos-complement is similar, except instead
of a bitwise logical complement, negation consists of
(unsigned) subtraction from 2^wordsize, which works only if
the so-called "sign bit" is the high-order bit. Negation
for twos-complement representation is readily implemented as
"perform ones complement then add one".
The different representations each have their own advantages
and disadvantages. CDC sought maximum speed, and decided
that ones-complement would provide that, using then-current
technology.
David Thompson
...
> Note that your model for [1sC] addition does not carry over to
> other operations such as multiplication and division.
>
scaled addition or subtraction depending. You can
(and should?) _optimize_ this with at least carry-save,
but it works. If you do full-to-double-length multiplication
you need to add correction terms for negative operands,
but that's equally true of 2sC. Neither 1sC or 2sC works well
for division, you need to (temporarily) convert to S&M.
Also, in checking RFC1936 for another reason I see
that lookahead-carry does work for 1sC. It still seems
to me more difficult, but that's somewhat subjective.
> The *definition* of ones-complement representation is that
> each bit represents an additive contribution of a successive
> power of 2 (positional notation, binary numeration system);
> this includes the high-order bit, which is relevant when
> representing *unsigned* values. Negative values are
> represented as the bit-by-bit complement ...
That's where we disagree. To me, 1sC or 2sC or S&M
is a representation of signed numbers only, symmetric
about zero except for the extra -2^Nmag value in 2sC;
any unsigned representation is separate even if related.
Yes, the positional binary magnitude bits are complemented
(and the sign set) for negative; this is equivalent to the
mathematical definition (2^Nmag -1) -pos . In no signed
scheme does the sign bit have the same weight as any
possible magnitude bit; 2sC comes closest at - 2^Nmag .
I agree and said that if you want unsigned in the same
ALU with 1sC, as you usually do, it is best to use the
same (leftmost) bit for 1sC-sign and uns-top-magnitude
(even more so for 2sC) and designers do; even without this
it may be convenient to put the sign at the left because
users (except maybe accountants) expect it. Especially
on systems where you (may) want to implement C.
But it is not inherent in the concept, and shouldn't be required
by the _definition_ of 1sC, or 2sC, unless 2382 (which I don't have)
disagrees. My claim was that it would be permitted and work
to implement 1sC with the sign at the right, not that anyone
has or should. This is a fairly fine distinction, as usual here.
For comparison, on serial (async, low-bit-first *) comms links
using parity, the parity bit is sometimes readable as the
next-higher data bit (usually if Ndata < CHAR_BIT) but
isn't really a data bit -- though when _emulating_ parity
it is data to the part of the code doing the emulation.
(* There was an X3.n whose entire substantive content
was "low-bit-first"; I don't recall if it actually limited itself
to async, as at the time there were no real synchronous
serial comms links, although there were plenty of serial
synchronous storage devices/interfaces.)
> The definition of twos-complement is similar, except instead
> of a bitwise logical complement, negation consists of
> (unsigned) subtraction from 2^wordsize, which works only if
> the so-called "sign bit" is the high-order bit. Negation
> for twos-complement representation is readily implemented as
> "perform ones complement then add one".
>
It works if you subtract the magnitude bits (only) from
a hidden 1 at the left -- which need not be the sign bit.
Other comments parallel above. Agree as to implementation;
I always liked the way the PDP-8 used two micro-ops for this.
(Though not particularly the "composite" acronym CIA <G>.)
Douglas A. Gwyn
The issue was whether the so-called "sign bit" has to
be "adjacent" to the most-significant bit (ignoring
padding), which matters for shifting etc. I argued
that for 1s- and 2s-complement that was part of the
definition of the format, and David disputes that.
My (hopefully) final attempt at supporting my position
is to direct your attention to the standard textbook
presentations of 1s- and 2s-complement, which
traditionally start out using the decimal system with
9s-complement. They invariably (so far as I have yet
seen) use the "sign digit" in such a way that it is
necessarily at the high-order end of the value digits.
(Conceptually, not physically.)
David Thompson
_after JW leaves it_ is something of a wonder.
This may fall in the AnnIrrepRes area of "[things]
which cannot, or should not, be reproduced". <G>
[ severely but I think fairly abbreviated ]
> The issue was whether the so-called "sign bit" has to
> be "adjacent" to the most-significant bit (ignoring
> padding), ... standard textbook
> presentations of 1s- and 2s-complement, ...
> use the "sign digit" in such a way that it is
> necessarily at the high-order end of the value digits.
> (Conceptually, not physically.)
I agree the sign is, with no exception I know of,
_presented_ and thought of to the left of the msb,
and AFAIK in practice always stored there.
(I didn't initially detail this because I consider it
implicit that I agree with everything substantive
I don't dispute; probably that didn't help matters.)
What I object(ed) to is rejecting anything else
as _impossible_. If you can accept such as
a theoretical possibility, I'm happy to waive
any practical importance or application for it.
HTH.
Jun Woong
I think the problem is quite simple. The standard uses the term "two's
complement" and "one's complement" *) (6.2.6.2p2) without defining
them if 2382 dose not define. Does 2382 define them?
(The following discussion assumes that 2382 does not)
Even without the definitions of the terms, the semantic of the sign
bit is already clear enough not to make any confusion on placement of
the sign bit unless we consider the definitions of them which Douglas
Gwyn referred to.
I think, the C standard itself does not require a conforming
implementation to locate the sign bit on the top-magnitude bit of its
corresponding unsigned type. Even the semantic of the bitwise shift
opertors do not preclude it. For example, if an integer type has the
following representation
vvv...vvvs [v: value bit, s: sign bit]
and the operators << and >> are implemented as usual and >> retains
the copy of the sign bit, then the implementation can be still
conforming.
If the intent of the C standard about placement of the sign bit is
that it must be at MSB, it need to have more restriction about it. But
in the present state of affairs, the sign bit can be at any magnitude
bit (provided that other things which the standard requires are
conforming).
*) Is "1's complement" a correct term? I know that "1s' complement" is
a correct one. To convert to "2's complement", we subtract the
value from some power of the single 2, however to "1s' complement",
we subtract the value from many 1s.
--
Jun Woong (myco...@hanmail.net)
Dept. of Physics, Univ. of Seoul
Cell: +82 16 467 6247
Web : http://c-expert.uos.ac.kr
Jun Woong
Hmm... if a definition of a term can appear in parentheses, the C
standard defines them in 6.2.6.2p2, thus it does not matter what any
other standards and documents (not for usual English) say about them.
Brian Inglis
wrote:
>*) Is "1's complement" a correct term? I know that "1s' complement" is
> a correct one. To convert to "2's complement", we subtract the
> value from some power of the single 2, however to "1s' complement",
> we subtract the value from many 1s.
[Dodging the apostrophe issue.]
1s complement inverts all bits; 2s complement does a 1s
complement, then increments the result -- clears low order 1 bits
and sets the lowest order 0 bit.
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada
--
Brian....@CSi.com (Brian dot Inglis at SystematicSw dot ab dot ca)
fake address use address above to reply
tos...@aol.com ab...@aol.com ab...@yahoo.com ab...@hotmail.com ab...@msn.com ab...@sprint.com ab...@earthlink.com ab...@cadvision.com ab...@ibsystems.com u...@ftc.gov
spam traps
Jun Woong
>
>On 2 Jul 2001 23:49:10 -0700, myco...@hanmail.net (Jun Woong)
>wrote:
>
>>*) Is "1's complement" a correct term? I know that "1s' complement" is
>> a correct one. To convert to "2's complement", we subtract the
>> value from some power of the single 2, however to "1s' complement",
>> we subtract the value from many 1s.
>
>[Dodging the apostrophe issue.]
>1s complement inverts all bits;
That's subtracting the value from many 1s.
>2s complement does a 1s
>complement, then increments the result -- clears low order 1 bits
>and sets the lowest order 0 bit.
That's substracting the value from some power of the single 2.
The C Standard defines the terms "1's complement" and "2's complement".
It does not borrow their definitions from general terminology. Thus I
can't claim that it's incorrect in that regard. But, I think "1s'
complement" and "2's complement" are correct in general case. (I know
neither whether the Committee recognized this, nor how ISO 2382
defines them)
Douglas A. Gwyn
> The C Standard defines the terms "1's complement" and "2's complement".
Actually it uses the terms; it does not define them.
> It does not borrow their definitions from general terminology. Thus I
> can't claim that it's incorrect in that regard. But, I think "1s'
> complement" and "2's complement" are correct in general case. (I know
> neither whether the Committee recognized this, nor how ISO 2382
> defines them)
"Ones-complement" and "twos-complement" are each spelled in at least
three different ways in common practice, not counting "1" for "one"
and "2" for "two". The C99 document editor either selected the
spelling he preferred, or else he copied the spelling that was
provided to him by whoever generated the text.
It is disingenuous to imply that the spelling raises a question
about what was meant. Everybody who knows the standard terminology
recognizes that these phrases refer to it.
There has been a question about whether the sign bit has to be
adjacent to the high-order bit. I maintain that that is part of
the common meaning of the terms, and was certainly intended.
Clive D. W. Feather
<DAG...@null.net> writes
>> The C Standard defines the terms "1's complement" and "2's complement".
>Actually it uses the terms; it does not define them.
I've just checked the PDF version, which shows them in italics. That
means it's defining them. See also below.
>The C99 document editor either selected the
>spelling he preferred, or else he copied the spelling that was
>provided to him by whoever generated the text.
The latter, I think.
>It is disingenuous to imply that the spelling raises a question
>about what was meant. Everybody who knows the standard terminology
>recognizes that these phrases refer to it.
Wrong. See below.
>There has been a question about whether the sign bit has to be
>adjacent to the high-order bit. I maintain that that is part of
>the common meaning of the terms, and was certainly intended.
Doug, *I* wrote that wording. And I state:
(1) The intent was to define the terms using the explicit rules in
6.2.6.2#2.
(2) The intent was *not* to rely on any other definition of the terms
from "common practice" or ISO 2382-1, since I already had experience in
this are showing that they are defective (see DR 069, IIRC).
(3) Had I meant to require the sign bit (or any bit) to live in a
particular place in the representation, I would have written 6.2.6.2#2
differently.
(4) Note that that paragraph explicitly does not require the sign bit of
signed types to live in the same place as an additional value bit in
unsigned types, whereas it *does* make such a requirement of the
corresponding value bits.
(5) Given that, the only way to determine whether two bits are
"adjacent" is to examine the effects of the shift operators. An
examination of 6.5.7#4 and #5 will show that they very carefully make no
assumptions about the location of the sign bit, other than *allowing* it
to be just to the "left" of the most significant value bit.
Larry Jones
> Jun Woong wrote:
> > The C Standard defines the terms "1's complement" and "2's complement".
>
> Actually it uses the terms; it does not define them.
It defines them in 6.2.6.2p2.
> > It does not borrow their definitions from general terminology. Thus I
> > can't claim that it's incorrect in that regard. But, I think "1s'
> > complement" and "2's complement" are correct in general case. (I know
> > neither whether the Committee recognized this, nor how ISO 2382
> > defines them)
>
> "Ones-complement" and "twos-complement" are each spelled in at least
> three different ways in common practice, not counting "1" for "one"
> and "2" for "two". The C99 document editor either selected the
> spelling he preferred, or else he copied the spelling that was
> provided to him by whoever generated the text.
The current editor has no recollection of making any concious decisions
in this matter. Most likely, the spellings came from the original
author of the text, but I don't recall whether it was given directly to
me or whether I inherited it from the previous editor. Nonetheless,
Knuth's usage agrees with Jun Woong, which is sufficient motivation for
me to note a potential future change (although I haven't decided whether
it's worth including in a future "typos" DR or not).
-Larry Jones
Why is it you always rip your pants on the day everyone has to
demonstrate a math problem at the chalkboard? -- Calvin
Douglas A. Gwyn
> >adjacent to the high-order bit. I maintain that that is part of
> >the common meaning of the terms, and was certainly intended.
But in order for it to enter C99 it had to be approved by WG14,
who may have had a different understanding of what was intended.
We have through the years repeatedly maintained that the intent
of C89's requirement for "binary numeration system" was that,
apart from padding, there be only *three* possibilities for
representation of signed integers: ones'-complement, twos'-
complement, and signed-magnitude, with the conventional meaning
of those terms. The requirement that the representation of
positive values be identical for corresponding signed and
unsigned integer types means that the *only* bit available for
representing the "sign bit" is the one at the high-order end of
the (unsigned) representation.
James Russell Kuyper Jr.
"apart from padding" dismisses most of the issues that have been debated
in this discussion. It's only the possibility of padding that makes this
any kind of issue at all.
Clive D. W. Feather
<DAG...@null.net> writes
>We have through the years repeatedly maintained that the intent
>of C89's requirement for "binary numeration system" was that,
>apart from padding,
That's the key phrase. If there is *no* padding, then of course:
>The requirement that the representation of
>positive values be identical for corresponding signed and
>unsigned integer types means that the *only* bit available for
>representing the "sign bit" is the one at the high-order end of
>the (unsigned) representation.
is correct. However, if there *is* padding, then it isn't.
Consider the following pair of types in a 20 bit word:
signed: PPVV VVVV VVVV VVVV VVSP
unsigned: VVVV VVVV VVVV VVVV VVPP
where P is a padding bit, V a value bit, and S the sign bit. What
requirement does this violate ?