3 ms·
Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
by albinofrenchy 9y ago
Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
- throwaway91111 9y agoIf "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type. Of course sorting 2^63 elements would require the different calculation.
- deleted 9y ago[deleted]
- pishpash 9y agoPointers are 64-bit on 64-bit machines, and so are the largest unsigned ints, hence the problem. On the other hand, you're probably searching at least 4-byte objects, so your actual list length isn't 64 bits but at most 62 bits even if you filled the memory space.
- JoshTriplett 9y agoIt doesn't, by itself, fix the bug identified in the article (though it does avoid a memory safety issue). But it's still important. Indexes should never be signed, any more than pointers should.
- boomlinde 9y agoWhy not? Indices are not pointers, so that's a poor argument by itself. Indices are offsets to pointers. If you can see any use for a negative offset off a pointer, that's your negative index use case. A nice example use is implementing IIR filters in a way that looks like the common mathematical form: y = a[0]*y[-1] + a[1]*y[-2] + b[0]*x[-1] + b[1]*x[-2]