How to find longest bitrange of ones

Discussion in 'C Programming' started by longhorn, May 7, 2008.

  1. longhorn

    longhorn Guest

    Hello,

    I'm looking for a macro that will return the longest range of ones
    in an unsigned integer, along with starting and ending position.

    For example I have an unsigned int data that looks like:

    bit pos: 31 30 29 28 27 26 25 24 23 22 21 20 19 18 .... 00
    data 0 1 1 1 1 0 1 1 0 1 0 1 1 0 ... 0

    In this case I would get the longest range = 4, start=27, end=30.

    Does anyone know a simple way to do this?

    Thanks,
    Kevin
    longhorn, May 7, 2008
    #1
    1. Advertising

  2. longhorn wrote:
    > Hello,
    >
    > I'm looking for a macro that will return the longest range of ones
    > in an unsigned integer, along with starting and ending position.
    >
    > For example I have an unsigned int data that looks like:
    >
    > bit pos: 31 30 29 28 27 26 25 24 23 22 21 20 19 18 .... 00
    > data 0 1 1 1 1 0 1 1 0 1 0 1 1 0 ... 0
    >
    > In this case I would get the longest range = 4, start=27, end=30.


    Have you considered cases like: 01111011110...0

    > Does anyone know a simple way to do this?


    Hint:

    What happens to a string of 1's in x if you do x &= x << 1?
    What happens if you keep iterating?

    --
    Peter
    Peter Nilsson, May 7, 2008
    #2
    1. Advertising

  3. longhorn

    Willem Guest

    longhorn wrote:
    ) Hello,
    )
    ) I'm looking for a macro that will return the longest range of ones
    ) in an unsigned integer, along with starting and ending position.
    )
    ) For example I have an unsigned int data that looks like:
    )
    ) bit pos: 31 30 29 28 27 26 25 24 23 22 21 20 19 18 .... 00
    ) data 0 1 1 1 1 0 1 1 0 1 0 1 1 0 ... 0
    )
    ) In this case I would get the longest range = 4, start=27, end=30.
    )
    ) Does anyone know a simple way to do this?

    Do you want a clever bit hack, or a straightforward iteration ?


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
    Willem, May 7, 2008
    #3
    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. Replies:
    0
    Views:
    656
  2. Replies:
    2
    Views:
    353
  3. Lou Pecora
    Replies:
    4
    Views:
    287
    Lou Pecora
    Nov 8, 2004
  4. Tim Zych
    Replies:
    2
    Views:
    164
    Tim Zych
    Nov 28, 2005
  5. John Howard
    Replies:
    14
    Views:
    219
    Paul Lalli
    Aug 19, 2005
Loading...

Share This Page