Representation in binary
For 32/64 bit, Sign binary in 31/63 bit with MSB is sign bit or Unsign binary in 32/64 bit.
Converting to binary
Modular operation is used to convert numbers in decimal form to binary form.
Modulating against n Power of 2 (n:1-32/64) NOT (n:0-31/63)
For example, 2135534156 will be mod against 2, 4, 8......2^32 (2^33 might be used to test if number is overflow)
Negative number representation
Goal: the sum of negative number and its positive counterpart is zero in binary form
Process:
1) Get the binary form of the positive counter part and do overflow check
2) convert the binary form of positive counter part to its 2's complement way,
Total subtraction: 2^16/2^32/2^64- binary
compliment and then plus 1: ~binary +1
3) leave the sign bit to 1
For example: 4 bit system, 7 = 0111, -7 =1001 0111+1001 = 0000, carry bit discounted
Expansion
Multiplication
Summation on Left shifting, e.g. 111 *101 = 1*(111<<2^1)+ 0*(111<<2^0)+ 1*(111)
Shifting n bit is equivalent multiplied by 2^n
Summary: M shift and summation where M is the number of digits in multiplier.
Division
Division is rather complicated, comparing to Multiplication. The most naive one is shift-and-subtract,
which is much simpler version of the conventional divide-and-subtract for decimal number.
Reminding decimal divide-and-subtract:
1) Divisor on the left of dividend
2) Start from the Nth digit from the left most, which N is the number digits Divisor has
3) Test and get the biggest multiple of divisor against the dividend portion,
and set the corresponding digit in the quotient
4) Subtract the multiple of divisor from the Dividend, and move onto next digits
How about binary shift-and-subtract:
there is Step3's test and get the biggest multiple of divisor testing,
the quotient digit is either 0 or 1 (the dividend portion always either smaller or bigger than divisor)
Summary: M-N shift and Subtraction, M is the number of digits in Dividend and N is the number digits of Divisor
http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
Any better way if divisor is decimal?
Divided by Tens using Multiplication and Right Shift
For integer smaller than 2^16, 23456/10 = 23456*52429>>>19;
52429 = 2^19/10 = 524288/10;
2^4/10 = 16/10 = 1.6
2^8/10 = 256/10 = 25.6
2^10/10 = 1024/10 = 102.4
2^16 /10 = 65536/10 = 6553.6 <= 1100 1100 1101 0
2^18 /10 = 262144/10 = 26214.4 = 1100 1100 1100 110
2^19/10 = 524288/10 = 52428.8 <= 52429 = 1100 1100 1100 1101
2^20/10 = 1048576/10 = 104857.6
2^19/10 is the highest resolution we could choose as a multiplier
Summary:
2^16/10 needs 12 shift and 12 subtraction using shift and subtract vs 10 shift and 9 summation
http://www.tofla.iconbar.com/tofla/arm/arm02/index.htm
Modular
Modular result = the original - quotient*divider.
Rounding Error: to the lowest instead of to the nearest
Exponential
Square-Multiply method
Exponent in binary: Sum(2^i)(i=0:n);
A^B: Prod(B^(2^i))(i=0:n)
For example, x^11 = x^1011 = x^1*x^2*x^8
Addition-Subtraction method