Method add mod 2 ^ 512
It adds modulo 2 ^ 512. Could you please explain to me why we are doing → 8 here and then & oxFF? I know that I am not good at math.
int AddModulo512(int []a, int []b)
{
int i = 0, t = 0;
int [] result = new int [a.length];
for(i = 63; i >= 0; i--)
{
t = (a[i]) + (int) (b[i]) + (t >> 8);
result[i] = (t & 0xFF); //?
}
return result;
}
source to share
It looks like you have 64
int
in each array, but your math is mod 2 ^ 512.512 divided by 64 is 8, so you only use the least significant bits 8
in each int
.
t
Used here to store intermediate result, which may be longer than a 8
bit.
The first loop t
is 0
, so it doesn't appear in the appendix in the first statement. Don't wear anything yet. But adding can result in a value that needs more than a 8
bit to store . Thus, the second line masks the least significant bits 8
to store in the current array of results. The result remains unchanged for the next cycle.
What does the previous value do t
in the next iteration? It performs a carry function in addition. Bit-shift right at positions 8
makes any bits higher than 8 in the previous loop result to carry to the current position.
Example: just 2-element arrays to illustrate wrapping:
[1, 255] + [1, 255]
First cycle:
t = 255 + 255 + (0) = 510; // 1 11111110
result[i] = 510 & 0xFF = 254; // 11111110
It & 0xFF
only accepts the least significant 8 bits here. Similar to normal math, 9 + 9 = 18, but in the problem of adding many numbers we say "8 carry 1". The bitmask here performs the same function as extracting "8" from 18.
Second loop:
// 1 11111110 >> 8 yields 0 00000001
t = 1 + 1 + (510 >> 8) = 1 + 1 + 1 = 3; // The 1 from above is carried here.
result[i] = 3 & 0xFF = 3;
>> 8
retrieves the possible carry value. Similar to normal math, 9 + 9 = 18, but in the problem of adding many digits, we say "8 carry 1". Offsetting the bits here performs the same function as extracting "1" from 18.
Result [3, 254]
.
Note that ignoring the remainder from the last iteration ( i == 0
) is ignored. This implements a unit of 2 ^ 512. Any carry over from the last iteration is 2 ^ 512 and is ignored.
source to share
The mathematical effect of a bitwise shift to the right (→) by an integer is equal to division by two (truncating any remainder). By moving the right 8 times, you are dividing by 2 ^ 8 or 256.
Bitwise and with 0xFF means the result will be limited to the first byte or the range 0-255.
Not sure why it is referring modulo 512 when it actually divides by 256.
source to share
→ - bit shift.
The written left shift operator "<shifts a bit to the left, and the signed right shift operator" → "shifts the bit pattern by correct. The bitmap is given by the left operand, and the number of positions to shift along the right operand. Unsigned right shift operator" →> "shifts zero to the far left position, and the far left position after "→" depends on the sign extension.
& is different and
The bitwise and operator performs a bitwise AND operation.
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
http://www.tutorialspoint.com/java/java_bitwise_operators_examples.htm
source to share
I think your question is missing a very important role - the data format, ie how the data is stored in [] and b []. To resolve this issue, I make some assumptions:
- Since it is modulo arithmetic, a, b <= 2 ^ 512. So a and b have 512 bits.
- Since a and b have 64 elements, only the 8 right-most bits of each element are used. In other words, a [i], b [i] = 256.
Then what remains is very simple. Just consider each a [i] and b [i] as a digit (each digit is 8 bits) in the base addition of 2 ^ 512, and then do the addition by adding the numeric digit from right to left.
t is a carry variable that stores the value (with carry) of addition at the last digit. t>>8
gives the path to the very 8 bits that were used for the last addition, which is used as a carry for the current addition. (t & 0xFF)
gets the right-most 8 bits of t, which are used for the current digit.
Since it is modulo addition, the final carry is discarded.
source to share