Assuming your input is too large for the biggest integer type, you have to convert it to a unlimited size integer. For this purpose you can use gmplib. If you are not allowed to use external libraries, you can use a different approach:
- is your string divisible by two (look at the last digit)?
- if yes, write 0 to left side of your output
- else, write 1 to left side of your output
- divide the string by 2 (every digit)
- repeat while string is not filled with 0
I am going to edit this answer, as soon as I wrote the code.
Here you go:
#include<stdbool.h>
#include<stdlib.h>
#include<memory.h>
#include<stdio.h>
typedef struct char_queue {
unsigned int len;
unsigned int capacity;
char* data;
} char_queue;
char_queue init_char_queue() {
return (char_queue) {
0,
4096,
malloc(4096)
};
}
void enqueue(char_queue* queue, char val) {
if (queue->len == queue->capacity) {
char* new_queue_data = malloc(queue->capacity + 4096);
memmove(new_queue_data, queue->data, queue->capacity);
free(queue->data);
queue->data = new_queue_data;
}
queue->len++;
queue->data[queue->capacity - queue->len] = val;
}
char* queue_get_arr(char_queue* queue) {
char* output = malloc(queue->len);
memcpy(output, &queue->data[queue->capacity - queue->len], queue->len);
return output;
}
void free_char_queue(char_queue* queue) {
if (queue->data) free(queue->data);
}
void convert_to_digit_arr(char* input, unsigned int len) {
for (unsigned int i = 0; i < len; i++) {
input[i] = input[i] - '0'; // '5' - '0' = 5
}
}
bool is_null(char* input, unsigned int len) {
for (unsigned int i = 0; i < len; i++) {
if (input[i] != 0) return false;
}
return true;
}
bool divisible_by_two(char* digit_arr, unsigned int len) {
return digit_arr[len - 1] % 2 == 0;
}
void divide_by_two(char* digit_arr, unsigned int len) {
for (unsigned int i = 0; i < len; i++) {
bool is_odd = digit_arr[i] % 2 == 1;
digit_arr[i] /= 2;
if (is_odd && i + 1 < len) { // and is not last (right) digit
digit_arr[i + 1] += 10;
}
}
}
int main(int argc, char** argv) {
for (int i = 1; i < argc; i++) {
unsigned int input_len = strlen(argv[i]);
char* input = malloc(input_len + 1);
strcpy(input, argv[i]);
convert_to_digit_arr(input, input_len);
char_queue queue = init_char_queue();
enqueue(&queue, 0); // null terminator to use the queue content as a string
while (!is_null(input, input_len)) {
enqueue(&queue, divisible_by_two(input, input_len) ? '0' : '1');
divide_by_two(input, input_len);
}
free(input);
char* output = queue_get_arr(&queue);
printf("%s\n", output);
free(output);
free_char_queue(&queue);
}
}
This is not the fastest approach, but it is very simple. Also feel free to optimize it.
