3 ms·
Signed integer division by a power of two can be expensive
- copperx 9y agoTL;DR: Unsigned integer division by 2 can be optimized by the compiler only if there are unsigned integer types in the language. Java doesn't have unsigned primitive types (besides char), so x >>> 1 will be faster than x / 2 if you know that x >= 0. Please correct me if this is wrong.
- Scaevolus 9y agoCorrect. Java's >>> is unsigned, since it's a logical shift, but there's no corresponding unsigned division. Here's a clearer example of how GCC handles the different cases of signed vs unsigned division and shifting: https://godbolt.org/g/glC97v https://godbolt.org/g/glC97v Note that the signed division is the most expensive, but it still doesn't resort to a full divide instruction.
- DerekL 9y agoI was surprised that this made a difference in doing a binary search. I figured that the cost of memory fetches would swamp the cost of index calculation. But then I saw that his benchmarks were done on an array of length 2048, so that the entire array easily fits in the L1 cache.