Multiplication and addition through binary operations
|
In order to get more comfortable using bitwise operators such as & | ^ ~ in the course Advanced C++ 2 for games, we received our first sub-assignment. Performing multiplication and addition through binary operations only. For addition we used the follow algorithm:
We have two integers, 39(0010 0111) and 23(0001 0111). 1. Perform XOR on them and store the results in a new integer we call sum. This will compare the bits of the integer and return a value were the bits are 1 and 0 in the other. Since this is not enough, we also have to… 2. Perform AND on them and store this value in another integer we call carry, as this will return 1 on all bits that are 1. 3. And finally bit shift our carry one step to the left and repeat these steps until the carry becomes zero. This is implemented through code in the following way
typedef __int64 int64;
int64 Add(int64 a, int64 b){
int64 iA=a;
int64 iB=b;
int64 sum=iA^iB;
int64 carry=iA&iB;
carry<<=1;
while(carry!=0){
iA=sum;
iB=carry;
sum=iA^iB;
carry=iA&iB;
carry<<=1;
}
return sum;
}
To perform bitwise multiplication we came to the realization that we were required to use addition in some form, preferably using our previously constructed function. This because after extensive research we used the Russian Peasant Multiplication algorithm but using bits, in a manner similar to this: 1101 = 13
int64 Muln(int64 a,int64 b){
int p;
for(p=0;a;a>>=1,b<<=1){
if(a&1)p=Add(p,b);
}
return p;
}
The following
if(a&1)p=Add(p,b);
checks if the given value is 1 or 0 in bits, similar to performing a modulo operation and since we don’t want to multiply if the value is 0 we use this opportunity to call our add function whenever this is true. This will continue for as long as a is larger than 0, then we return p. |
