Implementation of +,-,*,/ with bitwise operator

There is a question asked on Stackoverflow : Divide a number by 3 without using *,/,+,-,% operators. This question is an Oracle interview question. Some people give excellent answers. You can go there and take a look. Usually we need to use bitwise operators to do this kind of implementations. Here I want to show you ways to implement +,-,*,/ with bitwise operators.

A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. It is a fast, primitive action directly supported by the processor, and is used to manipulate values for comparisons and calculations. On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition. While modern high-performance processors usually perform addition and multiplication as fast as bitwise operations the latter may still be optimal for overall power/performance due to lower resource use. Some bitwise operators used frequently are <<(left shift),>>(right shift),~(complement),^(xor).

Come back to the implementation:

1. Add

int add(int x,int y){
    int a,b;
    do{
        a=x&y;
        b=x^y;
        x=a<<1;
        y=b;
    }while(a);
    return b;
}

The positions that generate a carry and the positions that don’t generate a carry. In each run, the newly generated carrys will be added to the corresponding positions.

2. Subtraction

int negate(int x){
    return add(~x,1);
}

int sub(int x,int y){
    return add(x,negate(y));
}

We can use the addition function implemented above here, first we implement how to get a negative number of a positive number. The ~x is to get the 1's complement of x and then by adding 1, we get the 2's complement number. This number will be the negative number of x.

Ok, then substration is just a number adds another number's negative number.

3. Multiplication

int mul(int x, int y){
    int m=1, z =0;
    if(x<0){
        x=negate(x);
        y=negate(y);
    }

    while(x>=m && y) {
        if (x &m) z=add(y,z);
        y <<= 1; m<<= 1;
    }
    return z;
}

The detail explanation for this implementation can be found in :Adding Two Numbers With Bitwise and Shift Operators. Here if x<0, we need to convert it to a positive number, otherwise, the result will be 0.

4. Division

int divide(int x,int y){
    int c=0,sign=0;

    if(x<0){
        x=negate(x);
        sign^=1;
    }
    
    if(y<0){
        y=negate(y);
        sign^=1;
    }

    if(y!=0){
        while(x>=y){
            x=sub(x,y);
            ++c;
        }
    }
    if(sign){
        c=negate(c);
    }
    return c;
}

If both x and y are positive numbers, then we will going to a while loop. Basically, what the loop does is to subtract y from x if x>=y, the loop will end until x

Note : The addition and multiplication implementations are from : Adding Two Numbers With Bitwise and Shift Operators.