Alejandro - 1 year ago 51

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`

`Y=0111 0000`

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`

`range`

`RAND_MAX/range`

`range`

`RAND_MAX`

`RAND_MAX/range`

`range`

It should be noted, therefore, that X and Y might be large, where possibly

`Y=1111 1111`

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`

`01`

there are 0 1-bits on the left, so I record that as

`01`

`11`

`10`

`01 10`

numbers in buckets of size 2, and replace the pair of them with the result;

1+2=3, so the bit string becomes

`0011`

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 Source

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