Bitset Macros

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!

"Alexander Bartolich" <al************ *****@gmx.at> wrote in message
news:bs******** ****@ID-193444.news.uni-berlin.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

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

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

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

"Michael B Allen" <mb*****@ioplex .com> wrote in message
news:pa******** *************** **********@iopl ex.com...

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

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

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!

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