How to find lowest bit position of mask with macro only

Discussion in 'C Programming' started by ex laguna, Jul 25, 2003.

  1. ex laguna

    ex laguna Guest

    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.
     
    ex laguna, Jul 25, 2003
    #1
    1. Advertising

  2. ex laguna

    Ben Pfaff Guest

    (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,0xa67f6aaa,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;}}}
     
    Ben Pfaff, Jul 25, 2003
    #2
    1. Advertising

  3. On 25 Jul 2003 10:23:20 -0700, (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, Jul 25, 2003
    #3
  4. 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, Jul 25, 2003
    #4
  5. On 25 Jul 2003 14:22:41 -0700, (ex laguna) wrote:

    > (Alf P. Steinbach) wrote in message news:<>...
    >> 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.
     
    Alf P. Steinbach, Jul 25, 2003
    #5
  6. ex laguna

    Eric Sosman Guest

    ex laguna wrote:
    >
    > (Alf P. Steinbach) wrote in message news:<>...
    > > 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 ...

    --
     
    Eric Sosman, Jul 25, 2003
    #6
  7. (ex laguna) wrote in message news:<>...
    > 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
     
    Peter Nilsson, Jul 26, 2003
    #7
  8. 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
     
    Michael B Allen, Jul 26, 2003
    #8
  9. ex laguna

    ex laguna Guest

    Michael B Allen <> wrote in message news:<>...
    > 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
     
    ex laguna, Jul 26, 2003
    #9
  10. (ex laguna) wrote in message news:<>...
    > Michael B Allen <> wrote in message news:<>...
    > > 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
     
    Peter Nilsson, Jul 27, 2003
    #10
  11. 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
     
    Michael B Allen, Jul 27, 2003
    #11
  12. Michael B Allen <> wrote in message news:<>...
    > 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
     
    Peter Nilsson, Jul 27, 2003
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Francois Grieu

    Improving mask-to-bit macro

    Francois Grieu, Oct 13, 2009, in forum: C Programming
    Replies:
    12
    Views:
    986
    Tim Rentsch
    Oct 14, 2009
  2. Jason Shohet

    want a treeview that only postbacks on lowest node

    Jason Shohet, Dec 15, 2003, in forum: ASP .Net Web Controls
    Replies:
    0
    Views:
    108
    Jason Shohet
    Dec 15, 2003
  3. Marcin Tyman

    Conversion mask in hex to bit mask

    Marcin Tyman, May 6, 2008, in forum: Ruby
    Replies:
    4
    Views:
    892
    Robert Klemme
    May 6, 2008
  4. 187
    Replies:
    2
    Views:
    621
    Bart Lateur
    Jul 29, 2004
  5. loial

    Find lowest level directory

    loial, Dec 13, 2012, in forum: Python
    Replies:
    2
    Views:
    144
    Peter Otten
    Dec 13, 2012
Loading...

Share This Page