3 ms·
Why would anyone do a silly thing like work with integers smaller than the register size of the machine? Yet, even C gets this sort-of right, in an obsolescent
by kazinator 5y ago
Why would anyone do a silly thing like work with integers smaller than the register size of the machine?
Yet, even C gets this sort-of right, in an obsolescent way. When integer types narrower than int are manipulated in expressions, they promote to either int or unsigned int (whichever can represent the original type's value range).
So for instance, this doesn't overflow, unless sizeof(char) == sizeof(int).
char mid, high, low;
...
mid = high + low / 2;
Reason being that this is actually doing something like:
mid = (char) (((int) high + (int) low) / 2);
(When sizeof(char) == 1, we are almost certainly on some DSP chip, where char is wider than 8 bits possibly as much as 32. Portable code using unsigned for array indexing would not assume that it goes beyond 255.)
It would be useful in a C like language if the declaration of a custom integer type could separately specify promotion semantics (possibly that it has none).
I would make it the default behavior that all integer values promote to the widest available type in their signedness. (E.g. the thing that corresponds to intmax_t or uintmax_t in C).
If someone wanted to optimize around that (due to the widest type not being the fastest, say), they could declare a custom type that promotes to something narrower, or doesn't promote.
- ridiculous_fish 5y agoYou misunderstood! In my code, all arithmetic is performed with 64-bit unsigned integers. The "trick" is a type whose size is zero bytes. If T is size zero, Vec<T> does not allocate any memory: it just keeps a count. You can make a Vec<()> with usize::max() for free, if you can finesse the compiler. The binary search itself does not access any memory: it's just pure arithmetic, and it overflows.
- kazinator 5y agoHow do you use this object in an application, such that it's useful to do a binary_search on it and part of the application? Would that be just to prototype something before going to other data structures, or in production too?