3 ms·

It's nice that it expresses algorithms in C. It's more concrete than most of Hacker's Delight, which is similar and more comprehensive, but often vaguer and occ

It's nice that it expresses algorithms in C. It's more concrete than most of Hacker's Delight, which is similar and more comprehensive, but often vaguer and occassionally covers tricks used on historical architectures and systems.[0] 0. Hacker's Delight (Second Edition) by Henry S. Warren, 2013, ISBN: 0321842685

unwind 2y ago
It is nice, and it's also nice that it contains notes on how right-shifting a signed integer is implementation-defined in C (it's not the much-feared undefined behavior) so inherently non-portable. You should of course always check your compiler output when doing stuff like this, but doubly so in those cases.
- dahart 2y ago
  Unfortunately it doesn’t mention how left-shifting a negative signed integer is undefined behavior. There are a few cases where constants were changed to fix this, e.g. using (1U<<n) instead of (1<<n), but strangely that change didn’t get propagated everywhere and it appears there are still a couple cases in the code that might be UB. Specifically, the variation of variable-width sign-extend in 3 operations looks crazy. Aren’t there multiple UBs in this one? unsigned b; // number of bits representing the number in x int x; // sign extend this b-bit number to r int r; // resulting sign-extended number // The following variation is not portable, but on architectures that employ an arithmetic right-shift, maintaining the sign, it should be fast. const int s = -b; // OR: sizeof(x) * CHAR_BIT - b; r = (x << s) >> s; Not sure if I’m missing something, but it looks like this relies on shift by a negative number (UB), potential left shift of a 1 bit into the sign bit (UB), and potential right shift of a negative number (implementation defined). Isn’t this much worse than non-portable, but guaranteed to be undefined?

unwind 2y ago

It is nice, and it's also nice that it contains notes on how right-shifting a signed integer is implementation-defined in C (it's not the much-feared undefined behavior) so inherently non-portable. You should of course always check your compiler output when doing stuff like this, but doubly so in those cases.

dahart 2y ago
Unfortunately it doesn’t mention how left-shifting a negative signed integer is undefined behavior. There are a few cases where constants were changed to fix this, e.g. using (1U<<n) instead of (1<<n), but strangely that change didn’t get propagated everywhere and it appears there are still a couple cases in the code that might be UB. Specifically, the variation of variable-width sign-extend in 3 operations looks crazy. Aren’t there multiple UBs in this one? unsigned b; // number of bits representing the number in x int x; // sign extend this b-bit number to r int r; // resulting sign-extended number // The following variation is not portable, but on architectures that employ an arithmetic right-shift, maintaining the sign, it should be fast. const int s = -b; // OR: sizeof(x) * CHAR_BIT - b; r = (x << s) >> s; Not sure if I’m missing something, but it looks like this relies on shift by a negative number (UB), potential left shift of a 1 bit into the sign bit (UB), and potential right shift of a negative number (implementation defined). Isn’t this much worse than non-portable, but guaranteed to be undefined?