欧几里德分部的位补码运算符

Question

没有回答这个问题.

我了解到,给定两个整数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);
}

在阅读了上面的代码之后,我很明白,如果(n> = 0){}块代码逻辑我们正在做真正的除法而不是欧几里德.

但是,使用位补码运算符(〜)的其他{(n <0)}代码逻辑对于理解使用〜运算符背后的思维方法并不明显.一般在考虑分割的时候使用>>运算符.

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

我的问题是:

我想理解思考方法,我怎么能想到使用位补码运算符(〜)它可以帮助你在n <0时执行欧几里德分割.因为我不习惯使用〜运算符.请帮助我调整我的方法.

Answer 1

~n是-n - 1.

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

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