Rarely, but still, tasks from interviews and trainings are of practical value. So, I needed to implement in Java an alternative to arithmetic operations on integer values. Fortunately, the first pages of search engines are full of ready-made solutions for bitwise analogs, and you didn't have to break your head over most of them.
To be honest, I was somewhat surprised at the lack of such material on Habré (did I look badly?), And therefore decided to make up for this deficiency, with my comments and additions.
Please note that in the examples with bitwise operations, the values are truncated to a nibble: there will be no fundamental difference, but easier to understand.
Addition
Algorithm:
private int add(int summand, int addend)
{
/*.*/
int carry = 0x00;
/* , .*/
while(addend != 0x00)
{
/* .*/
carry = (summand & addend);
/* , .*/
summand = summand ^ addend;
/* .*/
addend = (carry << 1);
}
return summand;
}
First you need to remember about the transfer to the senior category. In the decimal system, its definition (for the current digit) includes values in the range from 10 to 18:
109 +
019 =
128
In the binary system, everything that is greater than one is transferred:
0001 +
0001 =
----
0010
or like this:
0011 +
0011 =
----
0110
In the last example, the least significant bits are added first:
1 + 1 = 10 ()
Zero remains in the current bit, and the one goes to the most significant one, where it participates in addition:
1 + 1 + 1 = 11 ()
the lowest one remains in the current one, the older one moves further. From here, you can deduce the rule that in the binary system for one current bit, values from two to three, inclusive, fall under the carry.
In the part concerning the algorithm, it is worth paying attention to the instruction for determining the presence / absence of transfer using the example of previous values:
carry = (summand & addend);
0011 = 0011 & 0011
This is not a transfer yet, but the setting of "flags" over the digits, the addition of which leaves the transfer, i.e. add carry is when the bits are the same.
As soon as something has already cleared up, now the first term should be freed from the bits for which the transfer is taken into account:
summand = summand ^ addend;
0000 = 0011 ^ 0011
As you know, the bitwise XOR operator will set bits only if the bit values are opposite.
The third step in the loop is to convert the carry flags directly into a carry. To do this, they are shifted one step to the left and assigned to the second term:
addend = (carry << 1);
0110 = (0011 << 1);
At the next iteration, the transfer will not be fixed, because:
carry = (summand & addend);
0000 = 0000 & 0110
The second step will give us:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Which is the desired sum, and the third step will end the while () loop:
addend = (carry << 1);
0000 = (0000 << 1)
Subtraction
Algorithm:
private int sub(int minuend, int subtrahend)
{
/* .*/
int borrow = 0x00;
/* , .*/
while(subtrahend != 0x00)
{
/* .*/
borrow = ((~minuend) & subtrahend);
/* , .*/
minuend = minuend ^ subtrahend;
/* .*/
subtrahend = (borrow << 1);
}
return minuend;
}
Equivalent to the previous one, with the only difference that the borrowing of bits from the most significant bits is implemented inverse implication inversion . Well, we rename the local variables.
Multiplication
Algorithm:
public int multiply(int mul1, int mul2)
{
int result = 0;
/* .*/
while(mul2 != 0)
{
/* ...*/
if ((mul2 & 1) == 1)
{
/* .*/
result = add(result, mul1);
}
/* ("")*/
mul1 <<= 1;
/* if()*/
mul2 >>>= 1;
}
return result;
}
Back to basics: long multiplication in decimal system:
25 *
05 =
--
125 +
00
---
125
those. we multiply each digit of the second factor by the first factor. From here it follows that the product from the most significant bit is shifted one step to the left. Finally, add the intermediate values. The same thing happens at the bitwise level:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
We conclude that the algorithm only has to, that adding the first factor to itself every time the set bit is encountered in the second factor, naturally, taking into account the rule for transferring to the most significant bit:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
Then the first multiplier is shifted one bit to the left (we form a "ladder"):
mul1 <<= 1; //1100 = 0110 << 1;
Now we determine if there is a bit in the second most important bit of the second factor:
mul2 >>>= 1; //0001 = 0011 >>> 1;
The cycle runs until the second factor is zero. I would like to draw your attention to the following: an instance of this algorithm walks from resource to resource, where the logical shift of the second factor (mul2 >>> = 1) is replaced by an arithmetic one (mul2 >> = 1) . It probably originates from the implementation in C / C ++, where there is the unsigned keyword and this substitution is not a problem. However, in Java all types of numbers are signed, and if the second factor is represented by a negative value, then such an oversight will lead to the algorithm falling out into an infinite loop, since the second factor will always meet its condition:
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
Division
Algorithm:
private int divide(int dividend, int divisor)
{
/*, .*/
int quotient = 0x00, mask = 0x01;
/* .*/
int temp = divisor;
/* .*/
int sign = ((dividend < 0)^(divisor < 0)) ? sign = -1 : 1;
/* .*/
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
/* 0 .*/
if (dividend < divisor) return quotient;
while(dividend > 0 || divisor != 0)
{
/* .*/
if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
{
divisor <<= 0x01;
mask <<= 0x01;
}
/* .*/
else
{
/* "" .*/
quotient = quotient | mask;
/* .*/
dividend = sub(dividend, divisor);
/* .*/
divisor = temp;
mask = 0x01;
}
}
return multiply(quotient, sign);
}
The division did not work out as smoothly as with the previous examples: I had to write a bicycle (not hit hard).
Division is the subtraction of the divisor from the dividend as long as the quotient is greater than or equal to zero. With this approach, it is sufficient to define a counter, the value of which is incremented after each subtraction operation. Its final value is the particular:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
The disadvantage of this approach becomes especially noticeable when supplying a device with limited resources of sequence of instructions, such as: 2147483647/1; 2147483647/2; 2147483647/3 , it looks like the application is frozen.
Working at the bit level would be much more efficient. But the only solution found has the disadvantage that for correct inference, the type of variables is required, one step above the covered range, i.e. if the input is short , then the type of local variables must be int , otherwise the result of dividing large values will be surprising. In my case, the situation was aggravated by the absence of the long type.
But back to our rams.
To understand how the algorithm works, you need to remember the column division order:
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
Here in more detail. At the exhaust, we got the following: we "pushed" the divider to the left up to the discharge where it minimized the difference with the divisible:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
This mechanism is implemented in the algorithm. In a while () loop, the divisor must be shifted to the left until it satisfies the above rule. In parallel with it, the private mask is shifted. The branching operator if () says: "You can move if only the result of this operation does not violate the basic rule." An additional check for a negative number is due to the fact that in Java, the most significant bit set is a negative number. Without it, the cycle will fall to infinity:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
As soon as the algorithm stops meeting the if () conditions, the code enters the else, where the mask bit is set on the quotient:
quotient = quotient | mask;
0010 = 0000 | 0010
This is the same as setting the bits for long division. Then the divisor is subtracted from the dividend:
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
After that, the divider and the mask return to their original state and the cycle starts again:
divisor = temp;
mask = 0x01;
Finally, I would like to add a few words about additional code.
The above algorithm assumes division only of positive numbers that are obtained by the complementary code:
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
Here the following happens: if the number is negative, then its bits are inverted, and the result is added with one and we get a positive (absolute) value. The same rule applies to positive numbers, for example:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
But there is one exception - this is the largest negative number of a given type, for example:
int -2147483648 ->
~1000 0000 0000 0000 0000 0000 0000 0000 =
0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000.
Be careful.