Bitwise Shift Multiplication and Division Explained

Bitwise shift operations provide an efficient, low-level mechanism to perform arithmetic multiplication and division by powers of two. In the positional binary number system, shifting the bit pattern of an integer to the left multiplies the number by two for each shifted position, whereas shifting to the right divides the number by two. This guide explains how left and right bitwise shifts function, their mathematical equivalence to powers of two, and key considerations such as integer truncation, signed numbers, and overflow.

The Positional Binary Foundation

The binary number system is a base-2 positional numeral system. Each bit position from right to left represents an increasing power of two (\(2^0, 2^1, 2^2, 2^3\), and so on):

• \(2^3 = 8\)
• \(2^2 = 4\)
• \(2^1 = 2\)
• \(2^0 = 1\)

In the base-10 system, appending a zero to the right (shifting digits left) multiplies a number by 10 (e.g., \(5\) becomes \(50\)). Similarly, shifting a binary number’s bits to the left or right scales the value by the base of the system, which is 2.

Left Shift: Multiplication by \(2^n\)

A bitwise left shift (often denoted as <<) moves all bits in an operand to the left by a specified number of positions, filling the newly vacant least significant bits (LSBs) on the right with zeros.

Shifting an integer \(x\) to the left by \(n\) positions corresponds directly to:

\[\text{Result} = x \times 2^n\]

Example: Left Shift by 1 (\(x \times 2^1\))

Consider the decimal number \(5\), represented in an 8-bit binary format:

• Binary of \(5\): 00000101
• Shift left by 1 (5 << 1): 00001010
• Binary 00001010 in decimal: \((1 \times 8) + (0 \times 4) + (1 \times 2) + (0 \times 1) = 10\)

Example: Left Shift by 3 (\(x \times 2^3\))

• Shift left by 3 (5 << 3): 00101000
• Binary 00101000 in decimal: \((1 \times 32) + (1 \times 8) = 40\)
• Calculation: \(5 \times 2^3 = 5 \times 8 = 40\)

Overflow Considerations

When shifting left, if the most significant bits (MSBs) that represent the value are shifted beyond the fixed width of the integer register (e.g., 32-bit or 64-bit bounds), an overflow occurs, resulting in data loss or sign inversion in signed integers.

Right Shift: Division by \(2^n\)

A bitwise right shift moves all bits in an operand to the right by a specified number of positions, discarding the bits that fall off the right edge. This operation is mathematically equivalent to integer division (floor division) by \(2^n\):

\[\text{Result} = \lfloor x / 2^n \rfloor\]

Example: Right Shift by 1 (\(x / 2^1\))

Consider the decimal number \(20\):

• Binary of \(20\): 00010100
• Shift right by 1 (20 >> 1): 00001010
• Binary 00001010 in decimal: \(10\)

Truncation with Odd Numbers

Because bitwise shifting discards the lowest bits rather than calculating fractions, dividing an odd number truncates the remainder:

• Binary of \(7\): 00000111
• Shift right by 1 (7 >> 1): 00000011
• Binary 00000011 in decimal: \(3\) (equivalent to \(\lfloor 7 / 2 \rfloor\))

Logical vs. Arithmetic Right Shifts

When dealing with negative values in two’s complement representation, the distinction between logical and arithmetic right shifts is essential:

• Logical Right Shift (>>>): Vacant positions on the left are always filled with zeros. This is suitable for unsigned integers.
• Arithmetic Right Shift (>>): The sign bit (MSB) is replicated to fill the empty positions on the left. This preserves the negative sign of two’s complement numbers, maintaining correct integer division behavior for signed values.

Summary of Operations