CODEWITHSUNDEEP
calgorithmdata-structures
Hoang Nam
Hoang Nam

Reputation: 548

Bits function in Radix-sort

Radix-sort is the sort keys as the numbers represented in the base of M-number. In order to use Radix sort, I need to understand the bits function. 

unsigned bits(int x, int k, int j)
{ return (x >> k) & ~(~0 << j); }

According to the document I read, it said

It computes the j bits which appear k bits from the right of x.

but it's too short and there is some symbol that I hardly understand (i.e >>, ~ and & ). I made an attempt to test this and it return two value 0 and 1 only. I really need an explanation about this and the real function of it

Upvotes: 0

Views: 102

Answers (1)

chmike
chmike

Reputation: 22174

In the function unsigned bits(int x, int k, int j), x is the value to be sorted, k is the right most position of the bits to extract from x, and j is the number of bits to extract from x.

If you want to do a radix sort with 4 bit values, you would set j to 4 and k to the value 0, then 4, then 8, etc.

The function works as follow. First, it shifts x by k bits on the right. That is done with the expression (x >> k).

The other expression is (~0 << j). The ~0 inverts all the bits of the value 0. This yields a value with all bits to 1. This value is then shifted left by j bits. You then get a value with all bits to 1, and the j right most bits to 0.

This value get all its bits inverted again due to the ~ operator in front of (~0 << j). You then get a value with all bits set to 0 and the j right most bits set to 1.

This value is then combined with an and operation with the result of the first expression x >> k. With an and operation, all bits with zero are forced to zero. Since the second expression had all bits to 0 except the j less significant. The result is that all bits are forced to 0, except the j less significant (right most).

The final result is to return the j bits at offset k in the value x.

If, for instance, the bits of x are 100101001 and k is 3 and j is 3, the result will be 0000000101.

This is the binary equivalent of extracting a digit from a number.

Upvotes: 1

Related Questions