I need a little explaination on this bitwise puzzle

Question

I have been stuck on this bitwise puzzle for a few hours. I was searching for a good solution to this problem on google to see how others were solving it and i came across this solution. I am trying to figure out how it works. The only thing i don't understand about this is the rounding process and the lost bits? what bits are lost?

I would really appreciate someone explaining this solution to me.

Thanks in advance guys, Yosemite :)

/*
 * ezThreeFourths - multiplies by 3/4 rounding toward 0,
 *   Should exactly duplicate effect of C expression (x*3/4),
 *   including overflow behavior.
 *   Examples: ezThreeFourths(11) = 8
 *             ezThreeFourths(-9) = -6
 *             ezThreeFourths(1073741824) = -268435456 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */

int ezThreeFourths(int x) {
/*
 *sets y to make up for the lost bits while rounding. Multiplies
 *by three by adding x 3 times. Records the sign since
 * what is added will be different depending on whether the sign
 *is positive or negative and adds this to to the number. Then
 *divedes by 8 by shifting.
 */
  int y = 3;
  x =x+x+x;
  int z = x>>31;
  z = y & z;
  x = z + x;
  x = x>>2;
  return x;
}

this is the link where i got it from: link the individual didn't mark his name in the file so i don't know his name

user_3018243 · Answer

All the work here is just being done to match the fact that iso C defines division to round towards zero. The much easier version of multiplying by 3/4 is to just multiply by three and shift by 2:

return (x+x+x) >> 2;

Unfortunately this has the wrong behaviour for negative values (it floors the value instead of rounding towards zero).

To fix it we need to add 3^* to negative terms before shifting by 2 to emulate rounding via truncation. We do it as follows:

int z = x >> 31; // Arithmetic right shift extracts sign mask (0xffffffff or 0x0)
int y = 3 & z; // 3 for negative values, 0 for nonnegative
return (x + x + x + y) >> 2; // Multiply and divide with rounding

To be even more correct we should take into account that we don't really know the size of an integer is 32 by changing the code like so:

int three_fourths(int x) {
    return (x + x + x + (3 & (x >> (8 * sizeof(x) - 1)))) >> 2;
}

You can see this final implementation in action here.

^{*_{This is an idiom for turning a flooring divide into a ceiling divide. If you have x / N rounding down you can change the expression to (x + N - 1) / N to round up instead. For N==4 the transformation would be x / 4->(x + 3) / 4}}

Undefined Behavior

What we have finally still has some assumptions. While of course x + x + x can overflow and yield undefined behavior, thats no different than x * 3 (ignore the question writer suggesting this has the same behavior for overflow, it will on some implementations but that's not guaranteed).

The big piece of implementation defined behavior is the arithmetic right shift. Here's what the C standard has to say on the issue (ISO/IEC 9899:TC3 §6.5.7 ¶5):

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

So the mask extraction will only work if right shifting any negative value by one less than the width of an int yields a value with ones in all of the bit positions. This holds in the common implementation for two's complement systems (and likely any system you will ever work on) but it's not technically guaranteed by the standard.

I need a little explaination on this bitwise puzzle

1 Answers