Top question`s answer gets shift operator wrong?

user_4416169 0
Viewed 151

In the following question: Why is processing a sorted array faster than processing an unsorted array? the accepted answer explains a way of avoiding branch prediction for the given example. He/she goes on to replace a conditional statement with some bitwise operators:

Replace:

if (data[c] >= 128)
    sum += data[c];

with:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

however, in the line where he shifts to the right he seems to be doing so on a potentially signed value, which, as per this:

If the value after the shift operator is greater than the number of bits in the left-hand operand, the result is undefined. If the left-hand operand is unsigned, the right shift is a logical shift so the upper bits will be filled with zeros. If the left-hand operand is signed, the right shift may or may not be a logical shift (that is, the behavior is undefined).

is undefined behaviour. Can someone clarify if im missing something about the bitwise operations he is performing and may it also be explained what the bitwise operations performed are intended to do in layman's terms(given we interpret them as defined behaviour in some definition of shift for signed values).

bit c++
1 Answers

If data[c] >= 128, then data[c] - 128 will be non-negative, so it's sign bit will be 0. Otherwise, if data[c] < 128, then data[c] - 128 will be negative, so it's sign bit will be 1.

If we shift right by 31 (assuming an int is 32 bits, and right shifts are arithmetic, so yes implementation defined but pretty common), then we will have either 0x00000000 when data[c] >= 128 or 0xffffffff when data[c] < 128.

If we then bitwise invert that value, then we will have either 0xffffffff when data[c] >= 128 or 0x00000000 when data[c] < 128.

If we bitwise AND that value with data[c], then we will have either data[c] when data[c] >= 128 or 0x00000000 when data[c] < 128.

Adding 0 to sum does nothing, so we effectively only add the values that are greater or equal to 128 without branching.

user_6717030
Related