Integer division. Is int(-1/2) 0 or -1?

My friend, Christian told me a story about what is int(-1/2), 0 or -1? Christian found a problem when he explained a binary search program. When he computed the lower bound, but, the entry is not in an array.

  mid = (left+right)/2

When left = -1, right = 0. The mid is 0 in C, C++, and Java. The mid is -1 in python and ruby. I was also surprised this simple looking code depends on languages.

This is based on rounding method. C, C++, Java, and elisp does round to zero (truncate), therefore, this is 0.

python, ruby does round down (floor), therefore, this is -1. When we think about modulo, python and ruby holds

   x = x/y + x%y

condition, but not C++, Java. The modulo operation also depends on the languages when minus value is considered.

One more note, when I looked up binary search on the web, this mid code has overflow problem, so, it should be

  mid = low + (high - low)/2;




Thanks to Christian R.

No comments: