C++ Radix Sort - Bitshift Operators

[spool]

Hay guys,

I was looking at a few examples of how a Radix sort works, and writing up a document explaining it. I based my findings on one particular example I found, link follows.

http://www.cubic.org/docs/radix.htm

Well the bit shifting here is giving my head a bit of a spin, and I was wondering if someone could lay it out on the table for me so I can understand. I know what he is doing, he gets the key he is sorting and looks at the ones column, then continues, second pass he bit shifts the key by 8 bits, and so on up to 24 bits on the last pass. The following bit of code though I need a bit of help on.

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

Now with this line,

for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];

Could someone please run a number through it and show me step by step how it is actually getting the ones column, tens, hundreds and so on. I also have no clue to what the, ")&0xff" is doing.

Thanks in advance for any help!

[Rashakil Fol]

This code only works on one column, that's why you see the radix function called four times.

And it's not working on the ones, tens, hundreds columns, it's working on the first, second, third, and fourth bytes.

0xff is the number 255, and & does a bitwise 'and' operation. Look at the number 255 in binary and you'll see what bitwise anding with 255 does.

[spool]

The problem with the 0xFF is that, I know its 1111 1111 thats the problem, say we take the number 0010 0011 1000 which is 568, do a bitwise shift on it then logical & it the logical and isn't doing anything. e.g.

...001000111000 >> 4
...000000100011 &0xFF
...111111111111
= 000000100011 (this is the same before we did the &)

Thats why I have no idea why its there? I might be getting the wrong idea and if I am someone please correct me.

In other terms, would someone be able to take the number 568, and show me how to get the 6 in column 2 please.

Thanks =)

[Narue]

>Thats why I have no idea why its there?
It's there because a right shift may or may not fill the vacated bits with zeros. If the type of source is signed, the implementation could fill the bits with zeros (a logical shift) or the value of the sign bit (an arithmetic shift). The AND operation forces the same result as a logical shift, even if an arithmetic shift was performed.

[rezzy1]

The problem with the 0xFF is that
--

Note the original comments by the maker of this original code --

"I know, real programmers code in assembly"

Yep, so sorry if you don't understand the Radix sort it was made to impress, not to be readable.