bitwise operator !!

C

CBFalconer

pete said:
.... snip ...

I specified the implementation defined result of a right shift
on a negative integer. It's the kind of shift known as an
"arithmetic shift". The other kind of shift that I'm familiar
with, is called a "logical shift".

The only right shift available in C is that controlled by a '>>'
token. Whether it is an arithmetic or logical shift is unknown.
 
T

Tim Rentsch

jameskuyper said:
Tim said:
jameskuyper said:
CBFalconer wrote:
blargg wrote:

... snip ...

BTW, in another message in this thread someone said that shifting
a signed value right is undefined. My copy of the C99 standard
says otherwise:

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If
E1 has an unsigned type or if E1 has a signed type and a
nonnegative value, the value of the result is the integral part
of the quotient of E1 / 2^E2. If E1 has a signed type and a
negative value, the resulting value is implementation-defined.

Your quote (repeated above) specifies implementation-defined. This
also means that you don't know what your code will do on another
compiler or system.

You're confusing "implementation-defined value" with "undefined
behavior", which is precisely the distinction he's making. If the
behavior were undefined, as was incorrectly claimed, it would indeed
be the case that "you don't know what your code will do on another
machine", and the implemenation for that other machine has no
obligation to document what that behavior will be.

Since the behavior is in fact implementation-defined, you know that
such code will produce a valid value of the specified type, no matter
which conforming implementation you use. [...]

Except that 6.2.6.2 p 4 means there can be undefined behavior:

If the implementation does not support negative zeros, the
behavior of the &, |, ^, ~, <<, and >> operators with arguments
that would produce such a value is undefined.

3.17.1: "implementation-defined value
unspecified value where each implementation documents how the choice
is made"
3.17.1: "unspecified value
valid value of the relevant type where this International Standard
imposes no
requirements on which value is chosen in any instance."

Therefore, an implementation-defined value is required to be a valid
value. On a system where negative zeros are not valid, they can never
be that implementation's choice in any situation where the standard
says that a value is implementation-defined. This means that 6.2.6.2p4
can only apply when the result is NOT implementation-defined.

This interpretation has a problem: with this interpretation, I can't
find any way to apply 6.2.6.2p4 to any operation involving either
shift operator that would otherwise have defined behavior, so
inclusion of the shift operators in 6.2.6.2p4 seems to be redundant;
it does not, however, contradict anything said elsewhere. For the
other four operators, it's trivial to come up with cases where the
resulting value would otherwise be standard-defined as the one
represented by the bit pattern for negative zero, if it weren't for
the fact that this clause renders the behavior undefined.

I acknowlege the apparent conflict between the two sections
(namely, 6.2.6.2 p 4 and the description of >> in 6.5.7 p 5). In
light of the problem (as you point out) of there being no reason
for the inclusion of >> in 6.2.6.2 p 4, the only interpretation I
can find that makes any sense is that the phrase "the resulting
value is implementation-defined" (given in 6.5.7 p 5) admits the
possibility that an implementation can define the resulting value
in such a way that the undefined behavior provision of 6.2.6.2p4
can be invoked. In short, an implementation can choose to select
undefined behavior here if it wants to.

There is further evidence that the phrase "the resulting value is
implementation-defined" doesn't always mean a valid value is
produced. Consider these two sentences together:

(from 6.5.7 p 5):

If E1 has a signed type and a negative value, the resulting value
is implementation-defined.

(from 6.2.5 p 3):

If any other character is stored in a char object, the resulting
value is implementation-defined but shall be within the range of
values that can be represented in that type.

There is no reason for the clause after the "but" in 6.2.5p3
unless "the resulting value is implementation-defined" admits
the possibility that a non-valid value might otherwise be
produced.

There is also 6.5p4:

Some operators (the unary operator ~, and the binary operators <<, required to have operands that have integer type. These operators
yield values that depend on the internal representations of
integers, and have implementation-defined and undefined aspects
for signed types.

The only way that >> can have "undefined aspects" is if 6.5.7 p 5
allows some of the implementation-defined results to invoke
undefined behavior.

Taking all of these together, it seems clear that the Standard
allows >> to be defined (at least in some implementations) so that
some operand values invoke undefined behavior.
 
T

Tim Rentsch

Harald van =?UTF-8?b?RMSzaw==?= said:
The shifting method doesn't round towards zero, but division may.

Just doing a straight >> doesn't round towards zero, but I was
referring to the shifting method described above, which does round
towards zero (not counting the undefined behavior at INT_MIN).

How about

(a)

if (x < 0) {
x = ~(~x >> 5);
}

(b)

if (x < 0) {
x = ~(~x / (32 % 33));
}

Did I miss something here?

Aren't there problems with potential undefined behavior
for the ~ operator?

Also, I believe using ~ this way doesn't always produce the right
answer under two's complement or signed magnitude.
 
H

Harald van Dijk

Just doing a straight >> doesn't round towards zero, but I was referring
to the shifting method described above, which does round towards zero
(not counting the undefined behavior at INT_MIN).

Thanks for the clarification, I had missed that. From the text before the
code I believed and believe that rounding to -INF was intended, but you're
right, that's not what the code does.
Aren't there problems with potential undefined behavior for the ~
operator?

If x < 0, then the sign bit is already set, so ~x is well-defined. As for
~(~x >> 5), it can only produce a trap representation for ones'
complement, and only if a right shift with sign bit propagation would
produce that same trap representation. (Yes, my wording is sloppy, but I
think it is clear what I am trying to say.)
Also, I believe using ~ this way doesn't always produce the right answer
under two's complement or signed magnitude.

It produces the value of x right-shifted five bits (if that value
exists), with the topmost five bits set to 1, regardless of representation
method. This answer may be unexpected, but since that was what was asked,
I think it is the right answer.
 
H

Harald van Dijk

Harald said:
[...]
if (0 > x) {
x = -x;
x >>= 5;
x = -x;
} [...]
Exercise for the reader: write code to accomplish this operation,
with rounding towards zero, and no undefined behavior:
(a) using >>
(b) using / and %

How about

(a)

if (x < 0) {
x = ~(~x >> 5);
[...]
What's wrong with the following (posted to this thread a while back)

(x < 0) ? -(int) (-(unsigned) x >> 5) : x >> 5

?

If x == -1, your expression gives 0, while mine gives -1. Yours matches
the original code, mine matches the (snipped) text describing the original
code.
 
T

Tim Rentsch

Harald van =?UTF-8?b?RMSzaw==?= said:
[snip]
Exercise for the reader: write code to accomplish this operation,
with rounding towards zero, and no undefined behavior:
(a) using >>
(b) using / and %

Note: exercise refers to

if (0 > x) {
x = -x;
x >>= 5;
x = -x;
}

that appeared in the snipped text.

If x < 0, then the sign bit is already set, so ~x is well-defined. As for
~(~x >> 5), it can only produce a trap representation for ones'
complement, and only if a right shift with sign bit propagation would
produce that same trap representation. (Yes, my wording is sloppy, but I
think it is clear what I am trying to say.)

The problem is, that's undefined behavior. The exercise asks for
no undefined behavior.
It produces the value of x right-shifted five bits (if that value
exists), with the topmost five bits set to 1, regardless of representation
method. This answer may be unexpected, but since that was what was asked,
I think it is the right answer.

I see, there was confusion about what was asked for. The
exercise means to ask for a way of doing arithmetic shift,
with rounding towards zero, and no undefined behavior.
I think you interpreted the exercise as asking for a logical
shift, but that's not what the earlier example code fragment
does.
 
T

Tim Rentsch

Harald said:
[...]
if (0 > x) {
x = -x;
x >>= 5;
x = -x;
} [...]
Exercise for the reader: write code to accomplish this operation,
with rounding towards zero, and no undefined behavior:
(a) using >>
(b) using / and %

How about

(a)

if (x < 0) {
x = ~(~x >> 5); [...]
Aren't there problems with potential undefined behavior for the ~
operator?

If x < 0, then the sign bit is already set, so ~x is well-defined. As for
~(~x >> 5), it can only produce a trap representation for ones'
complement, and only if a right shift with sign bit propagation would
produce that same trap representation. (Yes, my wording is sloppy, but I
think it is clear what I am trying to say.)
[...]

What's wrong with the following (posted to this thread a while back)

(x < 0) ? -(int) (-(unsigned) x >> 5) : x >> 5

? It should be the same efficiency (negate, shift, negate, as opposed to
complement, shift, complement yours does), and completely portable without
even touching signed value representation issues.

The drawback is, it can yield a wrong result on implementations where
UINT_MAX == INT_MAX, which is allowed by the Standard. So it isn't
quite as portable as it might appear.
 
T

Tim Rentsch

Harald van =?UTF-8?b?RMSzaw==?= said:
Harald said:
19:35 -0800, Tim Rentsch wrote:
pete wrote: [...]
if (0 > x) {
x = -x;
x >>= 5;
x = -x;
} [...]
Exercise for the reader: write code to accomplish this operation,
with rounding towards zero, and no undefined behavior:
(a) using >>
(b) using / and %

How about

(a)

if (x < 0) {
x = ~(~x >> 5);
[...]
What's wrong with the following (posted to this thread a while back)

(x < 0) ? -(int) (-(unsigned) x >> 5) : x >> 5

?

If x == -1, your expression gives 0, while mine gives -1. Yours matches
the original code, mine matches the (snipped) text describing the original
code.

The 0 result is what the exercise asks for -- rounding towards zero.
 
J

James Kuyper

blargg said:
Tim said:
(e-mail address removed) (blargg) writes: [...]
What's wrong with the following (posted to this thread a while back)

(x < 0) ? -(int) (-(unsigned) x >> 5) : x >> 5

? It should be the same efficiency (negate, shift, negate, as opposed to
complement, shift, complement yours does), and completely portable without
even touching signed value representation issues.
The drawback is, it can yield a wrong result on implementations where
UINT_MAX == INT_MAX, which is allowed by the Standard. So it isn't
quite as portable as it might appear.

So if INT_MAX = UINT_MAX = 0x7FFF, INT_MIN = -0x8000 and x = INT_MIN, then
(unsigned) x = 0. Oh well. But are such implementations allowed? (as in,
care to reference/quote the sections of the standard?)

No: 5.2.4.2.1p1 requires that UINT_MAX be at least 65535 == 0xFFFF.
UINT_MAX==INT_MAX is possible only when 'int' has more than 16 bits; but
as far as I can see, it's perfectly legal when that is the case. The
relevant requirement is 6.2.5p9:

"The range of nonnegative values of a signed integer type is a subrange
of the corresponding unsigned integer type, "

In other words, INT_MAX <= UINT_MAX
 
T

Tim Rentsch

Tim said:
(e-mail address removed) (blargg) writes: [...]
What's wrong with the following (posted to this thread a while back)

(x < 0) ? -(int) (-(unsigned) x >> 5) : x >> 5

? It should be the same efficiency (negate, shift, negate, as opposed to
complement, shift, complement yours does), and completely portable without
even touching signed value representation issues.

The drawback is, it can yield a wrong result on implementations where
UINT_MAX == INT_MAX, which is allowed by the Standard. So it isn't
quite as portable as it might appear.

So if INT_MAX = UINT_MAX = 0x7FFF, INT_MIN = -0x8000 and x = INT_MIN, then
(unsigned) x = 0. Oh well. But are such implementations allowed? (as in,
care to reference/quote the sections of the standard?)

Do you have a copy of the Standard? If you don't, try googling
for n1256, which should get you to the latest revision of C99
standard. I really recommend that you get one.

The relevant citation is 6.2.6.2 p 2

For signed integer types, the bits of the object representation shall
be divided into three groups: value bits, padding bits, and the sign
bit. There need not be any padding bits; there shall be exactly one
sign bit. 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). 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: [...goes on...]

If M == N then the unsigned type has the same number of value bits
as the signed type, e.g., UINT_MAX == INT_MAX.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,479
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top