14 template <
class Integer>
struct Bsf;
17 struct Bsf<unsigned int>
19 static int bsf(
unsigned int mask)
24 __asm__(
"bsfl %1,%0" :
"=r"(ret) :
"r"(mask));
29 __asm__(
"bsfl %1,%0" :
"=r"(ret) :
"r"(mask));
31# elif defined __GNUC__
32 return __builtin_ctzl(mask);
34 for (
int i=0;i<32;i++)
44 struct Bsf<unsigned short>
46 static unsigned short bsf(
unsigned short mask)
51 __asm__(
"bsfw %1,%0" :
"=r"(ret) :
"r"(mask));
56 __asm__(
"bsfw %1,%0" :
"=r"(ret) :
"r"(mask));
59 return __builtin_ctzl(mask);
66 struct Bsf<unsigned long long>
68 static int bsf(
unsigned long long mask)
73 __asm__(
"bsfq %1,%0" :
"=r"(ret) :
"r"(mask));
74 return static_cast<int>(ret);
76 unsigned int mask32 =
static_cast<unsigned int>(mask);
79 mask32 =
static_cast<unsigned int>(mask >> 32);
85 template <
class Integer>
struct Bsr;
88 struct Bsr<unsigned int>
90 static int bsr(
unsigned int mask)
95 __asm__(
"bsrl %1,%0" :
"=r"(ret) :
"r"(mask));
100 __asm__(
"bsrl %1,%0" :
"=r"(ret) :
"r"(mask));
103 return __builtin_clzl(mask);
105 for (
int i=31; i>=0; --i)
116 struct Bsr<unsigned long long>
118 static int bsr(
unsigned long long mask)
123 __asm__(
"bsrq %1,%0" :
"=r"(ret) :
"r"(mask));
124 return static_cast<int>(ret);
126 unsigned int mask32 =
static_cast<unsigned int>(mask >> 32);
129 mask32 =
static_cast<unsigned int>(mask);
137 template <
class Integer>
138 static int bsf(Integer mask)
142 template <
class Integer>
143 static int bsr(Integer mask)
147 template <
class Integer>
150 const int num=
bsf(mask);
155 template <
class Integer>
170 template <
class Integer>
173 return (mask & (mask-1));
178 template <
class Integer>
181 return static_cast<Integer
>(mask & (-mask));
199 inline int countBitDense(
unsigned int mask)
201 mask = ((mask>>1)&0x55555555)+(mask&0x55555555);
202 mask = ((mask>>2)&0x33333333)+(mask&0x33333333);
203 mask = ((mask>>4)+mask)&0xf0f0f0f;
204 mask = (mask>>8)+mask;
205 return ((mask>>16)+mask)&0x3f;
211 template <
class Integer>
302 template <
class Integer>
inline
307 template <
class Integer>
inline
312 template <
class Integer>
inline
318 template <
class Integer>
inline
324 template <
class Integer>
inline
330 template <
class Integer>
inline
336 template <
class Integer>
inline
339 return result <<= shift;
341 template <
class Integer>
inline
344 return result >>= shift;
GeneralMask & operator|=(const GeneralMask &r)
GeneralMask & operator+=(const GeneralMask &r)
GeneralMask & operator<<=(int shift)
static const GeneralMask makeDirect(Integer value)
GeneralMask(Integer value)
const GeneralMask operator~() const
GeneralMask & operator>>=(int shift)
bool hasMultipleBit() const
non-zeroのmaskが複数ビットセットされているかどうかを返す.
int countBit() const
mask にセットされているビットの数を数える. あまり速くない.
GeneralMask & operator-=(const GeneralMask &r)
int countBit2() const
non-zeroのmaskにセットされているビットの数を2まで数える.
GeneralMask & operator^=(const GeneralMask &r)
int takeOneBit()
non-zeroのmaskのsetされているビットをLSBから探し,その番号を返す 副作用としてmaskの対応するビットをクリアする
GeneralMask lowestBit() const
non-zeroのmaskのsetされているビットをLSBから探し,そのビットだけがsetされたmaskを返す.
GeneralMask & operator&=(const GeneralMask &r)
bool operator==(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
const GeneralMask< Integer > operator^(GeneralMask< Integer > l, GeneralMask< Integer > r)
bool operator<(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
GeneralMask< mask_int_t > mask_t
bool operator!=(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
unsigned long long mask_int_t
const GeneralMask< Integer > operator>>(GeneralMask< Integer > m, int shift)
const GeneralMask< Integer > operator|(GeneralMask< Integer > l, GeneralMask< Integer > r)
GeneralMask< unsigned long long > Mask64
const GeneralMask< Integer > operator&(GeneralMask< Integer > l, GeneralMask< Integer > r)
const GeneralMask< Integer > operator<<(GeneralMask< Integer > m, int shift)
const PtypeO PTYPEO_EDGE __attribute__((unused))
static int bsf(Integer mask)
static int takeOneBit(Integer &mask)
static int bsr(Integer mask)
static bool hasMultipleBit(Integer mask)
static Integer lowestBit(Integer mask)
non-zeroのmaskのsetされているビットをLSBから探し,そのビットだけがsetされたmaskを返す.
static int countBit(Integer mask)
static int bsf(unsigned int mask)
static int bsf(unsigned long long mask)
static unsigned short bsf(unsigned short mask)
static int bsr(unsigned int mask)
static int bsr(unsigned long long mask)