Thread: Bitwise mask and manipulation...

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    22

    Bitwise mask and manipulation...

    Hi all, Im trying to learn radix sorting here. I found this nice sample code. While trying to undestand the code i have a few doubts.
    Can you explain what the coder has done?
    Code:
    #include <iostream.h>
    #include <stdlib.h>
    #include <string.h>
    
    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]; // Doubt 1.
    }
    
    void radixsort (long *source, long *temp, long N)
    {
      radix (0, N, source, temp);
      radix (1, N, temp, source);
      radix (2, N, source, temp);
      radix (3, N, temp, source);
    }
    
    void make_random (long *data, long N)
    {
      for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16);
    }
    
    long data[100];
    long temp[100];
    
    void main (void)
    {
      make_random(data, 100);
      radixsort (data, temp, 100);
      for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
    }
    In function radix i have marked the dount. Can you explain why the coder has used this sentence"?
    for ( i=0; i<N; i++ )
    {
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
    }

    in particular - whats right shift operator doing and why is & doing here .. which is incremented here?
    would help me understand it better
    thank
    regards
    KR

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Why not split it out into several statements?

    Code:
    temp = ((source[i])>>(byte*8))&0xff;
    dest[index[temp]++] = source[i];
    Then you can at least print the sub-expressions and learn what is going on.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    22
    thanks i tried that.. all i need to know is how is he sorted the numbers using the shift operators and & instead of using place value notation in this sorting...
    i hope you understood what im saying... i would be greatful if some1 explained..
    thanks
    regards,
    KR

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > (source[i])>>(byte*8)

    If source[i] contains say 0x12345678, then depending on the value of byte, you would get 0x12, 0x34, 0x56 or 0x78.

    The &0xff is to ensure that the result is just one byte.
    0x12345678 >> 8 is 0x00123456.
    Masking with 0xff leaves you with just 0x56

    Exactly how/why this implements a radix sort is another matter.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bit manipulation
    By dsupriya in forum C Programming
    Replies: 8
    Last Post: 03-05-2009, 09:36 AM
  2. Bitwise (need help not answer)
    By MSF1981 in forum C Programming
    Replies: 5
    Last Post: 02-12-2009, 01:28 PM