Divide an integer by the power of two in C

Question

When try to divide an integer by the power of two in two different ways, I get two different output. One way is to right shift it by k bits. Another way is to divide it by (1<<k).

#include <stdio.h>

int main(void) {
  int y1 = 0x00061290;
  int y2 = 0xFFFE1A32;
  printf("(y1/(1<<k))=%x\n", (y1/(1<<5)));
  printf("(y2/(1<<k))=%x\n", (y2/(1<<5)));
  printf("(y1>>k))=%x\n", (y1>>5));
  printf("(y2>>k))=%x\n", (y2>>5));
  return 0;
}

Output:

(y1/(1<<k))=3094
(y2/(1<<k))=fffff0d2
(y1>>k))=3094
(y2>>k))=fffff0d1

When y1 is 0x00061290, the outputs of that integer are the same. When y2 is 0xFFFE1A32, the outputs of that integer are different.

I guess it is because y1 is positive and y2 is not. But I am not sure. Can someone tell me under what situation they are different and what situation they are the same? And explain the difference of two operations if possible. Thanks

chqrlie · Accepted Answer · 2022-06-14T06:53:42.400

The reason you get different output is y1 and y2 are defined as int instead of unsigned int. Signed division rounds toward 0 (as specified since C99), whereas shifting a negative value to the right rounds toward negative infinity on your platform. The C Standard specifies that the behavior for shifting negative values to the right is implementation defined.

Note however that passing an int to printf for a %x format has undefined behavior.

If you defined y1 and y2 as unsigned, the division and the shift will produce the same result.

Here is a modified version:

#include <stdio.h>

int main() {
    unsigned y1 = 0x00061290;
    unsigned y2 = 0xFFFE1A32;
    printf("y1=%x, y1/(1<<k)=%x\n", y1, y1 / (1<<5));
    printf("y2=%x, y2/(1<<k)=%x\n", y2, y2 / (1<<5));
    printf("y1=%x, y1>>k=%x\n", y1, y1 >> 5);
    printf("y2=%x, y2>>k=%x\n", y2, y2 >> 5);
    printf("\n");
    int i1 = 511;
    int i2 = -511;
    printf("i1=%d, i1/(1<<k)=%d\n", i1, i1 / (1<<5));
    printf("i2=%d, i2/(1<<k)=%d\n", i2, i2 / (1<<5));
    printf("i1=%d, i1>>k=%d\n", i1, i1 >> 5);
    printf("i2=%d, i2>>k=%d\n", i2, i2 >> 5);
    return 0;
}

Output:

y1=61290, y1/(1<<k)=3094
y2=fffe1a32, y2/(1<<k)=7fff0d1
y1=61290, y1>>k=3094
y2=fffe1a32, y2>>k=7fff0d1

i1=511, i1/(1<<k)=15
i2=-511, i2/(1<<k)=-15
i1=511, i1>>k=15
i2=-511, i2>>k=-16

The implementation-defined rounding direction was corrected in C99, it's nowadays well defined. See https://stackoverflow.com/questions/3602827/what-is-the-behavior-of-integer-division. The OP could be compiling as C89 though. — Lundin, Jun 14 '22 at 06:47
@Lundin: of course *implementation defined* only applies to the shift. I rephrased the answer to clarify this point. — chqrlie, Jun 14 '22 at 06:55
Perhaps I just read that sentence wrong. Anyway, it's fine now. Right-shifting negative values is indeed impl.defined. — Lundin, Jun 14 '22 at 06:57
@Lundin: you had a valid point, the phrase was ambiguous. *this behavior* was not precise enough. — chqrlie, Jun 14 '22 at 07:03

score 0 · Answer 2 · answered Jun 14 '22 at 06:43

In general, and in lots of assembly languages, there's 2 different "right shift" operations - a bitwise shift right (which shifts literal bits without treating the sign any different) and a logical shift right which "smears" the sign bit into the left as old bits are removed from the right so that the sign is preserved and it behaves like (repeated) division by 2.

The designers of C couldn't be bothered having different operators for the different cases (e.g. perhaps a ">>" for bitwise shift right and ">>>" for logical shift right); and couldn't be bothered defining the actual behavior of their "shift right" so that people writing portable code can write fast code (e.g. if the CPU supports bitwise shift right and the programmer wants bitwise shift right, then a programmer writing portable code can't expect >> to give them a bitwise shift right).

Instead; the C designers made a right shift of a signed integer "implementation defined" so that it's essentially useless.

Your specific compiler is treating >> as a bitwise right shift (and not as a logical right shift). This causes the different behavior because the sign isn't preserved.

A different compiler (even on the same CPU) might use a logical shift and might give the same result.

The other problem is that int y2 = 0xFFFE1A32; is trying to put a "too big positive number" (larger than INT_MAX) into an int, and the compiler doesn't warn you about it and just pretends that your positive number is a negative number. This is caused by unrelated misguided foolishness in the C specification - specifically, integer overflow is defined as wrapping/truncation (and therefore trying to shove an elephant into a shoe box is considered perfectly valid and not a trivially detected bug).

Hm... *signed* integer overflow is UB – though not fully sure if this applies, too, for assigning too large values. In any case QA obviously is aware of the wrapping around (*'y1 is positive while y2 is not'*)... — Aconcagua, Jun 14 '22 at 06:52
@Aconcagua: As far as I know; for implicit conversions there's a completely different set of rules (e.g. "Usual Arithmetic Conversions") and the rules for (signed) overflow are ignored. I'm not a language lawyer though- what I care about is reality. The practical reality is that you can't convince most (all?) C compilers to treat it as a warning or error (e.g. GCC with `-O3 -Wall -Wextra -Wstrict-overflow=5 -Warith-conversion -Wtype-limits -Wconversion -Wsign-conversion` won't give a warning). — Brendan, Jun 14 '22 at 18:58
Indeed – though question author is aware of anyway. That would have been clearer if she/he would have used an explicitly negative literal like `-0x1e5ce` – or simpler numbers right from the start, should have been observable with -5 shifted by one bit already ;) — Aconcagua, Jun 15 '22 at 04:53
Oh, by the way: *'[...] because the sign isn't preserved.'* Well, it *is* preserved, QA is wondering about receiving -15 by division but -16 by left shift – both results negative... — Aconcagua, Jun 15 '22 at 04:59

Divide an integer by the power of two in C

2 Answers2