Alejandro - 1 year ago 69
C Question

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

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.

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

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download