000
09.01.2009, 23:56 Uhr
0xdeadbeef
Gott
(Operator)
|
Moin,
Ich bin eben mal wieder auf http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive gestoßen, eine sehr praktische Seite mit einem Haufen ausgesprochen nützlicher Performance-Hacks. Und als ich das so las, dachte ich mir: "Das muss doch auch generisch gehen. Wofür haben wir denn templates?"
Das vorläufige Ergebnis ist:
| C++: |
#include <iostream>
namespace impl {
template<typename t> struct bitwidth {
static int const val = sizeof(t) * 8;
};
template<typename t, int clumpsize, int it = bitwidth<t>::val / 4 / clumpsize> struct magic_builder_b {
static t const clump = magic_builder_b<t, clumpsize, it / 2>::val;
static t const val = clump | (clump << it * 2 * clumpsize);
};
template<typename t, int clumpsize>
struct magic_builder_b<t, clumpsize, 0> {
static t const val = (t(1) << clumpsize) - 1;
};
template<typename t, int ix> struct magic_numbers {
static t const S = 1 << ix;
static t const B = magic_builder_b<t, S>::val;
};
template<typename t, int it, bool finished> struct bitcounter {
typedef magic_numbers<t, it> mnum;
static inline int count(t x) {
return bitcounter<t, it + 1,
bitwidth<t>::val == mnum::S * 2>::count((x >> mnum::S) + x & mnum::B);
}
};
template<typename t, bool finished> struct bitcounter<t, 0, finished> {
typedef magic_numbers<t, 0> mnum;
static inline int count(t x) {
return bitcounter<t, 1,
bitwidth<t>::val == mnum::S * 2>::count(x - (x >> 1 & mnum::B));
}
};
template<typename t, bool finished> struct bitcounter<t, 1, finished> {
typedef magic_numbers<t, 1> mnum;
static inline int count(t x) {
return bitcounter<t, 2,
bitwidth<t>::val == mnum::S * 2>::count(((x >> mnum::S) & mnum::B)
+ (x & mnum::B));
}
};
template<typename t, int it> struct bitcounter<t, it, true> {
static inline int count(t x) { return x; }
};
}
template<typename t> int bitcount(t x) {
return impl::bitcounter<t, 0, false>::count(x);
}
template<typename t> void print_binary(t x) {
for(int i = 0; i < impl::bitwidth<t>::val; ++i) {
std::cout << (x >> i & 1) ? '1' : '0';
}
std::cout << std::endl;
}
int main() {
print_binary(impl::magic_builder_b<unsigned long long, 8>::val);
print_binary(impl::magic_numbers<int, 4>::B);
std::cout << bitcount(impl::magic_numbers<int, 4>::B) << std::endl;
std::cout << bitcount(127ULL) << std::endl;
std::cout << bitcount(-1L) << std::endl;
std::cout << bitcount(short(-1)) << std::endl;
std::cout << bitcount('A') << std::endl;
print_binary(0xdeadbeef);
std::cout << bitcount(0xdeadbeef) << std::endl;
print_binary(-1234);
std::cout << bitcount(-1234) << std::endl;
}
|
Meinungen?
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 10.01.2009 um 00:30 Uhr von 0xdeadbeef editiert. |
