Shift Operators

Part I · Module 3 · Chapter 3.9 · Shift Operators

1. Moving the Pattern

Two operators:

  value << n      shift the bit pattern n positions toward the high end
  value >> n      shift the bit pattern n positions toward the low end

As in Chapter 3.8, the examples use unsigned int with u-suffixed literals, because bit patterns belong in unsigned types and because — as §4 shows — signedness changes the rules.

#include <stdio.h>

int main(void)
{
    unsigned int value = 0x2Du;

    printf("value      = %u  (0x%X)\n", value, value);
    printf("value << 1 = %u  (0x%X)\n", value << 1, value << 1);
    printf("value << 4 = %u  (0x%X)\n", value << 4, value << 4);
    printf("value >> 1 = %u  (0x%X)\n", value >> 1, value >> 1);
    printf("value >> 3 = %u  (0x%X)\n", value >> 3, value >> 3);
    return 0;
}

Output:

value      = 45  (0x2D)
value << 1 = 90  (0x5A)
value << 4 = 720  (0x2D0)
value >> 1 = 22  (0x16)
value >> 3 = 5  (0x5)

In bits — showing only the low eight positions, which is enough for this value:

  value        0010 1101        0x2D   = 45
  value << 1   0101 1010        0x5A   = 90
  value >> 1   0001 0110        0x16   = 22
  value >> 3   0000 0101        0x05   = 5

Vacated positions are filled with zeros. That is the picture, and it is a picture of this example at a convenient width, not a statement about how wide an unsigned int is — Chapter 2.5 settled that it is implementation-defined, and §3 shows why the real width matters.

2. Bits That Leave Do Not Come Back

A shift is not a conveyor belt with storage at the end. Positions pushed beyond the width of the type are gone:

#include <stdio.h>

int main(void)
{
    unsigned int v = 0x80000000u;

    printf("v           = 0x%X\n", v);
    printf("v << 1      = 0x%X\n", v << 1);
    printf("v >> 31     = 0x%X\n", v >> 31);
    printf("(v>>31)<<31 = 0x%X\n", (v >> 31) << 31);
    return 0;
}

Output:

v           = 0x80000000
v << 1      = 0x0
v >> 31     = 0x1
(v>>31)<<31 = 0x80000000

The second line is the point: the only set bit was at the top, shifting left pushed it out, and the result is zero. Nothing was preserved anywhere. The fourth line shows the mirror case — that same bit shifted all the way down and back up again survives, because it never left the width.

So a shift can lose information, silently and by design. Chapter 3.8's masking kept bits where they were; shifting relocates them, and relocation past the edge is a one-way trip.

3. The Operation Does Not Happen in the Type You Wrote

This is the part that separates people who use shifts from people who get them right, and it is observable in three lines:

#include <stdio.h>

int main(void)
{
    unsigned char small = 0x01u;

    printf("sizeof small        = %zu\n", sizeof small);
    printf("sizeof (small << 1) = %zu\n", sizeof (small << 1));
    printf("small << 9          = %u\n", small << 9);
    return 0;
}

Output:

sizeof small        = 1
sizeof (small << 1) = 4
small << 9          = 512

Read those three lines carefully.

small occupies one byte. Chapter 2.12's sizeof confirms it.

The shift expression occupies four. The expression's type is not unsigned char.

Shifting by 9 produced 512. In an 8-bit type that would be impossible — the single set bit would have left the width long before position 9 and the answer would be 0.

What happened is that C performed an integer promotion on the left operand before shifting. A narrow operand is converted to a wider type first, and the shift happens in that wider type. Chapter 3.12 owns promotions and explains exactly which type you get and why; the fact you need now is the rule that follows from it:

The shift count must be less than the number of bits in the promoted left operand — not in the variable you declared.

You will see the folk version of this rule written as "less than the width of the variable". The program above is a direct counterexample: small is 8 bits wide and a count of 9 is perfectly legal, because the operation is not happening in 8 bits.

One more consequence worth noting now: shifts are unusual among the binary operators in that each operand is promoted individually, and the result takes the type of the promoted left operand. The right operand's type has no influence on the result type at all. Most other binary operators work differently, which is again Chapter 3.12's subject.

4. Signed Operands Change the Rules

Everything so far used unsigned operands. Here is what changes when the left operand is signed, stated precisely because the differences are exactly where the bugs are.

Left shift of a signed value. If the value is non-negative and the mathematical result is representable in the promoted type, that result is what you get. If the value is negative, or the result does not fit, the behaviour is undefined — not wrapped, not truncated, undefined. This is the same category Chapter 2.6 described for signed overflow, and it has the same consequence: there is nothing to predict.

Right shift of a signed value. For a non-negative value the result is the value divided by the appropriate power of two, discarding the remainder — the same truncation Chapter 3.3 established. For a negative value the result is implementation-defined: your implementation chooses and must document it. In Chapter 1.3's vocabulary that is a different category from undefined — there is an answer, and it is your implementation's answer rather than C's.

In practice almost every implementation keeps the sign by filling the vacated high positions with the sign bit, which Chapter 2.7's two's complement makes the natural choice. But almost every is not all, and relying on it without saying so is how code stops being portable.

5. Counts That Are Not Allowed

Two counts make a shift undefined regardless of signedness:

  value << -1          negative count          — undefined
  value << 32          count >= promoted width — undefined (where that width is 32)

Neither is a wrapped count, a zero result, or a shift in the other direction. C imposes no requirements, so nothing about the program's behaviour is predictable afterwards.

This chapter does not show you what either one prints, for the reason Chapters 2.6 and 3.7 gave: a result from one run on one compiler teaches you that the number is worth looking at, and it is not. Some compilers can diagnose a constant out-of-range count; none can catch a count that only becomes too large while the program runs.

The guard is yours. If a shift count comes from anywhere other than a literal you wrote, the question "can this reach the width?" is part of writing the line.

6. A Realistic Use

Shifts and masks together are how a value with several pieces packed into it is read and written. Here one byte holds two four-bit fields:

#include <stdio.h>

int main(void)
{
    unsigned int high = 0x0Au;
    unsigned int low = 0x03u;

    unsigned int packed = (high << 4) | low;

    unsigned int unpacked_high = (packed >> 4) & 0x0Fu;
    unsigned int unpacked_low = packed & 0x0Fu;

    printf("packed        = 0x%02X\n", packed);
    printf("unpacked high = 0x%X\n", unpacked_high);
    printf("unpacked low  = 0x%X\n", unpacked_low);
    return 0;
}

Output:

packed        = 0xA3
unpacked high = 0xA
unpacked low  = 0x3

Four operations, each one already familiar:

• high << 4 moves the first field into the upper four positions.
• | low sets the lower four, using Chapter 3.8's set idiom.
• (packed >> 4) brings the upper field back down.
• & 0x0Fu keeps only four positions, using Chapter 3.8's extract idiom.

The & 0x0Fu on the way out matters even though the value appears to fit. It states the field's width explicitly rather than relying on what happened to be above it, which is the habit that keeps this code correct when the packed value grows more fields.

This shape — shift into position, mask on the way out — is one of the most common in systems programming. Part II is largely about the case where somebody else's specification decides the positions.

7. What You Should Be Able to Say Now

1. << and >> move a value's bit pattern; vacated positions are filled with zeros for unsigned values.
2. Bits shifted beyond the width are lost. A shift can discard information silently.
3. The doubling and halving intuition is useful but conditional — safe for unsigned within the type's range, and a trap for signed.
4. Each operand is promoted individually, and the result takes the type of the promoted left operand. The right operand's type does not affect the result type.
5. The count must be less than the width of the promoted left operand, which is not the width of the variable you declared.
6. unsigned char small = 1; small << 9 gives 512 — direct proof of the previous two points.
7. Signed left shift is defined only for a non-negative value whose result fits; otherwise it is undefined.
8. Right shift of a negative signed value is implementation-defined — an answer your implementation chooses, not one C specifies.
9. A negative count, or a count at or beyond the promoted width, is undefined.
10. Use unsigned types when shifting bit patterns.

8. Exercise

Exercise 1 — predict in bits. For unsigned int x = 0x12u, give the value of x << 2, x >> 1 and x << 8, in hexadecimal. Work them as bit patterns, not arithmetic.

Exercise 2 — lose a bit on purpose. For an unsigned int holding 0x1u, what is the smallest left-shift count that produces 0 on a machine where that type is 32 bits? Explain why.

Exercise 3 — classify each shift. Say whether each is fully defined, implementation-defined, or undefined, and why: (a) unsigned int u = 5; u << 3 (b) int s = -8; s >> 1 (c) int s = -8; s << 1 (d) unsigned int u = 5; u << 64 on a 32-bit unsigned int (e) unsigned int u = 5; u << -1

Exercise 4 — disprove the folk rule. A tutorial states: "The shift count must be less than the number of bits in the variable being shifted." Using §3, give the counterexample and explain in two sentences why the rule is wrong as written.

Exercise 5 — repair the type. Someone writes int flags = 0x80000000; and then shifts it left by one, expecting it to wrap to 0. Say what is actually wrong with this code in two respects, and give the corrected declaration.

Exercise 6 — build a field. Using only shifts and the Chapter 3.8 idioms, write the expression that places the value in field into bit positions 8 through 11 of an otherwise-zero unsigned int, and the expression that reads it back out.

9. Summary

• << and >> move a bit pattern, filling vacated positions with zeros for unsigned values.
• Bits that leave the width are gone. Shifting loses information silently.
• Doubling and halving is an intuition, not a rule — conditional for unsigned and a trap for signed.
• The operation happens in the promoted type. Each operand is promoted individually and the result takes the promoted left operand's type.
• So the count limit is the promoted width, not the declared variable's — and small << 9 giving 512 proves it.
• Signed left shift is undefined for negative values or results that do not fit.
• Signed right shift of a negative value is implementation-defined, not undefined, and not guaranteed to preserve the sign.
• Negative or oversized counts are undefined. No output from one is worth reading.
• Shift bit patterns in unsigned types.

Something in this chapter was settled by a rule you have not been taught. The shift happened in a type you did not write, the count limit followed from that type, and §3 could only point forward. The same thing has now happened four times in this module — in Chapter 3.3's division, Chapter 3.5's reversed comparison, Chapter 3.8's wider-than-expected ~, and here. Before the chapter that explains all four, there is one more question to settle: when an expression contains several operators at once, which ones belong together?