#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__