Java - 是否存在欧几里德或地面模数的方法

Question

Java模运算符%基于截断的除法(参见Wikipedia:Modulo操作).

• 5%3生产2(注意5/3产生1)
• 5%(-3)生产2(注意5/(-3)产生-1)
• (-5)%3生产-2(注意(-5)/3产生-1)
• (-5)%(-3)生产-2(注意(-5)/(-3)产生1)

在计算科学,给出了两个整数a和n,n> 0,有时是让唯一的整数有用r内[a,n[全等到a模n.

题

Java中有一个有效的泛型运算符/方法,它遵循模数的这个规范吗？

这是为了避免在需要它的每个项目中重写它...

杂

我在stackoverflow上发现了很多关于这个问题的问题,其中大多数都混淆了不同的模数实现.如果您只是对负数的模运算结果感到不安,下面是一些基于Java %运算符的实现可能很有用.

常见的黑客

由于我们几乎不使用负除数,因此该实现返回欧几里得或平均模数n > 0.

static int mod(int a, int n){    
  return a<0 ? (a%n + n)%n : a%n;
}

• mod( 5, 3) 产生 2
• mod(-5, 3) 产生 1

欧几里德模数

static int euclideanModulo(int a, int n){
  return n<0 ? euclideanModulo(a, -n) : mod(a, n);
}

• euclideanModulo( 5, 3) 产生 2
• euclideanModulo(-5, 3) 产生 1
• euclideanModulo( 5,-3) 产生 2
• euclideanModulo(-5,-3) 产生 1

地板模数

static int flooredModulo(int a, int n){
  return n<0 ? -flooredModulo(-a, -n) : mod(a, n);
}

• flooredModulo( 5, 3) 产生 2
• flooredModulo(-5, 3) 产生 1
• flooredModulo( 5,-3) 产生 -1
• flooredModulo(-5,-3) 产生 -2

Answer 1

+----+----+-----------+---------+-----------+-----------+---------+-----------+
| x mod y |           quotient 'q'          |          remainder 'r'          |
| x  | y  | truncated | floored | Euclidean | truncated | floored | Euclidean |
+----+----+-----------+---------+-----------+-----------+---------+-----------+
|  5 |  3 |         1 |       1 |         1 |         2 |       2 |         2 |
| -5 |  3 |        -1 |      -2 |        -2 |        -2 |       1 |         1 |
|  5 | -3 |        -1 |      -2 |        -1 |         2 |      -1 |         2 |
| -5 | -3 |         1 |       1 |         2 |        -2 |      -2 |         1 |
+----+----+-----------+---------+-----------+-----------+---------+-----------+

他们中的任何一个至少满足x = yq + r.

截断分割和模数

static int truncatedDiv(int x, int y) {    
    return x / y;
}

static int truncatedMod(int x, int y) {    
    return x % y;
}

地板划分和模数

java.lang.Math从Java 8 开始,您可以使用方法.请参阅floorDiv和floorMod.

static int floorDiv(int x, int y) {    
    return Math.floorDiv(x, y);
}

static int floorMod(int x, int y) {    
    return Math.floorMod(x, y);
}

欧几里德分裂和模数

a)基于截断的划分

import static java.lang.Math.*;

static int euclideanDiv(int x, int y) {
    int r = x / y;
    // if the divident is negative and modulo not zero, round down for positive divisor, otherwise round up
    if (x < 0 && r * y != x) {
        r -= signum(y);
    }
    return r;
}

static int euclideanMod(int x, int y) {
    int r = x - euclideanDiv(x, y) * y;
    return r;
}

b)基于地板划分

import static java.lang.Math.*;

static int euclideanDiv(int x, int y) {
    int r = floorDiv(x, y);
    // if the divisor is negative and modulo not zero, round up
    if (y < 0 && r * y != x) {
        r++;
    }
    return r;
}

static int euclideanMod(int x, int y) {
    int r = x - euclideanDiv(x, y) * y;
    return r;
}

c)基于绝对模数

import static java.lang.Math.*;

static int euclideanMod(int x, int y) {
    int r = abs(x) % abs(y);
    // apply the sign of divident and make sure the remainder is positive number
    r *= signum(x);
    r = (r + abs(y)) % abs(y);
    return r;
}