4 inline cell log2(cell x)
7 #if defined(FACTOR_X86)
11 asm ("bsr %1, %0;":"=r"(n):"r"(x));
13 #elif defined(FACTOR_AMD64)
16 _BitScanReverse64((DWORD *)&n,x);
18 asm ("bsr %1, %0;":"=r"(n):"r"(x));
20 #elif defined(FACTOR_PPC64)
22 n = (63 - __builtin_clzll(x));
24 #error Unsupported compiler
26 #elif defined(FACTOR_PPC32)
28 n = (31 - __builtin_clz(x));
30 #error Unsupported compiler
33 #error Unsupported CPU
38 inline cell rightmost_clear_bit(cell x)
40 return log2(~x & (x + 1));
43 inline cell rightmost_set_bit(cell x)
45 return log2(x & (~x + 1));
48 inline cell popcount(cell x)
52 return __builtin_popcountll(x);
54 return __builtin_popcount(x);
58 u64 k1 = 0x5555555555555555ll;
59 u64 k2 = 0x3333333333333333ll;
60 u64 k4 = 0x0f0f0f0f0f0f0f0fll;
61 u64 kf = 0x0101010101010101ll;
71 x = x - ((x >> 1) & k1); // put count of each 2 bits into those 2 bits
72 x = (x & k2) + ((x >> 2) & k2); // put count of each 4 bits into those 4 bits
73 x = (x + (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
74 x = (x * kf) >> ks; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
80 inline bool bitmap_p(u8 *bitmap, cell index)
82 cell byte = index >> 3;
84 return (bitmap[byte] & (1 << bit)) != 0;