2012-02-05

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;

References

http://en.wikipedia.org/wiki/Modulo_operation
http://en.wikipedia.org/wiki/Rounding
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://xlinux.nist.gov/dads//HTML/binarySearch.html
http://www.codecodex.com/wiki/Binary_search


Acknowledgements

Thanks to Christian R.

No comments: