00001 #ifndef MISC_BITOP_H
00002 #define MISC_BITOP_H
00003
00004 #include <cassert>
00005 namespace osl
00006 {
00007 namespace misc
00008 {
00012 template <class Integer> struct Bsf;
00013
00014 template <>
00015 struct Bsf<unsigned int>
00016 {
00017 static int bsf(unsigned int mask)
00018 {
00019 assert(mask);
00020 #ifdef __x86_64
00021 int ret;
00022 __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
00023 return ret;
00024 #else
00025 # ifdef i386
00026 int ret;
00027 __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
00028 return ret;
00029 # else
00030 return __builtin_ctzl(mask);
00031 # endif
00032 #endif
00033 }
00034 };
00035
00036 template <>
00037 struct Bsf<unsigned long long>
00038 {
00039 static int bsf(unsigned long long mask)
00040 {
00041 assert(mask);
00042 #ifdef __x86_64
00043 long long ret;
00044 __asm__("bsfq %1,%0" : "=r"(ret) : "r"(mask));
00045 return static_cast<int>(ret);
00046 #else
00047 unsigned int mask32 = static_cast<unsigned int>(mask);
00048 if (mask32)
00049 return Bsf<unsigned int>::bsf(mask32);
00050 mask32 = static_cast<unsigned int>(mask >> 32);
00051 return 32+Bsf<unsigned int>::bsf(mask32);
00052 #endif
00053 }
00054 };
00055
00056 struct BitOp
00057 {
00058 template <class Integer>
00059 static int bsf(Integer mask)
00060 {
00061 return Bsf<Integer>::bsf(mask);
00062 }
00063 template <class Integer>
00064 static int takeOneBit(Integer& mask){
00065 assert(mask);
00066 const int num=bsf(mask);
00067 mask &= mask-1;
00068 return num;
00069 }
00070
00071 template <class Integer>
00072 static int countBit(Integer mask)
00073 {
00074 int count=0;
00075 while (mask)
00076 {
00077 ++count;
00078 mask &= (mask-1);
00079 }
00080 return count;
00081 }
00082 template <class Integer>
00083 static bool hasMultipleBit(Integer mask){
00084 assert(mask);
00085 return (mask & (mask-1));
00086 }
00090 template <class Integer>
00091 static Integer lowestBit(Integer mask){
00092 assert(mask);
00093 return static_cast<Integer>(mask & (-mask));
00094 }
00095 };
00096
00097 #if 0
00098
00111 inline int countBitDense(unsigned int mask)
00112 {
00113 mask = ((mask>>1)&0x55555555)+(mask&0x55555555);
00114 mask = ((mask>>2)&0x33333333)+(mask&0x33333333);
00115 mask = ((mask>>4)+mask)&0xf0f0f0f;
00116 mask = (mask>>8)+mask;
00117 return ((mask>>16)+mask)&0x3f;
00118 }
00119 #endif
00120 }
00121 }
00122 #endif // _BITOP_H
00123
00124
00125
00126