2 ms·
This is not a good way to implement clz. There are nice branch-free methods for these: /* Count no. trailing zeros */ int ntz(unsigned x) {
by jhallenworld 11y ago
This is not a good way to implement clz. There are nice branch-free methods for these:
/* Count no. trailing zeros */
int ntz(unsigned x)
{
/* Set all trailing zeros to ones */
/* And clear leading zeros */
x = ~x & (x - 1);
/* Now get population count */
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x3F;
}
/* Count leading zeros */
/* log2(x) is 31-nlz(x) */
int nlz(unsigned x)
{
/* Make all bits to the right of the first 1 a 1 */
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
/* Make all bits to the left 1s */
x = ~x;
/* Population count */
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x3F;
}
(these are from Hacker's Delight)