Need help on bit operations define
MakisGR
anyone provide some assistance?
#define SetBits(bits,pos) (((bits)[(pos) >> 3]) |= (1 << ((pos) &
7)))
--
comp.lang.c.moderated - moderation address: cl...@plethora.net
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.
--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Michael Mair
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
--
Change is inevitable, progress is not.
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
felipe....@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)
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);
}
--
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.
Keith Thompson
> MakisGR wrote:
> > #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( ...
[...]
--
Keith Thompson (The_Other_Keith) 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.
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
> MakisGR wrote:
>> #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.
>
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
> Keith Thompson wrote:
>> 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.
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.
--
Keith Thompson (The_Other_Keith) 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.
Charlie Gordon
news:clcm-2004...@plethora.net...
> MakisGR wrote:
> > #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...
--
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.
Francis Glassborow
<ne...@chqrlie.org> writes
>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.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Richard Bos
> "Derrick Coetzee" <dcn...@moonflare.com> wrote in message
> news:clcm-2004...@plethora.net...
> > MakisGR wrote:
> > > #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.
--
"This is a wonderful answer. It's off-topic, it's incorrect,
and it doesn't answer the question." -- Richard Heathfield
"I support the Red Sox and any team that beats the Yankees"