bit complement operator in euclidean division

Question

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

did not answer this query.

I learnt that, Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b - Definition euclidean division

Corresponding program that implements this logic is as shown below:

int ifloordiv(int n, int d){

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

After reading the above code, It look obvious for me to understand if(n>=0){} block code logic that we are doing real division not euclidean.

But, else{(n<0)} code logic using bit complement operator(~) was not looking obvious to me to understand the thinking approach behind usage of ~ operator. Generally we use >> operator when we think of division.

I know that java ~ operator is 1's complement operator on integral types.

My question is:

I would like to understand the thinking approach on, How can i think of using bit complement operator(~) that it helps you to perform euclidean divison when n<0. Because it was not obvious for me to think on using ~ operator. Please help me tune my approach.

Answer 1

~n is -n - 1.

So ~(~n / d) is -((-n - 1) / d) - 1.

For negative values of n and positive values of d, this turns out to be division that rounds down (division normally rounds towards zero, so up for negative values of n). I can't explain why that is.