Velocity Reviews > Bitwise operators.

# Bitwise operators.

dspfun
Guest
Posts: n/a

 01-13-2008
C doesn't specify the bit-layout in memory of the different types, so
how are the operations ( & | ~ ^ << >>) defined to modify the objects
(which does not have its bit-layout defined) ?

6.2.6.1p2:
Except for bit-fields, objects are composed of contiguous sequences of
one or more bytes,
the number, order, and encoding of which are either explicitly
specified or
implementation-defined.

Lets say for example:

unsigned int a = 6;
a = a & 3;

Do we know anything about the bit-layout of a?

Or do we simply know that the value of a is 2 after the last
statement, and we know nothing about the bit-layout? But why the name
bitwise operators if we don't know which bit the operator and operand
modifies?

What is the benefit of using the bit-operators if we do not know the
bit-layout of objects?

Ben Pfaff
Guest
Posts: n/a

 01-13-2008
dspfun <(E-Mail Removed)> writes:

> C doesn't specify the bit-layout in memory of the different types, so
> how are the operations ( & | ~ ^ << >>) defined to modify the objects
> (which does not have its bit-layout defined) ?

The bitwise operators are defined in terms of values.

> Lets say for example:
>
> unsigned int a = 6;
> a = a & 3;
>
> Do we know anything about the bit-layout of a?

No.

> Or do we simply know that the value of a is 2 after the last
> statement, and we know nothing about the bit-layout?

Yes.

> But why the name bitwise operators if we don't know which bit
> the operator and operand modifies?

We know that the statement modified the bit with value 4.
--
Ben Pfaff
http://benpfaff.org

dspfun
Guest
Posts: n/a

 01-13-2008
On 14 Jan, 00:08, Ben Pfaff <(E-Mail Removed)> wrote:
> dspfun <(E-Mail Removed)> writes:
> > C doesn't specify the bit-layout in memory of the different types, so
> > how are the operations ( & | ~ ^ << >>) defined to modify the objects
> > (which does not have its bit-layout defined) ?

>
> The bitwise operators are defined in terms of values.
>

Ok, thanks!

I believe it is the following in the standard the specifies this? :

6.5p4
Some operators (the unary operator ~, and the binary operators <<, >>,
&, ^, and |,
collectively described as bitwise operators) are 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.

Tomás Ó hÉilidhe
Guest
Posts: n/a

 01-14-2008
dspfun:

> C doesn't specify the bit-layout in memory of the different types, so
> how are the operations ( & | ~ ^ << >>) defined to modify the objects
> (which does not have its bit-layout defined) ?

C *does* in fact specify the bit-layout of integer types. It doesn't do
so in plain English, but it is inferred from other statements (such as
the fact that shifting to the left is the same as multiplying by powers
of two). It uses simple canonical binary:

0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000

> 6.2.6.1p2:
> Except for bit-fields, objects are composed of contiguous sequences of
> one or more bytes,
> the number, order, and encoding of which are either explicitly
> specified or
> implementation-defined.
>
> Lets say for example:
>
> unsigned int a = 6;
> a = a & 3;
>
> Do we know anything about the bit-layout of a?

At initialisation, a is 110. After the assignment, it's 10.

> Or do we simply know that the value of a is 2 after the last
> statement, and we know nothing about the bit-layout?

We are certain that the value is two and that the bit layout is 10.

> But why the name
> bitwise operators if we don't know which bit the operator and operand
> modifies?
>
> What is the benefit of using the bit-operators if we do not know the
> bit-layout of objects?

Fortunately for unsigned integer types, we know the bit patterns
exactly. For signed integer types, we must take the number system into
account, but this can easily be determined.

--
Tomás Ó hÉilidhe

Walter Roberson
Guest
Posts: n/a

 01-14-2008
In article <Xns9A255E792E66toelavabitcom@194.125.133.14>,
=?iso-8859-1?q?Tom=E1s_=D3_h=C9ilidhe?= <(E-Mail Removed)> wrote:
>dspfun:

>> C doesn't specify the bit-layout in memory of the different types, so
>> how are the operations ( & | ~ ^ << >>) defined to modify the objects
>> (which does not have its bit-layout defined) ?

>C *does* in fact specify the bit-layout of integer types. It doesn't do
>so in plain English, but it is inferred from other statements (such as
>the fact that shifting to the left is the same as multiplying by powers
>of two).

Those operations are -defined- by their result on *values*, not by
bit representation. If I recall correctly, ~ is the only operation
defined in terms of bits rather than in terms of values.

Because the operations are defined in terms of values, it doesn't
matter to C what the bit ordering is in memory. For example, it
does not say whether in a two-octet integeral type whether the
internal order is AAAAAAAABBBBBBBB or BBBBBBBBAAAAAAAA or
perhaps something else completely.

If C did in fact specify the bit-layout of integer types, then
there could not be both "big-endian" and "little-endian"
conformant C implementations: if the bit-layout was specified by C,
only one layout would be valid.
--
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth

Eric Sosman
Guest
Posts: n/a

 01-14-2008
Tomás Ó hÉilidhe wrote:
> dspfun:
>
>> C doesn't specify the bit-layout in memory of the different types, so
>> how are the operations ( & | ~ ^ << >>) defined to modify the objects
>> (which does not have its bit-layout defined) ?

>
>
> C *does* in fact specify the bit-layout of integer types. It doesn't do
> so in plain English, but it is inferred from other statements (such as
> the fact that shifting to the left is the same as multiplying by powers
> of two). [...]

No. I've used this "thought experiment" before, but maybe
it's time to trot it out again: Tomás, I have built a computer
two-state parts. Internally, therefore, numbers in my computer
are represented in base 4. Questions:

1) Since the "4's bit" and the "8's bit" both inhabit the
"4's quit," which is to the left of the other?

2) Propose a C program to demonstrate that I am lying
about using four-state parts, and am in fact using plain old
two-state components like everybody else.

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

Robert Latest
Guest
Posts: n/a

 01-14-2008
dspfun wrote:

> These operators yield values that depend on the internal
> representations of [unsigned] integers

Question is: Is --for instance-- (x << 2) == (x * 2) guaranteed? I thought
so.

robert

Philip Potter
Guest
Posts: n/a

 01-14-2008
Robert Latest wrote:
> dspfun wrote:
>
>> These operators yield values that depend on the internal
>> representations of [unsigned] integers

>
> Question is: Is --for instance-- (x << 2) == (x * 2) guaranteed? I thought
> so.

Assuming you meant (x<<1) == (x*2),

Consider the case x of type signed char, sign-magnitude representation
and x==-1, and 8-bit chars.

sign magnitude
-1 : 1 0000001 == -1
-1*2 : 1 0000010 == -2
-1<<1: 0 0000010 == 2

Of course, n1256 6.5.7p4 states that negative numbers shifted left cause
undefined behaviour, so -1 << 1 could yield any value, or even crash

I believe that if you add the following conditions:
* x is nonnegative
* x is of integer type
* x*2 falls within the defined range of x's type

then (x<<1) == (x*2) is guaranteed to be true.

But the compiler knows this anyway, so you don't gain anything by using
x<<1 when you should have used x*2 for clarity.

Philip Potter
Guest
Posts: n/a

 01-14-2008
Walter Roberson wrote:
> In article <Xns9A255E792E66toelavabitcom@194.125.133.14>,
> =?iso-8859-1?q?Tom=E1s_=D3_h=C9ilidhe?= <(E-Mail Removed)> wrote:
>> dspfun:

>
>>> C doesn't specify the bit-layout in memory of the different types, so
>>> how are the operations ( & | ~ ^ << >>) defined to modify the objects
>>> (which does not have its bit-layout defined) ?

>
>> C *does* in fact specify the bit-layout of integer types. It doesn't do
>> so in plain English, but it is inferred from other statements (such as
>> the fact that shifting to the left is the same as multiplying by powers
>> of two).

>
> Those operations are -defined- by their result on *values*, not by
> bit representation. If I recall correctly, ~ is the only operation
> defined in terms of bits rather than in terms of values.
>
> Because the operations are defined in terms of values, it doesn't
> matter to C what the bit ordering is in memory. For example, it
> does not say whether in a two-octet integeral type whether the
> internal order is AAAAAAAABBBBBBBB or BBBBBBBBAAAAAAAA or
> perhaps something else completely.
>
> If C did in fact specify the bit-layout of integer types, then
> there could not be both "big-endian" and "little-endian"
> conformant C implementations: if the bit-layout was specified by C,
> only one layout would be valid.

I disagree; C defines that certain bits have certain values, and this is
what we mean by "bit layout". We write them down in a canonical way:
sign bit, then MSB to LSB, in order from left to right, but there is no
guarantee they are stored in the machine this way. This doesn't matter.

In a little-endian system, a 16-bit short represented in a hex-editor as
ff 00 has the binary value 0000000011111111. The fact that its bytes are
conventionally written down in a different order to the bits don't faze
me; the bytes are written in order of address, while bits are written in
order of significance. Each convention is, in some sense, correct.

In fact, for the bitwise operators ~ & | ^ the order is irrelevant since
each bit's resultant value is dependent only on the corresponding bit in
the operand(s) and not on any other bit. For E1 << E2 and E1 >> E2, when
their behaviour is defined, it is exactly equivalent to shifting the E1
left or right by E2 bits, provided that E1 is written using the above
canonical bit representation.

IOW, I believe the definition of >> in terms of arithmetic defines the
bit-layout, and I have no problem with this disagreeing with the byte
layout. After all, byte layout is only of concern to the memory, while
bit layout is only of concern to the processor.

Phil

Philip Potter
Guest
Posts: n/a

 01-14-2008
Eric Sosman wrote:
> Tomás Ó hÉilidhe wrote:
>> dspfun:
>>
>>> C doesn't specify the bit-layout in memory of the different types, so
>>> how are the operations ( & | ~ ^ << >>) defined to modify the objects
>>> (which does not have its bit-layout defined) ?

>>
>> C *does* in fact specify the bit-layout of integer types. It doesn't do
>> so in plain English, but it is inferred from other statements (such as
>> the fact that shifting to the left is the same as multiplying by powers
>> of two). [...]

>
> No. I've used this "thought experiment" before, but maybe
> it's time to trot it out again: Tomás, I have built a computer
> two-state parts. Internally, therefore, numbers in my computer
> are represented in base 4. Questions:
>
> 1) Since the "4's bit" and the "8's bit" both inhabit the
> "4's quit," which is to the left of the other?
>
> 2) Propose a C program to demonstrate that I am lying
> about using four-state parts, and am in fact using plain old
> two-state components like everybody else.

You are quite correct, though to be a valid C implementation your
quit-based machine would have to emulate the bitwise operators in the
same way as if they operated on a bit-based machine.

My view (already expressed elsethread in response to Walter) is that you
can think of C as specifying a bit-layout in its abstract machine, and
although implmementations are free to use any techniques that produce
the same result, your mental model will still be appropriate and produce
correct reasoning.

Perhaps I am too strong to state that C does define a bit-layout;
rather, that it allows one to assume that integers are in a particular
bit-layout in order to reason about programs.

(The fact that << and >> do not always have defined behaviour vexes my
argument somewhat, though. When they are defined, it's perfectly fine to
reason about them in terms of bit-shifting within a standard bit-layout
rather than in terms of arithmetic; but you still need to remember when
their behaviour is defined, which is defined in terms of arithmetic

Phil