algorithmica-org/algorithmica

Section 3.3: ambiguous code and statements to fix

Andre1206 opened this issue · 0 comments

Another, more complicated way to implement this whole sequence is to convert this sign bit into a mask and then use bitwise and instead of multiplication: ((a[i] - 50) >> 31 - 1) & a[i].

First, in the C language the minus operation has higher priority than the >> operation, hence that code is equivalent to ((a[i] - 50) >> 30) & a[i] and thus is not consistent with the assembly language code shown below.
Second, as mentioned in Section 4.4, the result of the >> operation on negative integer depends on the implementation, which is not specified in Section 3.3. Let us consider the following 2 cases:
Case 1. If the leftmost bit is extended: then ((a[i]-50)>>31) is -1 when a[i]<50 (ignoring underflow) and is 0 when a[i]>=50. Therefore there is no need of the -1 after 31 at all.
Case 2. If the leftmost bit is filled with 0: Then (a[i] - 50) >> 31 does get the sign bit of a[i]-50. In this case, (((a[i] - 50) >> 31) - 1) is 0 when a[i]<50 and is -1 when a[i]>=50. This is the reverse of what we want here: We want a '-1' when 'a[i]<50' and a '0' when 'a[i]>=50'.

To sum up, I think this part is pretty confusing and need to be fixed.