java - 欧氏除法中的位补运算符

Question

https://math.stackexchange.com/questions/679146/euclidean-divison-program

没有回答这个问题。

我了解到，给定两个整数 a 和 b，且 b ≠ 0，存在唯一整数 q 和 r 使得 a = bq + r 且 0 ≤ r < |b|，其中 |b|表示b的绝对值 - 定义欧氏除法

实现该逻辑的对应程序如下所示:

int ifloordiv(int n, int d){

if (n >= 0)
    return n / d;
else
    return ~(~n / d);
}

看完上面的代码，我很明显地理解了 if(n>=0){} block 代码逻辑，我们正在做真正的除法而不是欧几里德。

但是，else{(n<0)} 使用位补码运算符 (~) 的代码逻辑在我看来并不明显，无法理解使用 ~ 运算符背后的思维方法。一般我们想到除法都会用到>>运算符。

我知道 java ~ 运算符是整数类型的 1 的补码运算符。

我的问题是:

我想了解一下思考方法，我怎么能想到使用位补运算符(~)来帮助你在 n<0 时执行欧氏除法。因为考虑使用 ~ 运算符对我来说并不明显。请帮我调整我的方法。

Answer 1

~n 是 -n - 1。

所以 ~(~n/d) 是 -((-n - 1)/d) - 1。

对于 n 的负值和 d 的正值，结果是向下舍入的除法(除法通常向零舍入，所以对于负值向上舍入n)。我无法解释为什么会这样。