Bitwise Operator Effects on Padding Bits

[Shao Miller]

Hello folks. I hope you're having a nice day today.

Which of the following groups of bits in an integer type will be
complemented by the unary '~' bitwise operator?:

- value bits
- padding bits
- the sign bit (for signed integer types)

 

[H Vlems]

Hello folks.  I hope you're having a nice day today.

Which of the following groups of bits in an integer type will be
complemented by the unary '~' bitwise operator?:

- value bits
- padding bits
- the sign bit (for signed integer types)

Why don't you write a little program and let the computer figure it
out?

 

[Shao Miller]

Why don't you write a little program and let the computer figure it
out?

Ok, thanks. Perhaps I could use the object representation to examine
the bits, would that make sense? If so, how do I know which bits in the
object representation correspond to the aforementioned groups?

 

[Ian Collins]

Ok, thanks. Perhaps I could use the object representation to examine the
bits, would that make sense? If so, how do I know which bits in the
object representation correspond to the aforementioned groups?

Find one of those mythical machines with padding bits and have look!

 

[Eric Sosman]

Hello folks. I hope you're having a nice day today.

Which of the following groups of bits in an integer type will be
complemented by the unary '~' bitwise operator?:

- value bits

Affected.

- padding bits

May be affected, may not be. Definitely not guaranteed
to be inverted.

- the sign bit (for signed integer types)

Affected. The consequences are not assuredly useful.

 

[Shao Miller]

What good would that do? Maybe some implementations differ in what they
do. The correct solution is to read the specification and find out what
it says. Or ask people who are likely to know.

Thanks, Mr. P. Seebach. I fully agree with your correct solution.

 

[Ian Collins]

Do you have a machine and C compiler that supports _Bool? Is it
mythical?
Several...

I think you are conflating padding bits with trap representations.
Padding bits are very common, but machines with trap representations
(which might well derive from the padding bits) are rarer.

I think you are correct, sorry for the noise.

 

[James Dow Allen]

Why don't you write a little program and let the computer figure it
out?

In the majority of cases, where real-program testing is
the obvious and correct way to get an answer, posters are
warned NOT to get their answers this way!

In the cases where posters want portable code, and testing
on a given machine is irrelevant, this answer is given!

Comp.lang.c. Great fun!!

James

 

[Francois Grieu]

I'm unsure about that, see below.

Oh please feel free to call me by my first name. Hopefully it is
sufficiently unique that I'll know who you mean.


Right. The padding bits will either be set or unset... I was more
asking about whether they are directly complemented by the unary '~'
operator.


I've read 6.2.6.2 several times but didn't read anything about whether
or not unary '~' (and other bitwise friends) are restricted to
particular bit groups. I think it's clear from those two points you
reference that the padding bits are unspecified. What I'm wondering is
if they must toggle when one applies unary '~' to an operand. Still
unspecified, but in the other state. My interpretation is that they are
not defined to toggle, but I cannot prove it with the Standard.

Also see 6.5.3.3p1 and See 6.5.3.3p4

The operand of the unary ~ operator shall have integer type.

The result of the ~ operator is the bitwise complement of its
(promoted) 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 integer promotions are performed on the operand,
and the result has the promoted type. If the promoted type is
an unsigned type, the expression ~E is equivalent to the
maximum value representable in that type minus E.

Because of *each*, I read this, even combined with 6.2.6.2,
as implying ~ inverts padding bits. One thing is sure: whatever
effect there is on padding bits has no incidence on the value
represented. The point is moot since the padding bit is a dodo,
or a even a dahu AFAIK.

Effect of ~ on the value and the possible occurrence of a trap
representation depends on if the promoted type is signed or
unsigned, and in the former case of which of the options in
6.2.6.2p2 (sign and magnitude, two's complement, one's
complement) is in effect.


Speaking of dodos, anyone know a machine, with a C compiler
in actual use, that does not use two's complement? Is there
support for keeping only that and/or dropping padding bits
in integer types in a forthcoming C standard?

Francois Grieu

 

[Ben Bacarisse]

Also see 6.5.3.3p1 and See 6.5.3.3p4

The operand of the unary ~ operator shall have integer type.

The result of the ~ operator is the bitwise complement of its
(promoted) 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 integer promotions are performed on the operand,
and the result has the promoted type. If the promoted type is
an unsigned type, the expression ~E is equivalent to the
maximum value representable in that type minus E.

Because of *each*, I read this, even combined with 6.2.6.2,
as implying ~ inverts padding bits. One thing is sure: whatever
effect there is on padding bits has no incidence on the value
represented.

That's a strong argument but it's not bullet proof. The operand is
promoted and integer promotion is all about values not representations.
Even if the type does not change, integer promotion is guaranteed to
preserve the value but not the representation.

The point is moot since the padding bit is a dodo,
or a even a dahu AFAIK.

As I keep saying, what about _Bool?

I think the question is moot for another reason altogether. Even if ~
is absolutely forced to invert a "value" that somehow keeps the padding
bits, none of assignment, parameter passing nor initialisation are
required to preserve them so how can you tell? I take Shao Miller's
intent to be to find some way to inspect them and that requires that the
result of ~E finds itself, unchanged, inside some object or other.

<snip>

 

[Eric Sosman]

On 9/6/2010 6:27 PM, Shao Miller wrote:
Eric Sosman wrote:
On 9/6/2010 5:24 PM, Shao Miller wrote:
Hello folks. I hope you're having a nice day today.

Which of the following groups of bits in an integer type will be
complemented by the unary '~' bitwise operator?:
[...]

- padding bits

May be affected, may not be. Definitely not guaranteed
to be inverted.

I'm unsure about that, see below.
[...]
Also see 6.5.3.3p1 and See 6.5.3.3p4

The operand of the unary ~ operator shall have integer type.

The result of the ~ operator is the bitwise complement of its
(promoted) 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 integer promotions are performed on the operand,
and the result has the promoted type. If the promoted type is
an unsigned type, the expression ~E is equivalent to the
maximum value representable in that type minus E.

Because of *each*, I read this, even combined with 6.2.6.2,
as implying ~ inverts padding bits.

I believe 6.2.6.2's "The values of any padding bits are
unspecified" should be taken as the overriding statement of how
padding bits are treated. In its description of expressions,
6.5 does not seem to mention padding bits at all, so I don't
think you can take the absence of an "except for padding bits"
clause as indicating that the ~ operator specifies anything
about them. The descriptions of & and | and << and >> also
omit mention of padding bits, yet I'm confident there's no
claim about what >>, say, does with padding in its operand.

Back to ~, though: The reading you favor seems at odds with
footnote 44, which describes the possible use of a padding bit
as a parity bit. If the value bits and sign bit taken together
come to an even number of bits and you invert them all, the
parity of the whole remains unchanged. So if ~ also inverted
a parity bit, the result would have bad parity -- and this would
contradict the assertion that a valid arithmetic operation on a
valid value cannot produce a trap representation. Footnotes are
of course non-normative, but they offer a guide to how the writers
expected the Standard to be understood.

 

[Shao Miller]

I'm unsure about that, see below.

... ... ...
The operand of the unary ~ operator shall have integer type.

... ... ...
Because of *each*, I read this, even combined with 6.2.6.2,
as implying ~ inverts padding bits. One thing is sure: whatever
effect there is on padding bits has no incidence on the value
represented. The point is moot since the padding bit is a dodo,
or a even a dahu AFAIK.
... ... ...

Thank you very much for your response, Mr. F. Grieu. There is
definitely some food for thought in your post. Perhaps it's moot, as
you say.

 

[Keith Thompson]

Francois Grieu wrote: [snip]

Thank you very much for your response, Mr. F. Grieu. There is
definitely some food for thought in your post. Perhaps it's moot, as
you say.

Just a thought: You could avoid any uncertainty about how to address
people by not addressing them by name at all. For example, it's
obvious from the attribution line who I'm addressing; there's no need
to mention your name.

I don't suggest that there's anything wrong with the way you're
doing it, but it is a trifle unusual and I personally find that it
distracts (*very* slightly) from the points you make.

Feel free to ignore this.

 

[Shao Miller]

That's a strong argument but it's not bullet proof. The operand is
promoted and integer promotion is all about values not representations.
Even if the type does not change, integer promotion is guaranteed to
preserve the value but not the representation.

Thank you for your valuable response as usual, Ben.

If I understand your point, it's that the padding bits of the operand
mightn't be preserved during promotion, so that information is
theoretically gone before bit-toggling takes place. That's good reasoning.

We do also have 6.3p2 regarding preservation of representation. Perhaps
that could apply for those few cases where promotion causes no change in
type. But that's now fewer cases, anyway.

As I keep saying, what about _Bool?

And bit-fields, for that matter. If we have an 'int' bit-field, since
there's no type change in promotion, I wonder if the other bits in the
surrounding storage unit are preserved in the representation of the
promoted result. What do you think?

I think the question is moot for another reason altogether. Even if ~
is absolutely forced to invert a "value" that somehow keeps the padding
bits, none of assignment, parameter passing nor initialisation are
required to preserve them so how can you tell? I take Shao Miller's
intent to be to find some way to inspect them and that requires that the
result of ~E finds itself, unchanged, inside some object or other.

Yup. You're right on, and this would toss away inspection value unless
6.3p2 preserves padding bits in an assignment.

 

[Shao Miller]

Eric Sosman wrote:
On 9/6/2010 6:27 PM, Shao Miller wrote:
Eric Sosman wrote:
On 9/6/2010 5:24 PM, Shao Miller wrote:
Hello folks. I hope you're having a nice day today.

Which of the following groups of bits in an integer type will be
complemented by the unary '~' bitwise operator?:
[...]

- padding bits

May be affected, may not be. Definitely not guaranteed
to be inverted.

I'm unsure about that, see below.
[...]
Also see 6.5.3.3p1 and See 6.5.3.3p4

The operand of the unary ~ operator shall have integer type.

The result of the ~ operator is the bitwise complement of its
(promoted) 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 integer promotions are performed on the operand,
and the result has the promoted type. If the promoted type is
an unsigned type, the expression ~E is equivalent to the
maximum value representable in that type minus E.

Because of *each*, I read this, even combined with 6.2.6.2,
as implying ~ inverts padding bits.

I believe 6.2.6.2's "The values of any padding bits are
unspecified" should be taken as the overriding statement of how
padding bits are treated. In its description of expressions,
6.5 does not seem to mention padding bits at all, so I don't
think you can take the absence of an "except for padding bits"
clause as indicating that the ~ operator specifies anything
about them.

"...computation of a value..." in 6.5 combined with your "unspecified"
above seems like good reasoning.

The descriptions of & and | and << and >> also
omit mention of padding bits, yet I'm confident there's no
claim about what >>, say, does with padding in its operand.

Hmmm... The bitwise shift operators do mention "width"[6.5.7p3].
"Width" excludes padding bits[6.2.6.2p6], unless I'm mistaken. So
"there's no claim" amounts to "undefined behavior" which amounts to
"there's no claim".

Back to ~, though: The reading you favor seems at odds with
footnote 44, which describes the possible use of a padding bit
as a parity bit. If the value bits and sign bit taken together
come to an even number of bits and you invert them all, the
parity of the whole remains unchanged. So if ~ also inverted
a parity bit, the result would have bad parity -- and this would
contradict the assertion that a valid arithmetic operation on a
valid value cannot produce a trap representation. Footnotes are
of course non-normative, but they offer a guide to how the writers
expected the Standard to be understood.

Yes I mentioned the same concern about parity in an earlier post; seems
that we'd be in a pickle if unary '~' complemented parity bits which led
to a trap representation.

Speaking of non-normative footnotes, that footnote's sibling, footnote
45, causes me a bit of confusion. If we use '~' to produce a negative
zero and it's a trap representation, what kind of exceptional condition
is that?

 

[Shao Miller]

I don't think this is well-formed question. For one thing, ~ operates
on a promoted operand and I don't think promotion preserves padding
bits. In fact, I don't think promotion results in the kind of "thing"
that can even have padding -- it results in a value. Secondly, padding
bits reside in objects and the result of ~E is not an object. Even if
we speculate that promotion somehow results in a "value" with padding
bits and the ~ must invert them, how could you ever tell?

In effect I am asking what the question means in terms of C programs.
What programs are you imagining whose behaviour is altered by the answer
to your question?

Hmmm... Good point. If we cannot depend on the padding bits of the
result of an expression persisting into an object where the value is
stored, the information about the padding bits is gone.

This bit seems very vague. What are these expectations and what might
they enable us to determine about the environment?

Well since there aren't any padding bits in 'unsigned char' (and thus
the object representation), we can compare the object representations of
various numbers to find out what their differences are. This might
enable us to determine which of the three representations are being
used, or we might be able to find the sign bit. Or could we?

 

[Shao Miller]

Francois Grieu wrote: [snip]
Thank you very much for your response, Mr. F. Grieu. There is
definitely some food for thought in your post. Perhaps it's moot, as
you say.

Just a thought: You could avoid any uncertainty about how to address
people by not addressing them by name at all. For example, it's
obvious from the attribution line who I'm addressing; there's no need
to mention your name.

I don't suggest that there's anything wrong with the way you're
doing it, but it is a trifle unusual and I personally find that it
distracts (*very* slightly) from the points you make.

Feel free to ignore this.

I guess I just thought it was more personal in an expression of
appreciation, but thanks for the feedback. Perhaps that's a better
strategy.

 

[Ben Bacarisse]

Ben Bacarisse wrote:

Well since there aren't any padding bits in 'unsigned char' (and thus
the object representation), we can compare the object representations
of various numbers to find out what their differences are. This might
enable us to determine which of the three representations are being
used, or we might be able to find the sign bit. Or could we?

I don't see any connection to padding bits. You can determine the
number representation by inspecting the value of -1 & 3. It will 1, 2
or 3 depending on the use of sign+magnitude, ones complement or twos
complement respectively. However, like "endianness", wanting to know is
often a sign of a wrong turn having been taken in the design (not
always, but often).

 

[Ben Bacarisse]

Thank you for your valuable response as usual, Ben.

If I understand your point, it's that the padding bits of the operand
mightn't be preserved during promotion, so that information is
theoretically gone before bit-toggling takes place. That's good
reasoning.

It's a bit stronger than that. Promotion produces a value not a
representation. I would say that any promoted operand has no padding
bits at all.

We do also have 6.3p2 regarding preservation of representation.
Perhaps that could apply for those few cases where promotion causes no
change in type. But that's now fewer cases, anyway.

I'd say the same even if the type does not change.

And bit-fields, for that matter. If we have an 'int' bit-field, since
there's no type change in promotion, I wonder if the other bits in the
surrounding storage unit are preserved in the representation of the
promoted result. What do you think?

My point is that promoted results don't have a representation.

At some level it doesn't matter either way. Imagine an implementation
that adds 107 padding bits to every promoted int. Since you can't
inspect these bits and they have no effect on the value, how could you
tell? I think it is simper to say they don't form part of the value
that results from a promotion.

But if it pleases you to think of them being there, why not? In fact,
lets just say that all padding bits stay with their values during
promotion and they all get toggled by ~. Now what? As far as I can
tell, such a language has the same semantics as the one I am describing.

 

[Ben Bacarisse]

I disagree.

((((signed char)-1) + (signed char)0) & 3)

will still tell you which representation of negative integers
is used.

Yes, what I wrote does not stand out of context. I should just have
said that promoted results don't have padding bits (though as I pointed
out this is just a simplification -- you can't tell if they do or do
not).

I think an argument can be made that values (such as promoted results)
don't have a representation but it would be verging on sophistry.