Velocity Reviews > How to find longest bitrange of ones

# How to find longest bitrange of ones

longhorn
Guest
Posts: n/a

 05-07-2008
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

Peter Nilsson
Guest
Posts: n/a

 05-07-2008
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

Willem
Guest
Posts: n/a

 05-07-2008
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