Thread: Exercise: Implement Addition Operator for a char array

Hey,

I am wondering if and how exactly you can implement addition by 1 in C without using the + or ++ Operator. (As an exercise)

Given a pointer to an array of unsigned chars you have to treat this array as a number and increase it by 1. The maximum length (also represented as a char array with length 4) of the array is 2^32 -1. (Therefore unlimited to every computer produced by a human). If all elements of the array are one, you have to create a new array and set the first char to 1 and increase the length (treated as a number) by 1.

You are not allowed to use any other type but char and it is forbidden to use any operator but &,|, ==, !=, =, >>, <<, <=,<,>,>=. You are allowed to use the sizeof operation, but you have to convert the output to an array of char if you would like to use the output. Every kind of loop is allowed and of course the if-else statment is allowed.

Personally, I cannot find a way to go around the +,++ operation, but then it would be solvable.
Personally I can't define the addOne function without the necessity of ++ or + or the addOne function itself.

I added my terrible code below, it is not working and it is really eye cancer;

Code:

/*Required Headers*/
#include <stdio.h>
#include <stdlib.h>




void intToCharArray(int lenint, char buf[]){
        buf[0] = (char)(lenint);
        buf[1] = (char)((lenint >> 0b1000));
        buf[2] = (char)((lenint >> 0b10000));
        buf[3] = (char)((lenint >> 0b11000));
}


char equalArr(char one[], char two[], char length){
    for(char i= 0; i < length; i++){ //this is not allowed
        if(one[i] != two[i])return 0;
    }
    return 1;
}


void  SetBit(char A[],  int k ){
      A[k/32] |= 1 << (k%32);  [I]// Set the bit at the k-th position in A
}


char add(char count, char reminder){
    return count+add;
}


//"expand" allows resizing
void addone(char arr[], char length[], char expand){
    //Check if array has to be resized
    char lengthoflength = 0b100;
    if(expand){
        char allOne = 1;
        char counter[4] = {0,0,0,0};
        while(!equalArr(counter, length, 4)){
            if(arr[((int)(counter))] == 0b11111111);
        }
        if(allOne){
            addone(length,lengthoflength,0);
            arr = malloc((int)(*length)); //is there any way around it?
        }
    }


}


int main(){
    char *arr = (char*)malloc(1); //number to be increased,
    char arrlen[4] = {255,255,255,255};
    char cmpt[] = "Y\n\0";


    while(1){
        char input[3];
        printf("Add 1 to the number?\n"); // Just use I/O, allow non-chars...
        fgets(input, 3, stdin);
        if(strncmp(input,cmpt,3))break; //end allowing non-chars


        int lenint = (int)(sizeof(arr)); //make size_t to char array, since we are not allowed to use other types...
        intToCharArray(lenint,arrlen);


        addone(arr, arrlen,1);
    }
}

There's a lot of detail missing from your description. Is there an online description? And can you use ~ (bitwise complement) ?


BTW, 2^32-1 is only 4,294,967,295, which is certainly not "unlimited to every computer produced by a human". You are probably were thinking of 2^64-1 which is 18,446,744,073,709,551,615.

And I don't think 0b... is standard C. Probably better to use 0x...

The details are too arbitrary and ill-defined for my taste.
Good luck.

Originally Posted by john.c

BTW, 2^32-1 is only 4,294,967,295, which is certainly not "unlimited to every computer produced by a human".

It is though, because that means that the max integer that can be represented would be 2^(8 * (2^32-1))-1.

I am wondering if and how exactly you can implement addition by 1 in C without using the + or ++ Operator.

You probably would benifit looking at how addition is done with "binary addition".

This uses logic gates to complete addition (& | ^)