Re: Fastest way to retrieve bit position within a __int64 (VC++ 6)

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

From: Mycroft Holmes (m.holmes_at_nospam.it)
Date: 10/21/04 

Date: Thu, 21 Oct 2004 17:30:05 +0200

> The fastest way I know of is as follows. Define a set of bit masks like
> this:
>
> m1 = 0xFFFFFFFF00000000;
> m2 = 0xFFFF0000FFFF0000;
> m3 = 0xFF00FF00FF00FF00;
> m4 = 0xF0F0F0F0F0F0F0F0;
> m5 = 0xCCCCCCCCCCCCC; // in binary, that's 11001100...
> m6 = 0xAAAAAAAAAAAA; // in binary, that's 10101010...

moreover, you can easily transform all this with a bit of good old
templates...
so you get a function which works on every integer size (as long as it's a
power of 2, but this is already an implicit assumption of the binary search)

in the code below static_butterfly<T, N>::mask is (the bitwise negation of)
your bitmask (with N starting from 0, I think)

highest_bit(x) returns 0 if x is 0, otherwise returns ceil(log2(N)).
I'm always happy to complicate simple problems... 

-- 
 The set of solutions is never empty.
 Two solutions together form a new problem.
-- Mycroft Holmes
template <size_t base>
struct static_log2
{
 enum
 {
  exact = !(base & (base-1)),
  floor = (base>0) + static_log2<(base>>1)>::floor,
  ceil = floor+!exact
 };
};
template <> struct static_log2<1> { enum { exact = 1, floor = 0, ceil =
0 }; };
template <> struct static_log2<0>;
template <typename int_t, size_t BITS, size_t INDEX>
struct static_butterfly_helper
{
 static const int_t value = (static_butterfly_helper< int_t, BITS, INDEX-1
>::value << (2*BITS) ) | static_butterfly_helper<int_t,BITS,1>::value;
};
template <typename int_t, size_t BITS>
struct static_butterfly_helper<int_t,BITS,1>
{
 static const int_t value = ( (1 << BITS)-1 );
};
template <typename int_t, size_t BITS>
struct static_butterfly_helper<int_t,BITS,0>;
template < typename int_t, size_t INDEX >
struct static_butterfly
{
 static const int_t mask = static_butterfly_helper< int_t, (1 << INDEX),
(8*sizeof(int_t))/(1 << (INDEX+1))>::value;
};
template <typename uint_t, size_t N>
struct highest_bit_helper
{
 inline static size_t apply (const uint_t x)
 {
  const size_t m = (x & ~static_butterfly<uint_t, N>::mask);
  return (m ? (1 << N) : 0) | highest_bit_helper<uint_t,N-1>::apply(m ? m :
x);
 }
};
template <typename uint_t>
struct highest_bit_helper<uint_t, 0>
{
 inline static size_t apply (const uint_t x)
 {
  const size_t m = (x & ~static_butterfly<uint_t, 0>::mask);
  return m ? 1 : 0;
 }
};
template <typename uint_t>
inline size_t highest_bit(const uint_t x)
{
 return (!!x) + highest_bit_helper< uint_t, static_log2< 8*sizeof(uint_t)
>::ceil-1 >::apply(x);
}

Relevant Pages