C - Need help on bit operations define

Author

Need help on bit operations define

MakisGR

2004-08-26, 8:55 pm

I'm having trouble understanding what the following define does. Can
anyone provide some assistance?

#define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
7)))
--
comp.lang.c.moderated - moderation address: clcm@plethora.net

Mike Wahler

2004-08-26, 8:55 pm

"MakisGR" <beloved27@hotmail.com> wrote in message
news:clcm-20040826-0022@plethora.net...
> I'm having trouble understanding what the following define does. Can
> anyone provide some assistance?
>
> #define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
> 7)))

1) It assumes that the passed argument 'bits' is a pointer or an array.

2) It assumes that 'pos' is of a type suitable for use as an array
index or pointer arithmetic (e.g. size_t).

3) Evaluates the object at address 'bits + (pos / 8)' [*1]

4) Bitwise ANDs [*2] 'pos' with 7 (which will set bits from bit 2 [*3]
through the highest order bit, to zero)

4) Calculates 2 to the power of the value from 4)

5) Bitwise ORs [*4] the two values from 3) and 4), and stores the
result in 'bits[pos / 8]'

[1] Shifting binary value one digit to the right divides it by two,
shifting left multiplies by two. So 'pos >> 3' is the same
as 'pos / 2^3', and 'pos / 8'. Some folks use shifting instead
of multiply and divide in the interest of 'optimization', but
with today's modern optimizing compilers, such 'cleverness'
is not typically necessary, and in some cases detrimental.

[2]
Bitwise AND:
Compares two operands bit by bit.

If both corresponding bits from each operand are one,
the result is 1 (for that bit). If either or both are
zero, the result is zero (for that bit).

AND 0 1
-----------
0 0 | 0
-----------
1 0 | 1

[3] Using the lowest order bit as 'bit zero'

[4]
Bitwise OR:
Compares two operands bit by bit.

If either (or both) of corresponding bits from each operand is one,
the result is 1 (for that bit). If both are zero, the result is
zero (for that bit).

OR 0 1
-----------
0 0 | 1
-----------
1 1 | 1

HTH,
-Mike

Kenneth Brody

2004-08-30, 3:55 am

MakisGR wrote:
>
> I'm having trouble understanding what the following define does. Can
> anyone provide some assistance?
>
> #define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) & 7)))

The "(pos) >> 3" is a quick divide-by-8.

The "(1 << ((pos) & 7))" references bit (pos)-modulo-8. In other words,
0 ==> 00000001
1 ==> 00000010
2 ==> 00000100
3 ==> 00001000
4 ==> 00010000
5 ==> 00100000
6 ==> 01000000
7 ==> 10000000

Assuming that (bits) is an array of 8-or-more-bit chars, used to hold 8*n
bits, it will set (that's the "|=" part) bit "pos" in the array.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
--
comp.lang.c.moderated - moderation address: clcm@plethora.net

Michael Mair

2004-08-30, 3:55 am

Hi there,

F'Up to comp.lang.c

> #define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
> 7)))

do not introduce linebreaks in macros; better:

#define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= \
(1 << ((pos) & 7)))

or

#define SetBits(bits,pos) \
(((bits)[(pos) >> 3]) |= (1 << ((pos) & 7)))

Let's "parse" it:
There is an assignment |=, i.e. we could also write

(((bits)[(pos) >> 3]) = ((bits)[(pos) >> 3]) | (1 << ((pos) & 7)))

Now, what does ((bits)[(pos) >> 3]) mean?
We can assume that (bits) is a pointer to a certain object
It is the object at the address
address of (bits) plus ( (pos)>>3 times the size of the object (bits)
points to )

(pos)>>3 means "take the binary representation of (pos) and shift it by
three to the right (i.e. throw away the last three binary digits and
fill three digits from the left).
(pos) must be of an unsigned type.
The lowest three bits of (pos) are not used here.

Right side of |:
(1<< ((pos) & 7) )
Take one in binary, that is still one and shift it to the left by
(pos) & 7, i.e. append (pos) & 7 zeros at the right and throw away
(pos) & 7 digits from the left.
(pos) & 7 means "set to zero all bits of (pos) for which the
corresponding bits of 7(decimal) are zero. 7(decimal) is 111(binary),
so we essentially consider only the lowest three bits of (pos) which
went unused before. That means we can shift left between 0 and 7 digits.

Let us assume that (bits) was a pointer to an array of unsigned chars
which consist of 8 bits and (pos) was an unsigned int, then we could
directly "address" an arbitrary bit. If (pos) = n, where n=8*i+j,
0<=j<8, then SetBits(bits,pos) sets the n'th bit, that is, the
j'th bit of the i'th byte from the start to be one.

So, you essentially can interpret (bits) as a binary number of arbitrary
length for which you can set an arbitrary digit to 1 by using
SetBits. This means you can save factor 8 compared with using
every element of your array as a binary digit. Then, you would
use (bits)[(pos)]=1 instead of SetBits(bits,pos).

If you have problems with the binary operators, we can eliminate some
of them:

#define SetBits(bits,pos) (((bits)[(pos)/8]) |=\
(1 << ((pos)%8)))

If CHAR_BIT is not 8, and you mainly want to have the maximum memory
save, then replace 8 by CHAR_BIT:

#define SetBits(bits,pos) (((bits)[(pos)/CHAR_BIT]) |=\
(1 << ((pos)%CHAR_BIT)))

By the way: You are only setting one bit here, so SetBit would
be a better name for the macro.

Cheers,
Michael
--
comp.lang.c.moderated - moderation address: clcm@plethora.net

Dave Hansen

2004-08-30, 3:55 am

On 26 Aug 2004 19:43:40 GMT, beloved27@hotmail.com (MakisGR) wrote:

>I'm having trouble understanding what the following define does. Can
>anyone provide some assistance?
>
>#define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
>7)))

Work it from the outside in.

At the highest level, the macro expands into "LHS |= RHS". Thus, the
macro causes one or more bits (defined by the mask on the RHS) to be
set in the LHS. Not surprising, given the name of the macro...

The RHS looks like "1 << SHIFT". So the mask is generated by taking a
1 and shifting it left by the appropriate amount. SHIFT is "(pos)&7".
So the amount shifted is found by taking only the least significant 3
bits of the parameter "pos". Obviously, this value will be between 0
and 7. If "pos" is positive, the result will be "(pos)%8".

The LHS looks like "PTR[IDX]". So we are accessing an array. PTR is
nothing more than the passed parameter "(bits)". Since the "|="
operator requires its operands have integer type, "bits" should be a
pointer to an object with such a type. IDX is "(pos)>>3". Shifting a
negative value is Not A Good Idea(TM), so the intent is for the user
to pass a positive value as "pos". If so, "(pos)>>3" will have the
same result as "(pos)/8".

So there you have it. The macro sets the bit (formed by shifting 1
left (pos)&7 times) in the object (presumably with integer type) found
by indexing the pointer "bits" with the value "(pos)>>3".

Without more information it's impossible to be certain. But consider
what happens if "bits" points to unsigned char, e.g.

unsigned char array[10];
SetBits(array,17);

Regards,

-=Dave
--
Change is inevitable, progress is not.
--
comp.lang.c.moderated - moderation address: clcm@plethora.net

Douglas A. Gwyn

2004-08-30, 3:55 am

MakisGR wrote:
> I'm having trouble understanding what the following define does. Can
> anyone provide some assistance?
> #define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
> 7)))

Break it down into simpler components:
(pos)&7 isolates the lowest three bits of the
index-position argument
1<<that creates a value with a single set-bit
at a bit-position from 0 through 7
(using little-endian bit ordering)
|=that makes the bit at that position in the
left-hand variable take on a set value
at the position just determined

(pos)>>3 in effect divides the index-position
argument by 8 (which is how many bits
will be used in each element of the
array specified by the first argument)
(bits)[that] accesses a member of the array
in which the bit computed on the
right-hand size of the |= will be accessed
So the net effect is that it sets a single bit in the
array object, using no more than the lowest 8 bits of
the value of eacy array member. It's a standard method
of implementing large bit arrays in C, which does not
directly support bit arrays in the language. There are
presumably companion functions such as GetBit(bits,pos).
--
comp.lang.c.moderated - moderation address: clcm@plethora.net

Felipe Magno de Almeida

2004-08-30, 3:55 am

MakisGR wrote:

> I'm having trouble understanding what the following define does. Can
> anyone provide some assistance?
>
> #define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
> 7)))
What it does is:
if 2^pos is less than 8, then sets bits[pos/8] with 2^pos, else
bits[pos/8] remains the same.

--
Felipe Magno de Almeida
Ciencia da Computacao - Unicamp
felipe.almeida@ic.unicamp.br - UIN: 2113442
Cause Rock and Roll can never die.
"if you want to learn something really well, teach it to a computer."
What is Communism?
Answer: "Communism is the doctrine of the conditions of the liberation
of the proletariat." (by Karl Marx)
--
comp.lang.c.moderated - moderation address: clcm@plethora.net

Sponsored Links