Need help on bit operations define

[MakisGR]

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

#define SetBits(bits,po s) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
7)))
--
comp.lang.c.mod erated - moderation address: cl**@plethora.n et

[Mike Wahler]

"MakisGR" <be*******@hotm ail.com> wrote in message
news:cl******** ********@pletho ra.net...

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

#define SetBits(bits,po s) (((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]

MakisGR wrote:

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

#define SetBits(bits,po s) (((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.mod erated - moderation address: cl**@plethora.n et

[Michael Mair]

Hi there,

F'Up to comp.lang.c

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

do not introduce linebreaks in macros; better:
#define SetBits(bits,po s) (((bits)[(pos) >> 3]) |= \
(1 << ((pos) & 7)))

or

#define SetBits(bits,po s) \
(((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,po s) 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,po s).

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

#define SetBits(bits,po s) (((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,po s) (((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.mod erated - moderation address: cl**@plethora.n et

[Dave Hansen]

On 26 Aug 2004 19:43:40 GMT, be*******@hotma il.com (MakisGR) wrote:

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

#define SetBits(bits,po s) (((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,1 7);

Regards,

-=Dave
--
Change is inevitable, progress is not.
--
comp.lang.c.mod erated - moderation address: cl**@plethora.n et

[Douglas A. Gwyn]

MakisGR wrote:

I'm having trouble understanding what the following define does. Can
anyone provide some assistance?
#define SetBits(bits,po s) (((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.mod erated - moderation address: cl**@plethora.n et

[Felipe Magno de Almeida]

MakisGR wrote:

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

#define SetBits(bits,po s) (((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
fe************@ 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.mod erated - moderation address: cl**@plethora.n et

[Derrick Coetzee]

MakisGR wrote:

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

This is a great example for observing the wonders of rewriting
prematurely optimized, obscure code into boring, obvious code.

To begin, the ">> 3" is just a division by 8, and the & 7 is likewise
being used to do a mod by 8. So let's be explicit:
#define SetBits(bits,po s) (((bits)[(pos) / 8]) |= (1 << ((pos) % 8)))

Next, use features of C99 (or C++, or GCC extensions) to rewrite it as
an inline function, eliminating all those extra parentheses:

inline SetBits(unsigne d char* bits, unsigned int pos) {
bits[pos / 8] |= 1 << (pos % 8);
}

The types add necessary restrictions that weren't there before. The
"unsigned" encourages the compiler to optimize it better. At this point
it should be pretty clear what the function is doing. If you want more
clarity, declare local variables for the partial results with
descriptive names, or add comments, like this:

inline SetBits(unsigne d char* bits, unsigned int pos) {
/* Sets a bit in bits, treated as an array of bits with the
indexes physically laid out in this order:
pos: 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 ... */
bits[pos / 8] |= 1 << (pos % 8);
}

--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.
--
comp.lang.c.mod erated - moderation address: cl**@plethora.n et

[Keith Thompson]

Derrick Coetzee <dc****@moonfla re.com> writes:

MakisGR wrote:

#define SetBits(bits,po s) (((bits)[(pos) >> 3]) |= (1 << ((pos) & 7)))
This is a great example for observing the wonders of rewriting
prematurely optimized, obscure code into boring, obvious code.

To begin, the ">> 3" is just a division by 8, and the & 7 is likewise
being used to do a mod by 8. So let's be explicit:
#define SetBits(bits,po s) (((bits)[(pos) / 8]) |= (1 << ((pos) % 8)))

Since the purpose of SetBits is bit manipulation, ">> 3" and "& 7" are
actually clearer than "/ 8" and "% 8", in my opinion.
Next, use features of C99 (or C++, or GCC extensions) to rewrite it as
an inline function, eliminating all those extra parentheses:

inline SetBits(unsigne d char* bits, unsigned int pos) {
bits[pos / 8] |= 1 << (pos % 8);
}

C99 doesn't allow implicit int (and you're not returning an int anyway).
The above should be:

inline void SetBits( ...

[...]

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <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.
--
comp.lang.c.mod erated - moderation address: cl**@plethora.n et

[Douglas A. Gwyn]

Derrick Coetzee wrote:

The types add necessary restrictions that weren't there before.

Actually they aren't necessary restrictions.
--
comp.lang.c.mod erated - moderation address: cl**@plethora.n et