How to find lowest bit position of mask with macro only

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

[Ben Pfaff]

ed*****@yahoo.com (ex laguna) writes:

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 */

--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,0xaa9aa9f6,0x1f6},*p=
b,x,i=24;for(;p+=!*p;*p/=4)switch(x=*p&3)case 0:{return 0;for(p--;i--;i--)case
2:{i++;if(1)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}

[Alf P. Steinbach]

On 25 Jul 2003 10:23:20 -0700, ed*****@yahoo.com (ex laguna) wrote:

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.

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

[Alf P. Steinbach]

On 25 Jul 2003 14:22:41 -0700, ed*****@yahoo.com (ex laguna) wrote:

al***@start.no (Alf P. Steinbach) wrote in message news:<3f***************@News.CIS.DFN.DE>...

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.

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.

[Eric Sosman]

ex laguna wrote:

al***@start.no (Alf P. Steinbach) wrote in message news:<3f***************@News.CIS.DFN.DE>...

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.

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 ...

--
Er*********@sun.com

[Peter Nilsson]

ed*****@yahoo.com (ex laguna) wrote in message news:<53************************@posting.google.co m>...

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.

--
Peter

[Michael B Allen]

On Fri, 25 Jul 2003 20:52:59 -0400, Peter Nilsson wrote:

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

[ex laguna]

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

On Fri, 25 Jul 2003 20:52:59 -0400, Peter Nilsson wrote:

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

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

[Peter Nilsson]

ed*****@yahoo.com (ex laguna) wrote in message news:<53**********************@posting.google.com> ...

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

On Fri, 25 Jul 2003 20:52:59 -0400, Peter Nilsson wrote:

If your mask is an unsigned integer
I should have added "of int rank or higher..."
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)
That's potential division by zero. Use 0x08u.

is the same as

val >> 4
ITYM val >> 3

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)

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... ;)

--
Peter

[Michael B Allen]

On Sat, 26 Jul 2003 19:09:29 -0400, Peter Nilsson wrote:

> mask 0x08 is bit 4:
>
> val / (0x08 & -0x08)
That's potential division by zero. Use 0x08u.

That's what the ((m) != 0 ? ... is for.

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

Might as well have ((m) != 0 ? ...

Right.

Mike

[Peter Nilsson]

Michael B Allen <mb*****@ioplex.com> wrote in message news:<pa*********************************@ioplex.c om>...

On Sat, 26 Jul 2003 19:09:29 -0400, Peter Nilsson wrote:

> mask 0x08 is bit 4:
>
> val / (0x08 & -0x08)

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

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.

--
Peter