Left shift and right shift in C - Deep Dive

Overview - Left shift and right shift

What is it?

Left shift and right shift are operations that move the bits of a number to the left or right. Each move shifts all bits by a certain number of positions, changing the number's value. Left shift adds zeros on the right, making the number bigger, while right shift removes bits from the right or fills with zeros or ones depending on the type. These operations work directly on the binary form of numbers inside the computer.

Why it matters

These shifts let programs quickly multiply or divide numbers by powers of two without slow math. Without them, computers would do these calculations slower, making programs less efficient. They also help in low-level tasks like controlling hardware, encoding data, or optimizing performance, which are common in real-world software and devices.

Where it fits

Before learning shifts, you should understand binary numbers and how computers store data. After shifts, you can learn about bitwise operators, masks, and how to manipulate data at the bit level for tasks like encryption, compression, or graphics.

Mental Model

Core Idea

Left and right shifts move all bits in a number left or right, changing its value by powers of two.

Think of it like...

Imagine a row of boxes with balls inside representing bits. Left shift moves all balls one box to the left, adding an empty box on the right, making the row longer and the number bigger. Right shift moves balls one box to the right, dropping balls off the end or filling empty boxes on the left, making the number smaller or changing its sign.

Original number bits:
  [b7][b6][b5][b4][b3][b2][b1][b0]

Left shift by 1:
  [b6][b5][b4][b3][b2][b1][b0][0]

Right shift by 1:
  [0 or sign][b7][b6][b5][b4][b3][b2][b1]

Build-Up - 7 Steps

1

Foundation

Understanding binary numbers

Concept: Learn how numbers are stored as bits (0s and 1s) in computers.

Every number in a computer is stored as a sequence of bits. For example, the number 5 in 8 bits is 00000101. Each bit represents a power of two, starting from the right (least significant bit).

Result

You can see how numbers translate to bits and how each bit affects the total value.

Understanding binary is essential because shifts move these bits, changing the number's value.

2

Foundation

What is bit shifting?

Concept: Bit shifting moves bits left or right inside a number.

Left shift (<<) moves bits to the left, adding zeros on the right. Right shift (>>) moves bits to the right, filling the left with zeros or the sign bit depending on the type.

Result

You know that shifting changes the number by moving its bits and adding or removing bits.

Bit shifting is a direct way to multiply or divide by powers of two using binary.

3

Intermediate

Left shift as multiplication

🤔Before reading on: do you think left shifting a number by 1 always doubles it? Commit to yes or no.

Concept: Left shifting a number by n bits multiplies it by 2 to the power of n, if no bits are lost.

For example, 3 << 1 shifts bits of 3 (00000011) left by 1 to get 00000110, which is 6. This is like multiplying 3 by 2. But if bits shift out of the size limit, the value can change unexpectedly.

Result

Left shift can multiply numbers quickly but watch for overflow.

Knowing left shift as multiplication helps write faster code but requires care with number size limits.

4

Intermediate

Right shift as division

🤔Before reading on: does right shifting always divide a number by 2? Commit to yes or no.

Concept: Right shifting a number by n bits divides it by 2 to the power of n, rounding down for unsigned numbers.

For example, 8 >> 1 shifts bits of 8 (00001000) right by 1 to get 00000100, which is 4. For signed numbers, right shift may fill left bits with the sign bit (arithmetic shift) or zeros (logical shift), affecting negative numbers differently.

Result

Right shift can divide numbers quickly but behaves differently for signed and unsigned types.

Understanding right shift as division helps with efficient calculations and knowing how sign affects results.

5

Intermediate

Signed vs unsigned shifts

🤔Before reading on: do you think right shift fills left bits with zeros for both signed and unsigned numbers? Commit to yes or no.

Concept: Right shift fills left bits differently: zeros for unsigned (logical shift), sign bit for signed (arithmetic shift).

For unsigned int x = 0xF0 (11110000), x >> 2 becomes 00111100. For signed int y = -16, y >> 2 fills left bits with 1 to keep the sign, preserving negativity.

Result

Signed right shift keeps the sign, unsigned right shift does not.

Knowing this prevents bugs when shifting negative numbers and helps choose the right type.

6

Advanced

Shift overflow and undefined behavior

🤔Before reading on: what happens if you shift bits more than the size of the type? Commit to your guess.

Concept: Shifting bits beyond the size of the data type causes undefined behavior in C, which can crash or produce wrong results.

For example, shifting a 32-bit int by 32 or more bits is undefined. Compilers may optimize away code or produce unexpected values. Always ensure shift counts are less than the bit width.

Result

Avoiding large shifts prevents crashes and bugs.

Understanding undefined behavior helps write safe, portable code.

7

Expert

Compiler optimizations and hardware shifts

🤔Before reading on: do you think bit shifts always run as simple CPU instructions? Commit to yes or no.

Concept: Compilers often optimize shifts into fast CPU instructions, but behavior can vary by hardware and compiler, especially for signed shifts.

Some CPUs have separate instructions for logical and arithmetic shifts. Compilers choose instructions based on type and context. Also, some optimizations may reorder or remove shifts if they detect undefined behavior.

Result

Shifts are usually very fast but require understanding compiler and hardware details for critical code.

Knowing how shifts map to hardware helps write high-performance and portable low-level code.

Under the Hood

At the hardware level, left and right shifts move bits inside CPU registers. Left shift moves bits towards the higher bit positions, inserting zeros at the right end. Right shift moves bits towards lower bit positions, filling the left end with zeros or the sign bit depending on the instruction. The CPU uses dedicated shift instructions that execute in a single cycle, making shifts very fast. The compiler translates C shift operators into these instructions, considering the data type and signedness.

Why designed this way?

Shifts were designed to provide a fast, simple way to multiply or divide by powers of two and manipulate bits directly. Early computers had limited arithmetic units, so shifting was an efficient alternative to multiplication or division. The distinction between logical and arithmetic right shifts preserves the sign of signed numbers, which is important for correct arithmetic behavior. Undefined behavior for large shifts allows compilers to optimize aggressively without extra checks.

CPU Register (8 bits):
┌─────────────────────────┐
│ b7 b6 b5 b4 b3 b2 b1 b0 │
└─────────────────────────┘

Left Shift by 1:
┌─────────────────────────┐
│ b6 b5 b4 b3 b2 b1 b0  0 │
└─────────────────────────┘

Right Shift by 1 (Logical):
┌─────────────────────────┐
│ 0 b7 b6 b5 b4 b3 b2 b1 │
└─────────────────────────┘

Right Shift by 1 (Arithmetic):
┌─────────────────────────┐
│ b7 b7 b6 b5 b4 b3 b2 b1 │
└─────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does left shifting a negative number always multiply it by two? Commit to yes or no.

Common Belief: Left shifting any number, including negative ones, always multiplies it by two.

Reality: Left shifting negative numbers can cause overflow or undefined behavior and does not reliably multiply by two.

Why it matters: Assuming this can cause bugs or crashes when working with signed integers.

Quick: Does right shifting a signed negative number always fill left bits with zeros? Commit to yes or no.

Common Belief: Right shift always fills left bits with zeros regardless of sign.

Reality: Right shift on signed negative numbers usually fills left bits with ones to preserve the sign (arithmetic shift).

Why it matters: Misunderstanding this leads to wrong results when dividing negative numbers by powers of two.

Quick: Is shifting by the number of bits equal to the type size safe and well-defined? Commit to yes or no.

Common Belief: Shifting by the bit width of the type (e.g., 32 for int) is safe and just results in zero.

Reality: Shifting by the bit width or more is undefined behavior in C and can cause unpredictable results.

Why it matters: Ignoring this can cause serious bugs and security issues in programs.

Quick: Do compilers always generate the same machine code for shifts on all platforms? Commit to yes or no.

Common Belief: Shift operations in C always compile to the same machine instructions everywhere.

Reality: Different CPUs and compilers may implement shifts differently, especially for signed types and large shift counts.

Why it matters: Assuming uniform behavior can cause portability problems across hardware.

Expert Zone

1

Signed right shifts are implementation-defined in C, so behavior can vary between compilers and platforms.

2

Shifting by a variable amount requires care because the compiler may not optimize it as well as constant shifts.

3

Some CPUs have rotate instructions that differ from shifts but can be combined with shifts for advanced bit manipulation.

When NOT to use

Avoid using shifts for multiplication or division when dealing with signed integers that might overflow or when exact rounding is needed. Use standard arithmetic operators instead. Also, do not use shifts for non-power-of-two multiplications or divisions. For portable code, avoid shifting by amounts equal to or larger than the bit width.

Production Patterns

In real-world systems, shifts are used for fast arithmetic in embedded systems, graphics programming for color channel extraction, cryptography for bit-level transformations, and network protocols for packing and unpacking data fields efficiently.

Connections

Bitwise operators

Builds-on

Understanding shifts is essential before mastering bitwise AND, OR, XOR, which manipulate bits without moving them.

Data compression

Builds-on

Shifts help pack and unpack bits tightly, a key step in compressing data to save space.

Signal processing

Similar pattern

Shifting bits in digital signals is like shifting frequencies in analog signals, both changing the representation to extract or modify information.

Common Pitfalls

#1 Shifting bits more than the size of the variable.

Wrong approach:

int x = 1 << 32; // shifting 32 bits on a 32-bit int

Correct approach:

int x = 1 << 31; // shift less than bit width

Root cause:

Misunderstanding that shifting by the bit width or more is undefined behavior in C.

#2 Assuming right shift always fills with zeros.

Wrong approach:

int y = -8; int z = y >> 1; // expecting z to be positive

Correct approach:

Use unsigned types or explicit masks if zero-fill is needed: unsigned int u = (unsigned int)y >> 1;

Root cause:

Not knowing that right shift on signed negative numbers usually fills with the sign bit.

#3 Using left shift to multiply signed integers without overflow checks.

Wrong approach:

int a = 1000000; int b = a << 10; // no overflow check

Correct approach:

Use safe multiplication or check for overflow before shifting.

Root cause:

Assuming left shift is always safe multiplication.

Key Takeaways

Left and right shifts move bits in a number, effectively multiplying or dividing by powers of two.

Shifts operate on the binary representation, so understanding binary is crucial.

Right shift behaves differently for signed and unsigned numbers, affecting results with negative values.

Shifting by amounts equal to or larger than the bit width causes undefined behavior in C.

Shifts are powerful for performance and low-level programming but require careful use to avoid bugs.