Decide if X is at most half as long as Y, in binary, for unsigned ints in C

Question

I have two unsigned ints X and Y, and I want to efficiently decide if X is at most half as long as Y, where the length of X is k+1, where 2^k is the largest power of 2 that is no larger than X.

i.e., X=0000 0101 has length 3, Y=0111 0000 is more than twice as long as X.

Obviously we can check by looking at individual bits in X and Y, for example by shifting right and counting in a loop, but is there an efficient, bit-twiddling (and loop-less) solution?

The (toy) motivation comes from the fact that I want to divide the range RAND_MAX either into range buckets or RAND_MAX/range buckets, plus some remainder, and I prefer use the larger number of buckets. If range is (approximately) at most the square root of RAND_MAX (i.e., at most half as long), than I prefer using RAND_MAX/range buckets, and otherwise I want to use range buckets.

It should be noted, therefore, that X and Y might be large, where possibly Y=1111 1111, in the 8-bit example above. We certainly don't want to square X.

Edit, post-answer: The answer below mentions the built-in count leading zeros function (__builtin_clz()), and that is probably the fastest way to compute the answer. If for some reason this is unavailable, the lengths of X and Y can be obtained through some well-known bit twiddling.

First, smear the bits of X to the right (filling X with 1s except its leading 0s), and then do a population count. Both of these operations involve O(log k) operations, where k is the number of bits that X occupies in memory (my examples are for uint32_t, 32 bit unsigned integers). There are various implementations, but I put the ones that are easiest to understand below:

//smear
x = x | x>>1;
x = x | x>>2;
x = x | x>>4;
x = x | x>>8;
x = x | x>>16;

//population count
x = ( x & 0x55555555 ) + ( (x >> 1 ) & 0x55555555 );
x = ( x & 0x33333333 ) + ( (x >> 2 ) & 0x33333333 );
x = ( x & 0x0F0F0F0F ) + ( (x >> 4 ) & 0x0F0F0F0F );
x = ( x & 0x00FF00FF ) + ( (x >> 8 ) & 0x00FF00FF );
x = ( x & 0x0000FFFF ) + ( (x >> 16) & 0x0000FFFF );

The idea behind the population count is to divide and conquer. For example with 01 11, I first count the 1-bits in 01: there is 1 1-bit on the right, and there are 0 1-bits on the left, so I record that as 01 (in place). Similarly, 11 becomes 10, so the updated bit-string is 01 10, and now I will add the numbers in buckets of size 2, and replace the pair of them with the result; 1+2=3, so the bit string becomes 0011, and we are done. The original bit-string is replaced with the population count.

There are faster ways to do the pop count given in Hacker's Delight, but this one is easier to explain, and seems to be the basis for most of the others. You can get my code as a Gist here..

X=0000 0000 0111 1111 1000 1010 0010 0100 
Set every bit that is 1 place to the right of a 1
0000 0000 0111 1111 1100 1111 0011 0110 
Set every bit that is 2 places to the right of a 1
0000 0000 0111 1111 1111 1111 1111 1111 
Set every bit that is 4 places to the right of a 1
0000 0000 0111 1111 1111 1111 1111 1111 
Set every bit that is 8 places to the right of a 1
0000 0000 0111 1111 1111 1111 1111 1111 
Set every bit that is 16 places to the right of a 1
0000 0000 0111 1111 1111 1111 1111 1111 
Accumulate pop counts of bit buckets size 2
0000 0000 0110 1010 1010 1010 1010 1010 
Accumulate pop counts of bit buckets size 4
0000 0000 0011 0100 0100 0100 0100 0100 
Accumulate pop counts of bit buckets size 8
0000 0000 0000 0111 0000 1000 0000 1000 
Accumulate pop counts of bit buckets size 16
0000 0000 0000 0111 0000 0000 0001 0000 
Accumulate pop counts of bit buckets size 32
0000 0000 0000 0000 0000 0000 0001 0111 

The length of 8358436 is 23 bits

Y=0000 0000 0000 0000 0011 0000 1010 1111 
Set every bit that is 1 place to the right of a 1
0000 0000 0000 0000 0011 1000 1111 1111 
Set every bit that is 2 places to the right of a 1
0000 0000 0000 0000 0011 1110 1111 1111 
Set every bit that is 4 places to the right of a 1
0000 0000 0000 0000 0011 1111 1111 1111 
Set every bit that is 8 places to the right of a 1
0000 0000 0000 0000 0011 1111 1111 1111 
Set every bit that is 16 places to the right of a 1
0000 0000 0000 0000 0011 1111 1111 1111 
Accumulate pop counts of bit buckets size 2
0000 0000 0000 0000 0010 1010 1010 1010 
Accumulate pop counts of bit buckets size 4
0000 0000 0000 0000 0010 0100 0100 0100 
Accumulate pop counts of bit buckets size 8
0000 0000 0000 0000 0000 0110 0000 1000 
Accumulate pop counts of bit buckets size 16
0000 0000 0000 0000 0000 0000 0000 1110 
Accumulate pop counts of bit buckets size 32
0000 0000 0000 0000 0000 0000 0000 1110 

The length of 12463 is 14 bits

So now I know that 12463 is significantly larger than the square root of 8358436, without taking square roots, or casting to floats, or dividing or multiplying.

See also Stackoverflow and Haacker's Delight (it's a book, of course, but I linked to some snippets on their website).

Answer 1

If you are dealing with unsigned int and sizeof(unsigned long long) >= sizeof(unsigned int), you can just use the square method after casting:

(unsigned long long)X * (unsigned long long)X <= (unsigned long long)Y

If not, you can still use the square method if X is less than the square root of UINT_MAX+1, which you may need to hard code in the function.

Otherwise, you could use floating point calculation:

sqrt((double)Y) >= (double)X

On modern CPUs, this would be quite fast anyway.

If you are OK with gcc extensions, you can use __builtin_clz() to compute the length of X and Y:

int length_of_X = X ? sizeof(X) * CHAR_BIT - __builtin_clz(X) : 0;
int length_of_Y = Y ? sizeof(Y) * CHAR_BIT - __builtin_clz(Y) : 0;
return length_of_X * 2 <= length_of_Y;

__buitin_clz() compiles to a single instruction on modern Intel CPUs.

Here is a discussion on more portable ways to count leading zeroes you could use to implement your length function: Counting leading zeros in a 32 bit unsigned integer with best algorithm in C programming or this one: Implementation of __builtin_clz