How to find lowest bit position of mask with macro only

E

ex laguna

How do I find the lowest bit position of a mask using only macros?

I want to do everything in compile time. That mean, there cannot be
control statements such as if, while, for, etc. in the macro.

Note that the macro takes only one (1) argument, the mask.

Examples:

// Mask Lowest bit position
0111 0000 4
0001 0000 4
0001 1000 3
0011 1111 0

Thanks.
 
B

Ben Pfaff

How do I find the lowest bit position of a mask using only macros?

Presumably you mean the lowest bit set to 1.
I want to do everything in compile time. That mean, there cannot be
control statements such as if, while, for, etc. in the macro.

#define LOWEST_1_BIT(MASK) \
(((MASK) & 0001) ? 0 : /* bit 0 is set? */
((MASK) & 0002) ? 1 : /* bit 1 is set? */
((MASK) & 0004) ? 2 : /* bit 2 is set? */
((MASK) & 0010) ? 3 : /* bit 3 is set? */
((MASK) & 0020) ? 4 : /* bit 4 is set? */
/* ... */
-1) /* no bits are set */
 
A

Alf P. Steinbach

How do I find the lowest bit position of a mask using only macros?

I want to do everything in compile time. That mean, there cannot be
control statements such as if, while, for, etc. in the macro.

Note that the macro takes only one (1) argument, the mask.

Examples:

// Mask Lowest bit position
0111 0000 4
0001 0000 4
0001 1000 3
0011 1111 0

You could do that with a lot of ?: operators in sequence, but
you'd need N operators where N is the number of bits.

Alternative you could use lg N macros, like (off the cuff)


#define LOWESTBITPOS2( x ) (x & 0x1? 0 : 1)
#define LOWESTBITPOS4( x ) (x & 0x3? LOWESTBITPOS2( x ) : 2+LOWESTBITPOS2( x >> 2 ))
#define LOWESTBITPOS8( x ) (x & 0xF? LOWESTBITPOS4( x ) : 4+LOWESTBITPOS4( x >> 4 ))
#define LOWESTBITPOS16( x ) (x & 0xFF? LOWESTBITPOS8( x ) : 8+LOWESTBITPOS8( x >> 8 ))
#define LOWESTBITPOS32( x ) (x & 0xFFFF? LOWESTBITPOS16( x ) : 16+LOWESTBITPOS16( x >> 16 ))

#define LOWESTBITPOS( x ) LOWESTBITPOS32( x )


If this works, then I wrote it. If not, then some unscroupolous
evil charlatan impersionated me. Anyway, note the assumption of 32
bits maximum.
 
A

Alf P. Steinbach

Also note the assumption of at least one 1-bit.

If that's not the case you need to decide what the result should
be for a bitpattern of all zeros.
 
A

Alf P. Steinbach

Yes, the assumption is that the mask is a non-zero constant number
known at compile time.

So my question is, would all these "?" statements use any CPU at run
time?

Not for a compile-time constant... ;-)

Whether they would for a run-time call is, however, a Quality Of
Implementation issue, i.e. that depends on your compiler.
 
E

Eric Sosman

ex said:
Yes, the assumption is that the mask is a non-zero constant number
known at compile time.

So my question is, would all these "?" statements use any CPU at run
time?

Probably not. The expression is a "constant expression,"
meaning that it can be evaluated at compile time and could
be used anywhere a constant can be used. However, there is
no absolute guarantee in the Standard that an expression
that *can* be evaluated at compile time *will* be evaluated
at compile time. An implementation that didn't do so would
certainly be regarded as perverse, but ...
 
P

Peter Nilsson

How do I find the lowest bit position of a mask using only macros?

I want to do everything in compile time. That mean, there cannot be
control statements such as if, while, for, etc. in the macro.

Note that the macro takes only one (1) argument, the mask.

Examples:

// Mask Lowest bit position
0111 0000 4
0001 0000 4
0001 1000 3
0011 1111 0

Thanks.

If your mask is an unsigned integer then (mask & -mask) will produce
the lowest masked bit. That's not what you asked for, but it may be
suitable for your underlying problem.
 
M

Michael B Allen

If your mask is an unsigned integer then (mask & -mask) will produce the
lowest masked bit. That's not what you asked for, but it may be suitable
for your underlying problem.

....and if you multiply or divide by the result of that it gives you the
same result as shifting by the index of that bit. For example if mask
0x08 is bit 4:

val / (0x08 & -0x08)

is the same as

val >> 4

So if the OP is going to use the value to shift they could multiply or
divide instead.

This leads to a nice macro for decoding bitfields:

#define FLD(i, m) (m != 0 ? ((i) & (m)) / ((m) & -(m)) : 0)

Mike
 
E

ex laguna

Michael B Allen said:
...and if you multiply or divide by the result of that it gives you the
same result as shifting by the index of that bit. For example if mask
0x08 is bit 4:

val / (0x08 & -0x08)

is the same as

val >> 4

So if the OP is going to use the value to shift they could multiply or
divide instead.

This leads to a nice macro for decoding bitfields:

#define FLD(i, m) (m != 0 ? ((i) & (m)) / ((m) & -(m)) : 0)

Mike

Thank you very much Mike. This is exactly what I am looking for. I am
writing a communications message protocol parser, so I only have to
define the bit masks of the messages.

Best Regards,
Ex Laguna
 
P

Peter Nilsson

I should have added "of int rank or higher..."

That's potential division by zero. Use 0x08u.

ITYM val >> 3

Might as well have ((m) != 0 ? ...
Thank you very much Mike. This is exactly what I am looking for. I am
writing a communications message protocol parser, so I only have to
define the bit masks of the messages.

As I thought, the old communication problem: I need to solve A, I
*think* I need to do B, so I'll ask how to solve B... ;)
 
P

Peter Nilsson

Michael B Allen said:
That's what the ((m) != 0 ? ... is for.

??? 0x08 is non-zero.

You're missing the fact that it's a *signed* int. On a one's
completement implementation the expression (0x08 & -0x08) evaluates to
0.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,905
Latest member
Kristy_Poole

Latest Threads

Top