Bitset Macros

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

#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

[Alexander Bartolich]

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!

[Peter Nilsson]

"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

[Michael B Allen]

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

[Michael B Allen]

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

[Arthur Gold]

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

[Peter Nilsson]

"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

[Michael B Allen]

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

[Alexander Bartolich]

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!

[Michael B Allen]

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

[Michael B Allen]

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

[Alexander Bartolich]

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 non-optimizing
compilers on typical platforms.

--
Für Google, Tux und GPL!

[pete]

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

[Peter Nilsson]

"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 non-constant 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