Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Bit shifts and endianness

Reply
Thread Tools

Bit shifts and endianness

 
 
Eric Sosman
Guest
Posts: n/a
 
      01-06-2006
Richard Heathfield wrote:
> http://www.velocityreviews.com/forums/(E-Mail Removed) said:
>
>
>>0xabff >> 8 always gives me 0x00ab regardless of weather

>
>
> Even so, I don't recommend that you try this in the rain.


.... lest the negative sign give you a positive charge ...

--
Eric Sosman
(E-Mail Removed)lid

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      01-06-2006
Jordan Abel wrote:

> On 2006-01-05, Richard Heathfield <(E-Mail Removed)> wrote:
>
>>Mark McIntyre said:
>>
>>
>>>On Thu, 05 Jan 2006 20:26:11 GMT, in comp.lang.c , Keith Thompson
>>><(E-Mail Removed)> wrote:
>>>
>>>
>>>>No. Shift operators are defined on the *values* of their operands,
>>>>not on their representations.
>>>
>>>Clarification: I assume you mean that shift operators operate on a
>>>binary value,

>>
>>No, they operate on a value. Values don't have number bases. That's merely a
>>representation issue.

>
>
> The standard mentions "bits" in too many places for me to believe this.


Yeah. And there's also the requirement for a "pure binary"
representation. Nonetheless, I stick with the Heathfield Maxim:
operators operate on values, not on representations. When the
Standard describes ^ or >> in terms of bits, it does so merely
as a convenience, as an appeal to the readers' understanding of
binary arithmetic. Nowhere (that I can see) is there a requirement
that the arithmetic actually be carried out bit-by-bit or even
bits-in-parallel; it's just easier for the Standard to describe
`x & 17' by referring to binary digits than by avoiding such a
reference. (Quick: Describe `x & 17' without reference to bits.
It can surely be done, but I expect the description would be
verbose and opaque even by the standards of Standardese.)

Let's put it this way: Imagine a machine with two "banks"
of memory, whose stoned-out-of-their-gourds designers have
decided should have different endiannesses. If `x' is in the
BigEndian bank and `y' in the LittleEndian, what is the effect
of `x = 1; y = x << 1;'? I claim that the effect must be the
same as `x = 1; y = 2;', or else the implementation is broken.
The fact that the representations differ just doesn't matter.

--
Eric Sosman
(E-Mail Removed)lid
 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      01-06-2006
Jordan Abel <(E-Mail Removed)> writes:
> On 2006-01-05, Richard Heathfield <(E-Mail Removed)> wrote:
>> Mark McIntyre said:
>>
>>> On Thu, 05 Jan 2006 20:26:11 GMT, in comp.lang.c , Keith Thompson
>>> <(E-Mail Removed)> wrote:
>>>
>>>>No. Shift operators are defined on the *values* of their operands,
>>>>not on their representations.
>>>
>>> Clarification: I assume you mean that shift operators operate on a
>>> binary value,

>>
>> No, they operate on a value. Values don't have number bases. That's
>> merely a representation issue.

>
> The standard mentions "bits" in too many places for me to believe this.


The standard imposes some fairly stringent requirements on how
integer, both signed and unsigned, are represented. These
requirements are tight enough to guarantee (I think) that the
"multiple or divide by powers of 2" and "shift by N bits" models of
the "<<" and ">>" operators turn out to be equivalent (with the
proviso that any padding bits don't participate).

Once could imagine a hypothetical C standard that doesn't place any
requirements on the representations of integers, but that defines "<<"
and ">>" in much the same way as the actual standard does. An
implementation conforming to this hypothetical standard could use,
say, a trinary hardware representation for integers, but would still
have to implement "<<" and ">>" so they yield the same results as on a
binary machine. (In fact, such an implementation would probably be
legal under the actual C standard as long as it does a sufficiently
good job of hiding the trinary hardware behind a binary-looking
interface.)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-06-2006
Keith Thompson <(E-Mail Removed)> writes:
[...]
> The standard imposes some fairly stringent requirements on how
> integer, both signed and unsigned, are represented. These
> requirements are tight enough to guarantee (I think) that the
> "multiple or divide by powers of 2" and "shift by N bits" models of
> the "<<" and ">>" operators turn out to be equivalent (with the
> proviso that any padding bits don't participate).


Since not everyone has a copy of the standard, here's what C99 says in
its description of the bitwise shift operators. (I've replaced the
multiplication symbol 'x' with "*", and the superscript exponent with
a "**" operator.)

The integer promotions are performed on each of the operands. The
type of the result is that of the promoted left operand. If the
value of the right operand is negative or is greater than or equal
to the width of the promoted left operand, the behavior is
undefined.

The result of E1 << E2 is E1 left-shifted E2 bit positions;
vacated bits are filled with zeros. If E1 has an unsigned type,
the value of the result is E1 * 2**E2, reduced modulo one more
than the maximum value representable in the result type. If E1 has
a signed type and nonnegative value, and E1 * 2**E2 is
representable in the result type, then that is the resulting
value; otherwise, the behavior is undefined.

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.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-06-2006
Eric Sosman <(E-Mail Removed)> writes:
[...]
> Yeah. And there's also the requirement for a "pure binary"
> representation. Nonetheless, I stick with the Heathfield Maxim:
> operators operate on values, not on representations. When the
> Standard describes ^ or >> in terms of bits, it does so merely
> as a convenience, as an appeal to the readers' understanding of
> binary arithmetic. Nowhere (that I can see) is there a requirement
> that the arithmetic actually be carried out bit-by-bit or even
> bits-in-parallel; it's just easier for the Standard to describe
> `x & 17' by referring to binary digits than by avoiding such a
> reference. (Quick: Describe `x & 17' without reference to bits.
> It can surely be done, but I expect the description would be
> verbose and opaque even by the standards of Standardese.)


I wouldn't try to describe x & 17 without reference to bits. Rather,
I'd define "bits" in terms of the arithmetic properties of the number,
and *then* define x & 17 in terms of the "bits" I've defined.
Something along the lines of:

An integer value in the range 0..2**(n-1) can be uniquely defined
as a sum of powers of two: ... + b3 * 2**3 + b2 * 2**2 + b1 * 2**1
+ b0 * 2**0. Each bn value is referred to as the nth _bit_ of the
integer value.

With this definition, it becomes irrelevant whether these "bits"
correspond to some on-off state in hardware somewhere; the description
applies equally well to numbers represented in decimal or trinary.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      01-06-2006
Keith Thompson wrote:
> Eric Sosman <(E-Mail Removed)> writes:
>> [...] (Quick: Describe `x & 17' without reference to bits.
>>It can surely be done, but I expect the description would be
>>verbose and opaque even by the standards of Standardese.)

>
>
> I wouldn't try to describe x & 17 without reference to bits. Rather,
> I'd define "bits" in terms of the arithmetic properties of the number,
> and *then* define x & 17 in terms of the "bits" I've defined.
> Something along the lines of:
>
> An integer value in the range 0..2**(n-1) can be uniquely defined
> as a sum of powers of two: ... + b3 * 2**3 + b2 * 2**2 + b1 * 2**1
> + b0 * 2**0. Each bn value is referred to as the nth _bit_ of the
> integer value.
>
> With this definition, it becomes irrelevant whether these "bits"
> correspond to some on-off state in hardware somewhere; the description
> applies equally well to numbers represented in decimal or trinary.


Right, and that's the point: C's operators[*] are defined
in terms of the values of the operands and the value of the
result. They are not defined in terms of the representations
of those values, but in terms of the values themselves, however
represented.
[*] "Ordinary" operators, anyhow. Special operators like
`.' don't fit well with this way of understanding -- but not
even these oddballs work with the representations of their
operands.

As a concrete example of a situation where values are
represented without any individual "bit-artifacts" being
present, consider the data stream between two modems. If I
understand correctly (I'm not a modem maven), each change in
the signal encodes an entire group of bits: one phase shift
represents 000, another phase shift represents 010, and so
on. "Value bits" are transmitted, but no isolated "signal
bits" are discernible.

--
Eric Sosman
(E-Mail Removed)lid
 
Reply With Quote
 
Jordan Abel
Guest
Posts: n/a
 
      01-06-2006
On 2006-01-06, Eric Sosman <(E-Mail Removed)> wrote:
> Keith Thompson wrote:
>> Eric Sosman <(E-Mail Removed)> writes:
>>> [...] (Quick: Describe `x & 17' without reference to bits.
>>>It can surely be done, but I expect the description would be
>>>verbose and opaque even by the standards of Standardese.)

>>
>>
>> I wouldn't try to describe x & 17 without reference to bits. Rather,
>> I'd define "bits" in terms of the arithmetic properties of the number,
>> and *then* define x & 17 in terms of the "bits" I've defined.
>> Something along the lines of:
>>
>> An integer value in the range 0..2**(n-1) can be uniquely defined
>> as a sum of powers of two: ... + b3 * 2**3 + b2 * 2**2 + b1 * 2**1
>> + b0 * 2**0. Each bn value is referred to as the nth _bit_ of the
>> integer value.
>>
>> With this definition, it becomes irrelevant whether these "bits"
>> correspond to some on-off state in hardware somewhere; the description
>> applies equally well to numbers represented in decimal or trinary.

>
> Right, and that's the point: C's operators[*] are defined
> in terms of the values of the operands and the value of the
> result. They are not defined in terms of the representations of
> those values, but in terms of the values themselves, however
> represented.
>
>[*] "Ordinary" operators, anyhow. Special operators like
> `.' don't fit well with this way of understanding -- but not even
> these oddballs work with the representations of their operands.
>
> As a concrete example of a situation where values are
> represented without any individual "bit-artifacts" being present,
> consider the data stream between two modems. If I understand
> correctly (I'm not a modem maven), each change in the signal
> encodes an entire group of bits: one phase shift represents 000,
> another phase shift represents 010, and so on. "Value bits" are
> transmitted, but no isolated "signal bits" are discernible.


That doesn't mean it's not a "binary value" - which, if you were
paying attention, is the claim you are attempting to refute.
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      01-06-2006
Jordan Abel wrote:
>
> That doesn't mean it's not a "binary value" - which, if you were
> paying attention, is the claim you are attempting to refute.


Thank you, Jordan, for drawing my attention to my
inattention. Tracing back the thread, though, I find
this remark from Mark McIntyre:

> No, they operate on a value. Values don't have number bases.
> That's merely a representation issue.


.... to which you responded:

> The standard mentions "bits" in too many places for me to
> believe this.


McIntyre says the shift operators work on values, not
representations, and you say you don't believe him. That's
what I'm trying to refute: I add my voice to the McIntyre
(and Heathfield) chorus to say that you are mistaken.

But perhaps the "this" in your response referred to
something else altogether?

--
Eric Sosman
(E-Mail Removed)lid
 
Reply With Quote
 
Walter Roberson
Guest
Posts: n/a
 
      01-06-2006
In article <(E-Mail Removed)>,
Eric Sosman <(E-Mail Removed)> wrote:
> As a concrete example of a situation where values are
>represented without any individual "bit-artifacts" being
>present, consider the data stream between two modems. If I
>understand correctly (I'm not a modem maven), each change in
>the signal encodes an entire group of bits: one phase shift
>represents 000, another phase shift represents 010, and so
>on. "Value bits" are transmitted, but no isolated "signal
>bits" are discernible.


There are a number of different encoding mechanisms used for
modems designed for use with telephone lines (the term 'modem'
applies to a number of other situations as well.) The first standards,
for 110 and 300 baud, were straight single-frequency carriers with
no phase encoding. 1200 baud was, if I recall correctly, dual frequency
but not phase encoded. All of the CCITT standard encodings from 2400 baud
upwards rely upon phase encoding. The proprietary Telebit protocols
worked rather differently (128 or 256 frequency channels but
individual signals were held for long periods.)

It is not exactly accurate to say that -each- change in the signal
encodes a group of bits; rather, the signal is sampled at several
intervals along the cycle, and the details of the "phase breaking"
that is imposed on the base sine wave over that interval encodes
a cluster of bits in a completely non-linear non-binary manner
[i.e., there is no single aspect of the phase changes that encodes
any one particular bit.]

Especially for the higher speeds, extra "logical" bits are encoded into
the signal, and the decoded group of bits is run through a
"constellation" corrector to find the most probable original bit group.
In theory the constellation corrector could map to a bit grouping that
had no obvious resemblance to the bits read off of the signal -- with
the non-linear encoding of bits and taking into account the need for
some slosh while the signal slews, the constellation correction could
decide that one should have chosen a different non-linear decoding.


Another example of non-binary encoding is gigabit ethernet, which
starts with the signaling mechanisms used for 100 megabit ethernet,
raised the carrier frequency from 100 megahertz to 125 megahertz,
but then does phase encoding and constellation correction that extracts
10 databits from each 16 signal values decoded out of the wave.
--
"law -- it's a commodity"
-- Andrew Ryan (The Globe and Mail, 2005/11/26)
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      01-06-2006
Eric Sosman said:

> Jordan Abel wrote:
>>
>> That doesn't mean it's not a "binary value" - which, if you were
>> paying attention, is the claim you are attempting to refute.

>
> Thank you, Jordan, for drawing my attention to my
> inattention. Tracing back the thread, though, I find
> this remark from Mark McIntyre:
>
> > No, they operate on a value. Values don't have number bases.
> > That's merely a representation issue.


No, those are my words, not Mark's.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Be cautious when iterating bit-shifts geo C Programming 4 11-21-2009 03:43 PM
bit shifts across array elements fermineutron C Programming 6 11-06-2006 02:53 AM
endianness and 64-bit machines bob_jenkins@burtleburtle.net C Programming 7 05-20-2006 01:46 PM
Variadic functions calling variadic functions with the argument list, HLL bit shifts on LE processors Ross A. Finlayson C Programming 19 03-10-2005 03:57 AM
python and bit shifts and byte order, oh my! Reid Nichol Python 11 09-11-2004 09:08 AM



Advertisments