1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
|
#ifndef __LASTBIT_H
#define __LASTBIT_H
#include "utypes.h"
inline uint firstbit (uint64_t v)
{
//unsigned int v; // 32-bit value to find the log2 of
// TODO: find utype identifier for 8-byte int (uL may not be portable)
const uint64_t b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000uLL};
const unsigned int S[] = {1, 2, 4, 8, 16, 32};
int i;
register unsigned int r = 0; // result of log2(v) will go here
for (i = 5; i >= 0; i--) // unroll for speed...
{
if (v & b[i])
{
v >>= S[i];
r |= S[i];
}
}
return r;
}
inline int lastbit (uint32_t v)
{
int r;
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
return r;
}
inline int lastbit (uint16_t v)
{
int r;
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
return r;
}
inline int lastbit (uint64_t v)
{
if (v)
{
uint32_t lower = static_cast<uint32_t>(v&0xFFFFFFFF);
if (lower)
return lastbit(lower);
uint32_t upper = static_cast<uint32_t>
((v & 0xFFFFFFFF00000000uLL)>>32);
//uint32_t upper = static_cast<uint32_t>((v>>32)&0xFFFFFFFF);
return lastbit(upper)+32;
}
return 0;
}
// this one is slow on XP 32
inline int lastbit64 (uint64_t v)
{
int r; // put the result in r
static const int Mod67BitPosition[] = // map a bit value mod 37 to its position
{
0, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59,
41, 19, 24, 54, 4, 0, 13, 10, 17, 62, 60, 28,
42, 30, 20, 51, 25, 44, 55, 47, 5, 32, 0, 38,
14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 29, 50,
43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36,
56, 7, 48, 35, 6, 34, 33,
};
r = Mod67BitPosition[(-v & v) % 67];
//cout << (-v&v)%37 << " " << lastbit(v) << endl;
// cout << (-v&v)%67 << " " << lastbit(v) << " " << r << endl;
// if (lastbit(v) != r)
// cout << "fuck\n";
return r;
}
#endif
|