50174. Bubble Sort

I'm a slow walker, but I never walk backwards.

Task Description

This task is to implement a bubble sort within a 64-bit unsigned integer. A 64-bit unsigned integer has 64 one or zero, each of them is just a key to be sorted. You need to do a bubble sort on these 64 bits so that all zeros go to the left (most significant bits) and all ones go to the right (least significant bits). As a result, you can focus on the bit pattern 10, which should be switched to 01. All the other patterns, i.e., 01, 00, and 11, do not change.

There are 63 steps for doing a bubble sort on a 64-bit unsigned integer. In every step you scan the bits from left to right, one at a time, change all 10 into 01. In order to confirm the correctness of your bubble sort, please output the result in every step. Please refer to the following animation for a single step.

bubble sortbubble sort

Write the bubble sort in a function.

#include <stdint.h>
void BubbleSort(uint64_t input, uint64_t output[63]);

The first argument ‘input’ is the unsigned 64-bit integer for bubble sort. The second argument ‘output’ is an array to store the 63 output results.

Note that you cannot use ‘%’ in your program. Otherwise, you will get compile error.

You can use the following main function to test your program.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include "BubbleSort.h"
#define N 63
int main(){
    uint64_t input;
    uint64_t output[N];
 
    scanf("%I64lu", &input);
    BubbleSort(input, output);
    for(int i = 0; i < N; i++)
        printf("%" PRIx64 "\n", output[i]);
    return 0;
}

Input Format

Some unsigned 64-bit integers.

Output Format

Output the results of 63 steps of all inputs, which in hexadecimal.

Sample Input 1

123456

Sample Output 1

Sample output 1

Sample Input 2

3457332117740902599

Sample Output 2

Sample output 2

Discussion