And those additional instructions are there only because C modulo is defined to have the same sign as the dividend (so that e.g. -5 % 2 == -1 instead of 1). Had it been defined as being always positive, &1 would have been sufficient in all cases (that would also have the effect of making integer division round to negative infinity instead of zero which too can be implemented simply by >>1, for both signed and unsigned numbers).