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,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
7)))

 

[Mike Wahler]

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

 

[Kenneth Brody]

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.

 

[Michael Mair]

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

 

[Dave Hansen]

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

 

[Douglas A. Gwyn]

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

 

[Felipe Magno de Almeida]

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
(e-mail address removed) - 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)

 

[Derrick Coetzee]

#define SetBits(bits,pos) (((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,pos) (((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(unsigned 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(unsigned 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);
}

 

[Keith Thompson]

#define SetBits(bits,pos) (((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,pos) (((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(unsigned 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( ...

[...]

 

[Douglas A. Gwyn]

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

Actually they aren't necessary restrictions.

 

[Douglas A. Gwyn]

Since the purpose of SetBits is bit manipulation, ">> 3" and
"& 7" are actually clearer than "/ 8" and "% 8", in my opinion.

The 1 << part is the bit, the / 8 part is address computation.

 

[Kalle Olavi Niemitalo]

Since the purpose of SetBits is bit manipulation, ">> 3" and "& 7" are
actually clearer than "/ 8" and "% 8", in my opinion.

Not so in mine. The macro is meant to manipulate the bits in the
array, not necessarily those in the index number. If one wanted
to change the macro to store 16 bits per element, I think
changing /8 to /16 and %8 to %16 would be easier to get right
than changing >>3 to >>4 and &7 to &15. And with CHAR_BIT bits
per element, the shifts just wouldn't work.

I also dislike the SetBits name as the macro (or inline function)
sets only one bit at a time.

 

[Mike Cowlishaw]

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

[snip]

However, one has to do the manual optimization if compilers won't
do it. If you buy a Microsoft C++/C compiler today, standard
version, all optimizations are turned off (and cannot be turned on).
So these 'tricks', unfortunately, still have value.

mfc

 

[Keith Thompson]

The 1 << part is the bit, the / 8 part is address computation.

You're right; I wasn't paying quite enough attention. There's also no
inherent reason why the number of bits per array element has to be a
power of 2.

 

[Charlie Gordon]

#define SetBits(bits,pos) (((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,pos) (((bits)[(pos) / 8]) |= (1 << ((pos) % 8)))

This is not correct : shifting right 3 bits and dividing by 8 are not
necessarily equivalent : because C99 doesn't preclude binary arithmetic (a
pedantic argument, with no real modern examples) and more importantly
because they produce different results for negative numbers !

-1 >> 3 is -1
-1 / 8 is 0
-1 & 7 is 7
-1 % 8 is -1

Of course this macro should only be used with positive numbers, but if the
pos argument is a signed int variable expression, the compiler cannot assume
its value to be positive, and will generate division code far less efficient
than the shift. The same applies to the remainder expression. You have to
cast (pos) to (unsigned) to avoid this:

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

There is another issue with this macro: it evaluates pos twice. This will
result in inefficient code generation at best and hard to find bugs when the
pos expression has side effects. Using an inline function is definitely a
better solution. SetBits is of course a poor name since only one bit gets
set.

Cheers,

Chqrlie.

C aint for CCs

 

[Derrick Coetzee]

inline SetBits(unsigned 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( ...

Oops, yes it should. Thanks. This is why I should compile my snippets
before posting them...

 

[Francis Glassborow]

This is not correct : shifting right 3 bits and dividing by 8 are not
necessarily equivalent : because C99 doesn't preclude binary arithmetic (a
pedantic argument, with no real modern examples) and more importantly
because they produce different results for negative numbers !

Yep, and bitwise operators should not be applied to signed integers,
doing so is a recipe for trouble.

 

[Richard Bos]

#define SetBits(bits,pos) (((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,pos) (((bits)[(pos) / 8]) |= (1 << ((pos) % 8)))

This is not correct : shifting right 3 bits and dividing by 8 are not
necessarily equivalent : because C99 doesn't preclude binary arithmetic (a

^^^^^^^^
I don't think that word means what you think it means.

pedantic argument, with no real modern examples) and more importantly
because they produce different results for negative numbers !

_May_ produce different results. Right-shifting negative integers has
implementation-defined results; it may be defined as being equal to
division.

-1 >> 3 is -1

You do not know this.

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

There is another issue with this macro: it evaluates pos twice. This will
result in inefficient code generation at best

Buy an optimising compiler, then.

Richard

 

[CBFalconer]

..... snip ...

This is not correct : shifting right 3 bits and dividing by 8 are
not necessarily equivalent : because C99 doesn't preclude binary
arithmetic (a pedantic argument, with no real modern examples)
and more importantly because they produce different results for
negative numbers !

That is not strong enough. In general, shift operations on
negative numbers are implementation defined, and should not be
used. They should be reserved purely for unsigned quantities.