Radix Sort C++ Not masking bits

Question

I have an queue and and an array of queues. buckets is the the array and collector is the queue. pass is an integer that saves which pass it is. I have a method that returns to me the contains of the first cell of the queue called peek(). shiftOne() is a method that moves the head of one queue to the tail of another.

Now this code does not work for me

bucket[((collector.peek()>>(pass * 8)) &0xFF)].shiftOne(collector);

I have gone step by step and it turn out I am not masking the bits properly. I can shift them but that is about it. So I will try to access element 102 for an 10 element array. What am I doing wrong? I know peek() and shiftOne() because I can sort using powers and modulus.

Answer 1

You're confusing radix-10 with radix-2.

Bit shifting is division by 2, so for example: 102 >> 1 = 102 / 2 = 51.
Similarly: 102 >> 8 = 102 / 2^8 = 102 / 256 = 0 (in int terms).

The code (i >> 8) & 0xFF for example is used to extract the content of the second byte of the given i value.

For your case - stick with divisions by 10 with modulus.