P: n/a

I found some bit set macros somewhere that look roughly like the following;
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8]
#define bitset_mask(ptr,bit) (1 << (bit) % 8)
#define bitset_isset(ptr,bit) ((bitset_elem(ptr,bit) & bitset_mask(ptr,bit)) != 0)
#define bitset_set(ptr,bit) (bitset_elem(ptr,bit) = bitset_mask(ptr,bit))
#define bitset_unset(ptr,bit) (bitset_elem(ptr,bit) &= ~bitset_mask(ptr,bit))
#define bitset_toggle(ptr,bit) (bitset_elem(ptr,bit) ^= bitset_mask(ptr,bit))
Are these legal and can anyone recommend improvements?
Mike  
Share this Question
P: n/a

begin followup to Michael B Allen: I found some bit set macros somewhere that look roughly like the following;
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
One obvious issue is to use CHAR_BIT from limits.h instead of a hard
wired '8'.

Für Google, Tux und GPL!  
P: n/a

"Alexander Bartolich" <al*****************@gmx.at> wrote in message
news:bs************@ID193444.news.uniberlin.de... begin followup to Michael B Allen: I found some bit set macros somewhere that look roughly like the following;
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
One obvious issue is to use CHAR_BIT from limits.h instead of a hard wired '8'.
The other would be to use 1u instead of 1, to cater for systems where
UCHAR_MAX > INT_MAX.
But I'd actually have to question what type ptr is and why the author feels
the need for the (unsigned char *) cast.
[Personally, I think the standard could help in these situations by defining
UINT_BIT and ULONG_BIT etc... to indiciate the number of (sign+) value bits
in a given integer type, not just unsigned char.]

Peter  
P: n/a

On Wed, 31 Dec 2003 17:37:17 0500, Alexander Bartolich wrote: begin followup to Michael B Allen: I found some bit set macros somewhere that look roughly like the following;
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
One obvious issue is to use CHAR_BIT from limits.h instead of a hard wired '8'.
Not obvious to me. Isn't char guaranteed to be 8 bits?
Mike  
P: n/a

On Wed, 31 Dec 2003 20:15:50 0500, Peter Nilsson wrote: > I found some bit set macros somewhere that look roughly like the > following; > > #define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] > #define bitset_mask(ptr,bit) (1 << (bit) % 8)
<snip> But I'd actually have to question what type ptr is and why the author feels the need for the (unsigned char *) cast.
The type of 'ptr' can be a pointer to anything. For example it could be
an uint32_t * so that 32 bits can be tested with each iteration of
a loop when searching for the first free or used bit in a bit map.
Mike  
P: n/a

Michael B Allen wrote: On Wed, 31 Dec 2003 17:37:17 0500, Alexander Bartolich wrote:
begin followup to Michael B Allen:
I found some bit set macros somewhere that look roughly like the following;
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
One obvious issue is to use CHAR_BIT from limits.h instead of a hard wired '8'.
Not obvious to me. Isn't char guaranteed to be 8 bits?
Nope. Just at *least* 8 bits
HTH,
ag


Artie Gold  Austin, Texas  
P: n/a

"Michael B Allen" <mb*****@ioplex.com> wrote in message
news:pa*********************************@ioplex.co m... On Wed, 31 Dec 2003 20:15:50 0500, Peter Nilsson wrote: > I found some bit set macros somewhere that look roughly like the > following; > > #define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] > #define bitset_mask(ptr,bit) (1 << (bit) % 8)
<snip> But I'd actually have to question what type ptr is and why the author feels the need for the (unsigned char *) cast.
The type of 'ptr' can be a pointer to anything. For example it could be an uint32_t * so that 32 bits can be tested with each iteration of a loop when searching for the first free or used bit in a bit map.
That would introduce endian issues into your code.
If the type is actually irrelevant (only its size is important) then you
might as well simply change the declaration of the bit array object to an
array of unsigned char...
unsigned char bitfield[(32 + CHAR_BIT  1)/ CHAR_BIT];
In anycase, using the above macros for this purpose would (in practice) be
highly inefficient. For the mask of the least significant bit you can simply
do...
uint32_t x = ...some value to be searched...
uint32_t m = x & (x + 0u);

Peter  
P: n/a

On Thu, 01 Jan 2004 00:12:44 0500, Peter Nilsson wrote: >> > #define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] >> > #define bitset_mask(ptr,bit) (1 << (bit) % 8) <snip> > > But I'd actually have to question what type ptr is and why the author > feels the need for the (unsigned char *) cast.
The type of 'ptr' can be a pointer to anything. For example it could be an uint32_t * so that 32 bits can be tested with each iteration of a loop when searching for the first free or used bit in a bit map.
That would introduce endian issues into your code.
Assuming different offsets within the bitset's memory aren't used and one
does not write the bitset memory to a file or the network, how exactly
are there "endian issues"?
If the type is actually irrelevant (only its size is important) then you might as well simply change the declaration of the bit array object to an array of unsigned char...
unsigned char bitfield[(32 + CHAR_BIT  1)/ CHAR_BIT];
I suppose this is nice for determing the correct size based on the number
of bits but I don't see why I should define a bitset type when all you
need is a pointer to the target memory and maybe a pointer to the end
of the target memory.
In anycase, using the above macros for this purpose would (in practice) be highly inefficient. For the mask of the least significant bit you can simply do...
uint32_t x = ...some value to be searched... uint32_t m = x & (x + 0u);
So (1 << (bit) % 8) is "highly inefficient" because it doesn't use &
over % 1/8th of the time?
Mike  
P: n/a

begin followup to Michael B Allen: On Thu, 01 Jan 2004 00:12:44 0500, Peter Nilsson wrote: For the mask of the least significant bit you can simply do...
uint32_t x = ...some value to be searched... uint32_t m = x & (x + 0u);
If x == 1 then m = 1 & 1 http://www.duke.edu/~twf/cps104/twoscomp.html
# To get the two's complement negative notation of an integer, you
# write out the number in binary. You then invert the digits, and
# add one to the result.
Expressed as two's complement 1 means a word with all bits set.
m will then be 1, i.e. the same as x.
If x is a power of two, then m will always be equal to x.
What's the point?
So (1 << (bit) % 8) is "highly inefficient" because it doesn't use & over % 1/8th of the time?
^^^^^^^^^^^^^^^^^
I don't understand this constraint. And I don't understand it's
relation to Nilsson's suggested improvement. Am I lame, or what?
Division is more expensive than bit manipulation. Always.
Given your original definitions:
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8]
#define bitset_mask(ptr,bit) (1 << (bit) % 8)
(bit) / 8 is equivalent to (bit) >> 3.
(bit) % 8 is equivalent to (bit) & 7.
Both optimisations require that the constant operand is a power
of two, e.g. 8, 16 or 32.
You may rely on the compiler to optimize this out. In the end all
discussions of this kind break down to a disassembly listing dick
size war.

Für Google, Tux und GPL!  
P: n/a

On Thu, 01 Jan 2004 09:07:31 0500, Alexander Bartolich wrote: For the mask of the least significant bit you can simply do...
uint32_t x = ...some value to be searched... uint32_t m = x & (x + 0u); So (1 << (bit) % 8) is "highly inefficient" because it doesn't use & over % 1/8th of the time? ^^^^^^^^^^^^^^^^^ I don't understand this constraint. And I don't understand it's relation
I still don't understand. Is Peter talking about searching such that
you can obtain the lowest bit in a 32 bit portion of the bit set in one
step? That's nice but does this have anything to do with the bitset_elem
macro? If so, can someone please just post a version that demonstraits
the improvement? Benadryl and bit manipulation don't mix.
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
(bit) / 8 is equivalent to (bit) >> 3. (bit) % 8 is equivalent to (bit) & 7.
Ok, so I can do:
#define bitset_mask(ptr,bit) (1u << ((bit) & (CHAR_BIT  1)))
but I don't know of a constant expression to get 3 from 8 or 4 from 16
or 5 from 32 assuming CHAR_BIT is a power of two so this doesn't help
with bitset_elem.
Mike  
P: n/a

Onn 2004 09:07:31 0500, Alexander Bartolich wrote: For the mask of the least significant bit you can simply do...
uint32_t x = ...some value to be searched... uint32_t m = x & (x + 0u); So (1 << (bit) % 8) is "highly inefficient" because it doesn't use & over % 1/8th of the time? ^^^^^^^^^^^^^^^^^ I don't understand this constraint. And I don't understand it's relation
I still don't understand. Is Peter talking about searching such that
you can obtain the lowest bit in a 32 bit portion of the bit set in one
step? That's nice but does this have anything to do with the bitset_elem
macro? If so, can someone please just post a version that demonstraits
the improvement? Benadryl and bit manipulation don't mix.
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
(bit) / 8 is equivalent to (bit) >> 3. (bit) % 8 is equivalent to (bit) & 7.
Ok, so I can do:
#define bitset_mask(ptr,bit) (1u << ((bit) & (CHAR_BIT  1)))
but I don't know of a constant expression to get 3 from 8 or 4 from 16
or 5 from 32 assuming CHAR_BIT is a power of two so this doesn't help
with bitset_elem.
Mike  
P: n/a

begin Michael B Allen: but I don't know of a constant expression to get 3 from 8 or 4 from 16 or 5 from 32 assuming CHAR_BIT is a power of two so this doesn't help with bitset_elem.
IMHO there is no need to shoot for perfect in this case.
#if CHAR_BIT == 8
# define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit) >> 3]
#else
# define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit) / CHAR_BIT]
#endif
Strictly conforming, but still gets performance out of nonoptimizing
compilers on typical platforms.

Für Google, Tux und GPL!  
P: n/a

Michael B Allen wrote: On Thu, 01 Jan 2004 09:07:31 0500, Alexander Bartolich wrote: For the mask of the least significant bit you can simply do...
uint32_t x = ...some value to be searched... uint32_t m = x & (x + 0u);
So (1 << (bit) % 8) is "highly inefficient" because it doesn't use & over % 1/8th of the time? ^^^^^^^^^^^^^^^^^ I don't understand this constraint. And I don't understand it's relation
I still don't understand. Is Peter talking about searching such that you can obtain the lowest bit in a 32 bit portion of the bit set in one step? That's nice but does this have anything to do with the bitset_elem macro? If so, can someone please just post a version that demonstraits the improvement? Benadryl and bit manipulation don't mix.
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
(bit) / 8 is equivalent to (bit) >> 3. (bit) % 8 is equivalent to (bit) & 7.
Ok, so I can do:
#define bitset_mask(ptr,bit) (1u << ((bit) & (CHAR_BIT  1)))
but I don't know of a constant expression to get 3 from 8 or 4 from 16 or 5 from 32 assuming CHAR_BIT is a power of two so this doesn't help with bitset_elem.
No.
Suppose CHAR_BIT equals eleven.
Do You want a mask that looks like this: '1010' ?
(1u << ((bit) % CHAR_BIT))

pete  
P: n/a

"Michael B Allen" <mb*****@ioplex.com> wrote in message
news:pa**********************************@ioplex.c om... On Thu, 01 Jan 2004 09:07:31 0500, Alexander Bartolich wrote: For the mask of the least significant bit you can simply do...
uint32_t x = ...some value to be searched... uint32_t m = x & (x + 0u);
So (1 << (bit) % 8) is "highly inefficient" because it doesn't use & over % 1/8th of the time? ^^^^^^^^^^^^^^^^^ I don't understand this constraint. And I don't understand it's relation
I still don't understand. Is Peter talking about searching such that you can obtain the lowest bit in a 32 bit portion of the bit set in one step?
Yes.
That's nice but does this have anything to do with the bitset_elem macro?
It was an example of an alternative which may be more efficient (in one
specific instance).
If so, can someone please just post a version that demonstraits the improvement? Benadryl and bit manipulation don't mix.
#define bitset_elem(ptr,bit) ((unsigned char *)(ptr))[(bit)/8] #define bitset_mask(ptr,bit) (1 << (bit) % 8)
(bit) / 8 is equivalent to (bit) >> 3. (bit) % 8 is equivalent to (bit) & 7. Ok, so I can do:
#define bitset_mask(ptr,bit) (1u << ((bit) & (CHAR_BIT  1)))
That wouldn't be useful in all cases. Even on machines with power of 2
CHAR_BIT values, the original code will generally be optimised. [It's
subject to QoI, of course.]
but I don't know of a constant expression to get 3 from 8 or 4 from 16 or 5 from 32 assuming CHAR_BIT is a power of two so this doesn't help with bitset_elem.
With constant expressions this can be done up to a point (i.e. a finite bit
size).
#define LOG2_2POWN(x) \
( (x == 0x00000001) ? 1 \
: (x == 0x00000002) ? 2 \
: (x == 0x00000004) ? 3 \
: (x == 0x80000000) ? 31 )
For nonconstant expressions, you can try a switch statement, or a hack
like...
unsigned magic_table[] = {
31, 0, 22, 1, 28, 23, 13, 2,
29, 26, 24, 17, 19, 14, 9, 3,
30, 21, 27, 12, 25, 16, 18, 8,
20, 11, 15, 7, 10, 6, 5, 4
};
#define LOG2_2POWN(x) \
( magic_table[ ((x)*0x0FB9AC52u >> 27) & 0x1F ] )

Peter   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 7489
 replies: 13
 date asked: Nov 14 '05
