mirror of https://github.com/lianthony/NT4.0
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
59 lines
1.4 KiB
59 lines
1.4 KiB
#ifndef __TWO_INCLUDED__
|
|
#define __TWO_INCLUDED__
|
|
|
|
// return largest i such that 2^i <= u
|
|
inline int lg(unsigned u) {
|
|
debug(unsigned u0 = u;)
|
|
precondition(u > 0);
|
|
|
|
int n = 0;
|
|
#define t(j) if (u >= (1 << (j))) { u >>= (j); n += (j); }
|
|
t(16); t(8); t(4); t(2); t(1);
|
|
#undef t
|
|
|
|
postcondition(u == 1);
|
|
postcondition((1U << n) <= u0);
|
|
postcondition(n == 31 || u0 < (1U << (n+1)));
|
|
return n;
|
|
}
|
|
|
|
// return smallest n such that n = 2^i and u <= n
|
|
inline unsigned nextPowerOfTwo(unsigned u) {
|
|
precondition(u > 0);
|
|
|
|
int lgu = lg(u);
|
|
int lguRoundedUp = lg(u + (1 << lgu) - 1);
|
|
unsigned n = 1 << lguRoundedUp;
|
|
|
|
postcondition(n/2 < u && u <= n);
|
|
return n;
|
|
// examples:
|
|
// u lgu lgRU n
|
|
// 1 0 0 1
|
|
// 4 2 2 4
|
|
// 5 2 3 8
|
|
// 7 2 3 8
|
|
// 8 3 3 8
|
|
}
|
|
|
|
inline unsigned nextMultiple(unsigned u, unsigned m) {
|
|
return (u + m - 1) / m * m;
|
|
}
|
|
|
|
inline int nextMultiple(int i, unsigned m) {
|
|
return (i + m - 1) / m * m;
|
|
}
|
|
|
|
// Return number of set bits in the word.
|
|
inline unsigned bitcount(unsigned u) {
|
|
// In-place adder tree: perform 16 1-bit adds, 8 2-bit adds, 4 4-bit adds,
|
|
// 2 8=bit adds, and 1 16-bit add.
|
|
u = ((u >> 1)&0x55555555) + (u&0x55555555);
|
|
u = ((u >> 2)&0x33333333) + (u&0x33333333);
|
|
u = ((u >> 4)&0x0F0F0F0F) + (u&0x0F0F0F0F);
|
|
u = ((u >> 8)&0x00FF00FF) + (u&0x00FF00FF);
|
|
u = ((u >>16)&0x0000FFFF) + (u&0x0000FFFF);
|
|
return u;
|
|
}
|
|
|
|
#endif // !__TWO_INCLUDED__
|