CS1101C Lab 1 (Even Week)

Bit Sorting

The name of your C program file must be called sort.c, files with any other name will not be marked.

Preliminary

Suppose we have a 4-bit binary string (i.e. a string consisting only of 0s and 1s) such as "0110", sorting the binary string simply means to rearrage the bits such that it runs in ascending order (i.e. "0011"). As another example, sorting "1101" produces "0111" in ascending order.

The Task

Write a program sort.c that accepts a 4-bit binary input string and rearranges the bits to produce the output in ascending order. The following sort.c program has been provided for you that reads in the input. Your task is to simply extend the program to generate and print out the sorted output.

/**********************************************************************/
/* Matric Number: U051234A and U059876B                               */
/* Userid: u0501234 and u0509876                                      */
/* (For those doing pair programming, only ONE of you should submit   */
/*  your program. The other student should NOT submit.)               */
/* Lab: 1                                                             */
/* Lab Group Number: 99                                               */
/* Lab TA's Name: Who needs a lab TA when you're Bill Gates?          */
/* Lab Session Date: 20 September 2006                                */
/* Lab Session Time: 0800 - 0945                                      */
/* Title: Bit Sorting                                                 */
/* Purpose: Perform 4-bit sorting in ascending order.                 */
/**********************************************************************/

#include <stdio.h>

int main()
{
    /* Variable declaration.
       You can declare any other variables here. */
    int input;

    /* Get user input. */
    printf("Enter 4-bit binary  : ");
    scanf("%d", &input);

    /* Generate and print sorted output here. */

    return 0;
}

Assuming that the executable is sort, a sample run of the program is shown below. User input is denoted in bold.

$ gcc -Wall sort.c -o sort
$ ./sort
Enter a 4-bit binary : 0110
Sorted 4-bit binary  : 0011

$ ./sort
Enter a 4-bit binary : 1101
Sorted 4-bit binary  : 0111

$ ./sort
Enter a 4-bit binary : 0010
Sorted 4-bit binary  : 0001

$ ./sort
Enter a 4-bit binary : 0000
Sorted 4-bit binary  : 0000

$ ./sort
Enter a 4-bit binary : 1111
Sorted 4-bit binary  : 1111

$ ./sort
Enter a 4-bit binary : 1001
Sorted 4-bit binary  : 0011

$ ./sort
Enter a 4-bit binary : 1100
Sorted 4-bit binary  : 0011

$ ./sort
Enter a 4-bit binary : 0011
Sorted 4-bit binary  : 0011

$

Points to Note

• For simplicity, we assume that user input will always be within the range of permissible values, so there is no need to perform any explicit checks on the data entered by the user.
• Do not use any other data types except int. That means you are not allowed to use double, float, char, etc. You are only allowed to use the int data type and nothing else.
• The only conversion specifier allowed within printf statements is strictly %i (or %d).
• Do not use any field-width specifiers with scanf or printf. E.g. You are not allowed to use scanf("%4d", &input); or printf("%04d", input);
• Do not use any logical (&&, ||, !) or bit-wise (&, |, ^, !, <<, >>) operators.
• Do not use any selection statements (if, if-else, switch), repetition statements (while, do-while, for), nor the conditional operator "?:".
• Do not use any functions from the math library.

Questions to Ponder

• Why do we use %d instead of %i in the scanf statement?
• In the sample output shown above, why do we invoke our program with the command ./sort rather than sort?

A total of 10 different hosts have accessed this document in the last 445 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 5 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.