Java - 是否有欧几里得或向下取整模运算的方法？

Question

Java - 是否有欧几里得或向下取整模运算的方法？

javaoperatorsmodulomodulusnegative-number

14

Java 取模运算符 % 基于截断除法（参见维基百科：模运算）。

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

- boumbh

你可能已经看过了，但是你可以很容易地使用 Math.floor()（JavaDocs）将值向下取整（最接近的整数）。 - classicjonesynz

2

@Killrawr，Math.floor()比上面任何一种解决方案都要差。 - UmNyobe

@Killrawr a - n * (int)Math.floor((double)a/n); 在数学上是正确的，用于向下取整的模运算，但不是高效的，也不是通用的。 - boumbh

@boumbh 您希望表现如何？(-5)magicmod(-3)应该返回什么？ -2 还是 2？ - UmNyobe

是的，可以使用循环数组 array[mod(i++, array.length)]。这不是一个紧急问题，更像是我“个人修养”的好奇问题。 - boumbh

显示剩余5条评论

2个回答

-1

这段代码怎么样？

public static int gcd(int p, int q) {
    if(count == 0) 
        System.out.print("Gcd for " + p + " and " + q);
    if (q == 0) {
           System.out.println(" returns " + p + " after " + count + " iterations");
        return p;
    }
    count++;
    return gcd(q, p % q);
}
public static void main(String[] args) {
    count = 0;
    gcd(4, 16);
    count = 0;
    gcd(4, 16);
    count = 0;
    gcd(16, 4);
    count = 0;
    gcd(15, 60);
    count = 0;
    gcd(15, 65);
    count = 0;
    gcd(1052, 52);
}

- TheWhiteRabbit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vlastimil Ovčáčík · Accepted Answer

无论哪种情况都至少满足 x = yq + r。

截断除法和取模

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

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

向下取整除法和模数

自Java 8以来，您可以使用java.lang.Math中的方法。请参见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;
}

基于向下取整除法

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;
}

基于绝对模数

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;
}