Velocity Reviews > Unary minus and bitwise complement

# Unary minus and bitwise complement

Noob
Guest
Posts: n/a

 03-19-2013
Hello,

Considering a properly initialized unsigned int variable v,
are -v and ~(v-1) equivalent for any value of v, even on
the DS9k?

(let <-> mean "are equivalent for any value of v")

According to C89 3.3.3.3
~v <-> UINT_MAX - v

Thus
~(v-1) <-> UINT_MAX - (v-1)
~(v-1) <-> UINT_MAX - v + 1
~(v-1) <-> (UINT_MAX + 1) - v

Adding (UINT_MAX + 1) to an unsigned int variable is a NOP,
thus ~(v-1) <-> -v

I think this is true always, I don't think the "usual arithmetic
conversions" come in play in problematic ways?

Regards.

Eric Sosman
Guest
Posts: n/a

 03-19-2013
On 3/19/2013 10:49 AM, Noob wrote:
> Hello,
>
> Considering a properly initialized unsigned int variable v,
> are -v and ~(v-1) equivalent for any value of v, even on
> the DS9k?
>
> (let <-> mean "are equivalent for any value of v")
>
> According to C89 3.3.3.3
> ~v <-> UINT_MAX - v
>
> Thus
> ~(v-1) <-> UINT_MAX - (v-1)
> ~(v-1) <-> UINT_MAX - v + 1
> ~(v-1) <-> (UINT_MAX + 1) - v
>
> Adding (UINT_MAX + 1) to an unsigned int variable is a NOP,
> thus ~(v-1) <-> -v
>
> I think this is true always, I don't think the "usual arithmetic
> conversions" come in play in problematic ways?

True always. (And still true in more recent Standards.)

The usual arithmetic conversions appear in the subexpression
`v-1', where they convert the `int' constant 1 to `unsigned int'
before the subtraction happens. So, no surprises there.

Neither the unary minus nor the complement operator use the
U.A.C., but only the "integral promotions." These "promote" an
`unsigned int' to, er, `unsigned int', so again: no surprises.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d

Bart van Ingen Schenau
Guest
Posts: n/a

 03-19-2013
On Tue, 19 Mar 2013 15:49:42 +0100, Noob wrote:

> Hello,
>
> Considering a properly initialized unsigned int variable v, are -v and
> ~(v-1) equivalent for any value of v, even on the DS9k?

For integers with a conversion-rank equal to or higher than int: Yes.
For other integer types: Not guaranteed.

>
> (let <-> mean "are equivalent for any value of v")
>
> According to C89 3.3.3.3
> ~v <-> UINT_MAX - v
>
> Thus
> ~(v-1) <-> UINT_MAX - (v-1)
> ~(v-1) <-> UINT_MAX - v + 1
> ~(v-1) <-> (UINT_MAX + 1) - v
>
> Adding (UINT_MAX + 1) to an unsigned int variable is a NOP, thus ~(v-1)
> <-> -v
>
> I think this is true always, I don't think the "usual arithmetic
> conversions" come in play in problematic ways?

If v has the type `unsigned char` or `unsigned short` AND if `signed int`
can represent all the values that can be stored in v, then the integer
promotions (part of the usual arithmetic conversions) do cause problems.
In that case, the unary minus and the bitwise complement operators both
operate on a signed type, so your equivalences no longer hold.

>
> Regards.

Bart v Ingen Schenau

James Kuyper
Guest
Posts: n/a

 03-19-2013
On 03/19/2013 10:49 AM, Noob wrote:
> Hello,
>
> Considering a properly initialized unsigned int variable v,
> are -v and ~(v-1) equivalent for any value of v, even on
> the DS9k?
>
> (let <-> mean "are equivalent for any value of v")
>
> According to C89 3.3.3.3

That's 6.5.3.3 in the current standard.

> ~v <-> UINT_MAX - v
>
> Thus
> ~(v-1) <-> UINT_MAX - (v-1)
> ~(v-1) <-> UINT_MAX - v + 1
> ~(v-1) <-> (UINT_MAX + 1) - v
>
> Adding (UINT_MAX + 1) to an unsigned int variable is a NOP,
> thus ~(v-1) <-> -v
>
> I think this is true always, I don't think the "usual arithmetic
> conversions" come in play in problematic ways?

Since v is unsigned int, and 1 has the type int, the usual arithmetic
conversions require that 1 be converted to unsigned int, and then
everything goes through fine.

The tricky case is an unsigned type where TYPE_MAX < INT_MAX, and v==0.
In that case, the unsigned value is converted to int, so the result is
~(-1), which has different results depending upon whether 2's
complement, 1's complement, or sign-magnitude representation is used.
The DS9k, of course, only uses 2's complement representation in it's
floating point implementation.

James Kuyper
Guest
Posts: n/a

 03-19-2013
On 03/19/2013 11:42 AM, Eric Sosman wrote:
> On 3/19/2013 10:49 AM, Noob wrote:
>> Hello,
>>
>> Considering a properly initialized unsigned int variable v,
>> are -v and ~(v-1) equivalent for any value of v, even on
>> the DS9k?
>>
>> (let <-> mean "are equivalent for any value of v")
>>
>> According to C89 3.3.3.3
>> ~v <-> UINT_MAX - v
>>
>> Thus
>> ~(v-1) <-> UINT_MAX - (v-1)
>> ~(v-1) <-> UINT_MAX - v + 1
>> ~(v-1) <-> (UINT_MAX + 1) - v
>>
>> Adding (UINT_MAX + 1) to an unsigned int variable is a NOP,
>> thus ~(v-1) <-> -v
>>
>> I think this is true always, I don't think the "usual arithmetic
>> conversions" come in play in problematic ways?

>
> True always. (And still true in more recent Standards.)
>
> The usual arithmetic conversions appear in the subexpression
> `v-1', where they convert the `int' constant 1 to `unsigned int'
> before the subtraction happens. So, no surprises there.
>
> Neither the unary minus nor the complement operator use the
> U.A.C., but only the "integral promotions." These "promote" an
> `unsigned int' to, er, `unsigned int', so again: no surprises.
>

The U.A.C come into play through the v-1 sub-expression.

Lew Pitcher
Guest
Posts: n/a

 03-19-2013
On Tuesday 19 March 2013 10:49, in comp.lang.c, root@127.0.0.1 wrote:

> Hello,
>
> Considering a properly initialized unsigned int variable v,
> are -v and ~(v-1) equivalent for any value of v, even on
> the DS9k?
>
> (let <-> mean "are equivalent for any value of v")
>
> According to C89 3.3.3.3
> ~v <-> UINT_MAX - v
>
> Thus
> ~(v-1) <-> UINT_MAX - (v-1)
> ~(v-1) <-> UINT_MAX - v + 1
> ~(v-1) <-> (UINT_MAX + 1) - v
>
> Adding (UINT_MAX + 1) to an unsigned int variable is a NOP,
> thus ~(v-1) <-> -v

First off, ~(v-1) is the canonical definition of 2's complement negation of
a value v. Your analysis seems to preclude the C standard's requirement
for "pure binary" representation of unsigned integers, and sign&magnitude
and ones-complement representation for signed integers, by defining
negation as a two's-complement operation. I'll have to spend some time

~(v-1) <-> -v
no longer fits within the given parameters of unsigned integers, as there is
no viable representation /as an unsigned integer/ of a negative value. If
~(v-1) <-> (UINT_MAX + 1) - v
this would not be a problem, as neither side of this equation results in a
negative value.

--
Lew Pitcher
"In Skills, We Trust"

glen herrmannsfeldt
Guest
Posts: n/a

 03-19-2013
James Kuyper <(E-Mail Removed)> wrote:
> On 03/19/2013 10:49 AM, Noob wrote:

(snip)
>> Considering a properly initialized unsigned int variable v,
>> are -v and ~(v-1) equivalent for any value of v, even on
>> the DS9k?

(snip)
>> I think this is true always, I don't think the "usual arithmetic
>> conversions" come in play in problematic ways?

> Since v is unsigned int, and 1 has the type int, the usual arithmetic
> conversions require that 1 be converted to unsigned int, and then
> everything goes through fine.

> The tricky case is an unsigned type where TYPE_MAX < INT_MAX, and v==0.
> In that case, the unsigned value is converted to int, so the result is
> ~(-1), which has different results depending upon whether 2's
> complement, 1's complement, or sign-magnitude representation is used.

Other than the DS9K, the sign-magnitude machines that I know about
are word addressed. They might not have any type smaller than int.

The last one I know about is the 7094, successor to the 7090 and 709.
With IBM OSs, they used six BCDIC (IBM called it BCD) characters
per 36 bit word. As I understand it, the card reader reads each
card punch row into two 36 bit words. Software then converts that
to six characters per word. Note that the last eight card colunmns
aren't read. (Possibly that was the 704, and not the 709. It is,
at least, the reason Fortran ignores columns 73-80 (in fixed-form).

Nine track tape drives didn't come along until later. Seven track
drives, six plus (even or odd) parity were used. So, what would
CHAR_BIT be on the 7094?

For ones complement, there are the CDC machines (10 six bit characters
in a 60 bit word) and Unisys machines, but popular long after the 7090.

> The DS9k, of course, only uses 2's complement representation in it's
> floating point implementation.

In PDP-10 style (2's complement the whole word) or DSP style
(significand only)?

The PDP-10 allows one to use integer compare instructions on floating
point values (and get the right result). Somewhat convenient for
sorting, such that you don't need to know which fields are integer
and which aren't.

Seems to me that C pretty much requires binary for integer types,
but, for example, IEEE 754-2008 style decimal float should work
(which is sign magnitude). But a nine's complement or ten's
complement decimal float form should also work.

-- glen

army1987
Guest
Posts: n/a

 03-21-2013
On Tue, 19 Mar 2013 08:13:51 -0700, China Blue Clay wrote:

> In article <ki9tp3\$7ob\$(E-Mail Removed)>, Noob <root@127.0.0.1> wrote:

>> Considering a properly initialized unsigned int variable v, are -v and
>> ~(v-1) equivalent for any value of v, even on the DS9k?

>
> Not with ones complement or signed magnitude.

The OP is talking about *unsigned* variables.

--
[ T H I S S P A C E I S F O R R E N T ]
Troppo poca cultura ci rende ignoranti, troppa ci rende folli.
-- fathermckenzie di it.cultura.linguistica.italiano
<http://xkcd.com/397/>

Noob
Guest
Posts: n/a

 03-21-2013
China Blue Clay wrote:

> army1987 wrote:
>
>> China Blue Clay wrote:
>>
>>> Noob wrote:

>>
>>>> Considering a properly initialized unsigned int variable v,
>>>> are -v and ~(v-1) equivalent for any value of v?
>>>
>>> Not with ones complement or signed magnitude.

>>
>> The OP is talking about *unsigned* variables.

>
> Doesn't matter. With one's complement -v = ~v,
> and signed magnitude -v = 0x800...00 ^ v.

The "signedness" of the variable does matter. The standard fully
specifies the behavior of the ~ operator for unsigned types:

(C89) 3.3.3.3 Unary arithmetic operators

Constraints

The operand of the unary + or - operator shall have arithmetic
type; of the ~ operator, integral type; of the ! operator, scalar
type.

Semantics

The result of the unary + operator is the value of its operand.
The integral promotion is performed on the operand, and the result has
the promoted type.

The result of the unary - operator is the negative of its operand.
The integral promotion is performed on the operand, and the result has
the promoted type.

The result of the ~ operator is the bitwise complement of its
operand (that is, each bit in the result is set if and only if the
corresponding bit in the converted operand is not set). The integral
promotion is performed on the operand, and the result has the promoted
type. The expression ~E is equivalent to (ULONG_MAX-E) if E is
promoted to type unsigned long , to (UINT_MAX-E) if E is promoted to
type unsigned int.

As for the behavior of unary minus on an unsigned variable, I believe
it is fully defined by the following paragraph:

"A computation involving unsigned operands can
never overflow, because a result that cannot be represented by the
resulting unsigned integer type is reduced modulo the number that is
one greater than the largest value that can be represented by the
resulting unsigned integer type."

Thus -v "reduces to" UINT_MAX+1-v == UINT_MAX-(v-1)

"one's complement" and "sign magnitude" are concepts for signed
variables, they have no bearing on unsigned variables. Or did I
misunderstand what you wrote?

Regards.

Noob
Guest
Posts: n/a

 03-21-2013
Lew Pitcher wrote:

> Noob wrote:
>
>> Considering a properly initialized unsigned int variable v,
>> are -v and ~(v-1) equivalent for any value of v, even on
>> the DS9k?
>>
>> (let <-> mean "are equivalent for any value of v")
>>
>> According to C89 3.3.3.3
>> ~v <-> UINT_MAX - v
>>
>> Thus
>> ~(v-1) <-> UINT_MAX - (v-1)
>> ~(v-1) <-> UINT_MAX - v + 1
>> ~(v-1) <-> (UINT_MAX + 1) - v
>>
>> Adding (UINT_MAX + 1) to an unsigned int variable is a NOP,
>> thus ~(v-1) <-> -v

>
>
> First off, ~(v-1) is the canonical definition of 2's complement negation of
> a value v. Your analysis seems to preclude the C standard's requirement
> for "pure binary" representation of unsigned integers, and sign&magnitude
> and ones-complement representation for signed integers, by defining
> negation as a two's-complement operation. I'll have to spend some time

First, do you dispute the following statement?

"Considering a properly initialized unsigned int variable v,
-v and ~(v-1u) equivalent, for any and all value of v"

In other words, considering foo:
void foo(unsigned v) { assert(-v == ~(v-1u)); }
foo will never fail on any conforming implementation known
(or unknown) to mankind.

Second, as I replied to CBC, "one's complement", "two's complement",
"sign magnitude" are all concepts involving /signed/ integral types.
These notions do not come in play for /unsigned/ types, AFAIU.
(Do you dispute this?)

> ~(v-1) <-> -v
> no longer fits within the given parameters of unsigned integers, as there is
> no viable representation /as an unsigned integer/ of a negative value.

This statement is confusing. Are you saying that
unsigned v = 42; v = -v;
has undefined behavior?

> If you had stopped at ~(v-1) <-> (UINT_MAX + 1) - v
> this would not be a problem, as neither side of this equation results in a
> negative value.

Since "unsigned int" arithmetic is performed modulo (UINT_MAX+1),
UINT_MAX+1+u and u are equivalent (as in "they have the same value,
as far as the abstract machine is concerned")

Regards.