From: martelli@cadlab.sublink.org (Alex Martelli)
Newsgroups: comp.lang.c,comp.edu
Subject: Re: Help needed with C Bitwise Exercises.
Date: 11 Nov 92 11:05:07 GMT
Organization: CAD.LAB S.p.A., Bologna, Italia

hauben@cunixf.cc.columbia.edu (Michael Hauben) writes:
	...
:	I have two problems for my C Programming Language class
:that I am not quite sure how to approach. This C class has been
:frustrating because much of the problems (less so these) have
:been particularly obscure, and the actual class hasn't helped in
:figuring the exercise out. The Problems are as follows:

Many consider it bad form to use the net for class assignments,
but I believe in this case you're going about it the right way:
i.e., being upfront about it and asking for approaches on how
to THINK about the problems, rather than for somebody else to
do them for you.  So...:

:1) Write a function that will reverse the bit representation of
:an int. Here are two examples if a reversing operation defined
:for a char instead of an int:
:
:	01110101 reversed yields  10101110
:	10101111 reversed yields  11110101
:
:and 
:
:2) Write a function that will extract every other bit position
:from a 32-bit expression. The result should be returned as a
:16-bit expression. Your function should work on machines having
:either 2- or 4-byte words.
:
:	I would greatly appreciate any help in how to approach
:these problems.

*ABSTRACT* - that's the keyword.  If, instead of being about
integers as bitstrings, the same problems were about "arrays
of bits", wouldn't it be easier to see your way to a solution?
I.e. 1) becomes "write an array the same as another but
reversed", 2) becomes "write an array having every other element
from another one twice as long" (say all those with even index
0 upwards).  I believe you can solve these; sketch a solution,
BUT, do NOT use 'array[index]' to read the index-th element or
'array[index]=value' to write it; instead, ABSTRACT them into
macros:

#define GETELEM(array,index)       (array)[index]
#define PUTELEM(array,index,value) ((array)[index]=(value))

Write a solution using these macros, and a simple program to
test your solution function.  Also keep the array lengths
symbolic via #define - remember, you must ABSTRACT!  You
cannot "return an array from a function" in C so for this
stage you will have to build the array to be returned as a
local static array of your solution-function, and return
the address of this local static array (receiving it into
a pointer) - a minor stumbling block though.

NOW - you ALMOST have your solution, except that now you know
you aren't using arrays, but "bitstrings" which are really
unsigned integers (possibly long or short ones, for the
16-bit and 32-bit specs).  So think back to these macros which
extract or place an "element" into an "array".  Do you know
how to extract one bit from an integer?  Hints: bitwise
operations, shifting the constant "1" appropriately, testing
against zero... do you know how to PLACE one bit in an
integer?  Hints: set-to-1 is easy if you have the "extract"
thingy above right; set-to-0's hints are "&" and "~"...

You should now have enough hints to implement and test.
The solution you obtain this way will NOT be optimized.  Must
you optimize?  In this case, think about whether there is a
better overall way to extract all bits from an integer, one
after another in a given order, and, similarly, to set all
bits in an integer, possibly in a different order.  Hints:
the shift operator is your friend, and it comes in two
directions...
-- 
Email: martelli@cadlab.sublink.org                   Phone: ++39 (51) 6130360
CAD.LAB s.p.a., v. Ronzani 7/29, Casalecchio, Italia   Fax: ++39 (51) 6130294 
Newsgroups: comp.lang.c