Re: 64-bit masks

[Juergen Buchmueller <pullmoll%t-online.de@localhost>]

On Sun, 29 Nov 2009 18:55:12 -0500 (EST)
der Mouse <mouse%Rodents-Montreal.ORG@localhost> wrote:
> Given your convention for bit values, you'd have to complement your
> mask before using it, but it may still be fast enough to be useful:
> 
> int first_free(uint64_t m)
> {
>  m = (~m) & ~((~m)-1);
>  if (! m) return(-1);
>  return( ((m & 0xffffffff00000000ULL) ? 32 : 0) +
>        ((m & 0xffff0000ffff0000ULL) ? 16 : 0) +
>        ((m & 0xff00ff00ff00ff00ULL) ?  8 : 0) +
>        ((m & 0xf0f0f0f0f0f0f0f0ULL) ?  4 : 0) +
>        ((m & 0xccccccccccccccccULL) ?  2 : 0) +
>        ((m & 0x5555555555555555ULL) ?  1 : 0) );
> }

There's a number of algorithms like this on: http://aggregate.org/MAGIC/
For Sad Clouds' case he could use:

unsigned ones64(uint64_t x)
{
  x -= ((x>>1) & 0x5555555555555555ULL);
  x = (((x>>2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL));
  x = (((x>>4) + x) & 0x0f0f0f0f0f0f0f0fULL);
  x += (x>>8);
  x += (x>>16);
  x += (x>>32);
  return(x & 0x0000007f);
}

unsigned trailing_zero_count(uint64_t x)
{
   return ones64((x & -x) - 1);
}

unsigned first_zero_bit(uint64_t x)
{
  return trailing_zero_count(~x);
}

HTH,
Juergen