GetByte(int x, int n)

[Eric Sosman]

Now that everyone's had their fun with Floyd's discomfiture, and the thread
is starting to drift, I wanted to ask a *somewhat* similar question, in that
it involves bit manipulations. I do not, however, have a T.A.

In K&R2 §2.9 appears the following sentence: The bitwise OR operator | is
used to turn bits on:
x=x | SET_ON;
sets to one in x the bits that are set to one in SET_ON.

I've looked in the index and the usual header files, and I find nothing on
SET_ON. I am no longer subject to the admonition to read K&R sequentially,
as I am doing so presently and am past this point. MPJ

K&R Classic (I don't have the New Testament) uses the
identifier MASK instead of SET_ON. Neither identifier is
in any way "special" to C, and neither is predefined in a
header or elsewhere. If you want to set the low-order bit
you'd provide a SET_ON or MASK of 1. If you want to set
the three low-order bits you'd use 7:

Original x = 00101010 binary = 42
SET_ON = 00000111 binary = 7
Result = 00101111 binary = 47

Each bit in the final `x' is a one if it was already a one
or if SET_ON's corresponding bit is a one, or is a zero if
both `x' and SET_ON had a zero at that position. Another
(and equivalent) view is that each bit in the final `x' is
a one if SET_ON has a one at that position, or is unchanged
if SET_ON has a zero.

 

[Michael Mair]

Hi Dan,

Please have the minimal decency not to expose newbies to badly implemented
macros! Both x and u MUST be protected by parentheses in the expression.

Besides, you have chosen the worst algorithm.

Out of curiosity:
Which, do you think, is the _best_ algorithm for that?

Apart from the fact that I would not want to do this in a macro
in C99 and would not use parentheses so sparingly (macro or not),
I would rather shift and then mask in this case but I do not find
the above solution offending.


Cheers,
Michael

 

[Dave Vandervies]

Indeed, although this is my own alma mater we're talking about here...
I just felt the worth of my degree decrease just a tiny bit

I would think that seeing a TA catch a student looking for homework
solutions would have the opposite effect...


dave

--
Dave Vandervies (e-mail address removed)

Should anything be taken care of when printf format specifier string has
a ','(comma) in it?

Yes, the comma. It gets printed. --qazmlp and Dave Neary in comp.lang.c

 

[Randy Howard]

Using resources is one thing, asking for the answer to your HW question
straight out is another.

Yes, I keep up with this newsgroup.

Good for you. It's a pity this isn't done more widely. It would
really cut down on the number of homework questions asked here.

 

[Randy Howard]

[snip]

Why did you solve his homework for him?

Coudn't you read the other answers before throwing out
code like that???

*sigh*

 

[Jason Whitehurst]

Hmmm, the assignment needs better definition.

Well, had he posted the entire assignment, your questions would have been
answered. ;-)

 

[Jason Whitehurst]

Your homework assignment is unclear.

Well, had he posted the entire assignment, your questions would have been
answered. ;-)

 

[pete]

Merrill & Michele wrote:

In K&R2 §2.9 appears the following sentence:
The bitwise OR operator | is
used to turn bits on:
x=x | SET_ON;
sets to one in x the bits that are set to one in SET_ON.

I've looked in the index and the usual header files,
and I find nothing on SET_ON.

Their statement is true for all values of SET_ON, if you assume
that the width of SET_ON isn't greater than the width of x.

 

[pete]

Hi Dan,



Out of curiosity:
Which, do you think, is the _best_ algorithm for that?

Apart from the fact that I would not want to do this in a macro
in C99 and would not use parentheses so sparingly (macro or not),
I would rather shift and then mask in this case but I do not find
the above solution offending.

I agree with Dan about the parentheses around macro arguments.
As for the remaining sparsity of parentheses,
I'll admit that I had to look at page 53, to write that.
The algorithm that I chose was just the very first that popped
into my head. I need more practice doing other people's homework.

 

[Michael Mair]

I agree with Dan about the parentheses around macro arguments.
As for the remaining sparsity of parentheses,
I'll admit that I had to look at page 53, to write that.
The algorithm that I chose was just the very first that popped
into my head. I need more practice doing other people's homework.

*lol* Well, if you really need it, I can give you the more
interesting exercises I wanted my students to do in my C class...
Probably you will provide me with better solutions as my teaching
assistant and I came up with.

I really am just curious what Dan proposes as optimal solution
to the problem.


Cheers
Michael

 

[Dan Pop]

In K&R2 §2.9 appears the following sentence: The bitwise OR operator | is
used to turn bits on:
x=x | SET_ON;
sets to one in x the bits that are set to one in SET_ON.

I've looked in the index and the usual header files, and I find nothing on
SET_ON.

It's simply a place holder for a programmer-supplied value. The example
*implies* the existence of something like:

#define SET_ON 0xAA /* or whatever */

somewhere upcode.

Dan

 

[Dan Pop]

Hi Dan,




Out of curiosity:
Which, do you think, is the _best_ algorithm for that?

The one I have described upthread, *obviously* ;-)

Apart from the fact that I would not want to do this in a macro
in C99 and would not use parentheses so sparingly (macro or not),
I would rather shift and then mask in this case but I do not find
the above solution offending.

It is offending because it is a lot less readable than the solution
involving one shift and one masking. The correctness of the latter
can be trivially proven, while the above needs to be examined with a lot
more care. Compare:

(((x) & (UCHAR_MAX << (u) * CHAR_BIT)) >> (u) * CHAR_BIT)
(((x) >> (u) * CHAR_BIT) & UCHAR_MAX)

The complexity of an expression increases exponentially with the number
of *combined* shift operators it contains.

The apparent objection that the >> operator has implementation-defined
behaviour if its left operand is signed and negative is moot, because
the bits not well defined by the standard are masked away from the final
result.

Dan

 

[Nils Petter Vaskinn]

Well, had he posted the entire assignment, your questions would have been
answered. ;-)

Please post the complete assignment (once it's due date has come and gone
obviously)


--
Nils Petter Vaskinn (n + surname at broadpark dot no)

"They can sense totalitarianism approaching from a distance,
as animals can sense an approaching thunderstorm."
Paul Graham, about Hackers (http://paulgraham.com/gba.html)

 

[Michael Mair]

The one I have described upthread, *obviously* ;-)

Ouch, completely escaped me as you usually post concise
code Now that you say it, I find it. I am just not sure
whether I have forgotten it or whether it escaped me due to
my change of the news server... However, thanks for the reply.

It is offending because it is a lot less readable than the solution
involving one shift and one masking. The correctness of the latter
can be trivially proven, while the above needs to be examined with a lot
more care. Compare:

(((x) & (UCHAR_MAX << (u) * CHAR_BIT)) >> (u) * CHAR_BIT)
(((x) >> (u) * CHAR_BIT) & UCHAR_MAX)

The complexity of an expression increases exponentially with the number
of *combined* shift operators it contains.

The apparent objection that the >> operator has implementation-defined
behaviour if its left operand is signed and negative is moot, because
the bits not well defined by the standard are masked away from the final
result.

Thank you very much!
Now I am reassured; I was not sure whether some very obvious improvement
of the (u) * CHAR_BIT part completely escaped me...


Cheers
Michael

 

[CBFalconer]

.... snip ...

The apparent objection that the >> operator has implementation-
defined behaviour if its left operand is signed and negative is
moot, because the bits not well defined by the standard are
masked away from the final result.

Please point out where, in the standard, this segregation of bits
into classes is defined. A suitable implementation definition
would be "A right shift of a negative value results in zero".

 

[Dan Pop]

Please point out where, in the standard, this segregation of bits
into classes is defined. A suitable implementation definition
would be "A right shift of a negative value results in zero".

This is at odds with the actual definition of the right shift operator:

5 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.

The only thing the underlined text leaves up to the implementor to
define is the values of the bits filling the vacated bit positions.
They can be all ones or all zeroes (the only cases one will see in real
world implementations) or some arbitrary bit pattern defined by the
implementor. The bits coming from right-shifting E1 have all well
defined values.

Dan

 

[Mark Piffer]

Hi Dan,




Apart from the fact that I would not want to do this in a macro
in C99 and would not use parentheses so sparingly (macro or not),
I would rather shift and then mask in this case but I do not find
the above solution offending.

I could bet that the macro will invoke UB if sizeof long > sizeof int,
and also for invokations with u = sizeof int - 1 on most
implementations. But then again, I'm used to being totally wrong about
the simplest of C's rules, so it could be totally the other way
'round.

Mark

 

[Michael Mair]

I could bet that the macro will invoke UB if sizeof long > sizeof int,
and also for invokations with u = sizeof int - 1 on most
implementations. But then again, I'm used to being totally wrong about
the simplest of C's rules, so it could be totally the other way
'round.

Umh, are you referring to the given macro or the function/macro I was
describing?
The macro at hand will give you not more problems if
sizeof long > sizeof int.
What sizeof int - 1 has to do with it, I am not sure at all.

Let us, for a moment, assume that we do not use the macro for negative
x and have inserted the parentheses. UCHAR_MAX << u*CHAR_BIT will not
have overlapping non-zero bits with x if u >= sizeof x. As
UCHAR_MAX << u*CHAR_BIT is considered unsigned and a multiple of
exp2(u*CHAR_BIT), it is effectively 0 if we shift "out of" the largest
unsigned type. Now we consider the case u == sizeof x - 1.
What can go wrong? Assume CHAR_BIT==8, sizeof x==2, x=(T*2<<12) +
(U*2<<8) + (V*2<<4) + W, written symbolically as 0xTUVW:
0xff << 1*8 --> 0xff00
0xTUVW & 0xff00 --> 0xTU00
0xTU00 >> 1*8 -->0x$$TU. We assumed nonnegative x -->0xTU
If x was negative, we also could have non-zero nibbles instead
of the $ signs. However, this is only unspecified, not undefined.

Maybe you want to elaborate where you think the UB creeps in.


Cheers
Michael

 

[Eric Sosman]

This is at odds with the actual definition of the right shift operator:

5 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.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Not "the high-order bits of the resulting value," but
"the resulting value, period."

The only thing the underlined text leaves up to the implementor to
define is the values of the bits filling the vacated bit positions.
They can be all ones or all zeroes (the only cases one will see in real
world implementations) or some arbitrary bit pattern defined by the
implementor. The bits coming from right-shifting E1 have all well
defined values.

Well-defined, yes -- but by the implementation, not by
the Standard.

 

[Dan Pop]

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Not "the high-order bits of the resulting value," but
"the resulting value, period."


Well-defined, yes -- but by the implementation, not by
the Standard.

Wrong. You have no licence to ignore the first statement of the
paragraph, which is limiting the options of the implementor.

Dan