Bitwise Operations: Shifts and Masks

Processors do more with binary patterns than add and subtract — they shift bits sideways and combine them with logical operators acting on every bit position at once. These bitwise operations are how a computer multiplies and divides by powers of two cheaply, how it packs several flags into a single byte, and how it isolates or alters individual bits. This lesson covers the three kinds of shift (logical, arithmetic, circular), shifting as multiplication and division (and the information loss involved), the bitwise operators AND, OR, XOR, NOT, and the use of masks to set, clear, test and flip specific bits — each with fully worked examples.

---

Spec Mapping

This lesson covers the bitwise strand of the AQA A-Level Computer Science (7517) Fundamentals of data representation area:

• Logical shifts, arithmetic shifts and circular (cyclic) shifts — what each does to the bits and to the value.
• Shifts as multiplication and division by powers of two — and how bits "fall off the end", causing information loss.
• Bitwise logical operations — AND, OR, XOR and NOT applied bit-by-bit.
• Masks — constructing and applying masks to set, clear, test (check) and toggle (flip) chosen bits.

These operations underpin low-level systems programming and connect to logic gates and the arithmetic logic unit.

---

Shifts

A shift moves every bit a fixed number of places left or right. What happens at the ends — what fills the vacated positions and what becomes of the displaced bits — depends on the kind of shift.

Logical shift

A logical shift treats the pattern as a plain unsigned value. Vacated positions are filled with 0, and bits shifted off the end are lost.

Logical shift left of $\texttt{00010110}$00010110 by 1:

	$2^7$27	$2^6$26	$2^5$25	$2^4$24	$2^3$23	$2^2$22	$2^1$21	$2^0$20
Before	0	0	0	1	0	1	1	0
After (LSL 1)	0	0	1	0	1	1	0	0

The value goes from $22$22 to $44$44. Logical shift right of $\texttt{00010110}$00010110 by 1 gives $\texttt{00001011}$00001011 ($22 \to 11$22→11): a 0 enters at the left and the rightmost bit (here a 0) drops off.

Shifts as multiply / divide by powers of two

For unsigned values:

• A logical shift left by $n$n multiplies by $2^n$2n (each place left doubles the value).
• A logical shift right by $n$n divides by $2^n$2n (integer division — the remainder, in the bits that fall off, is discarded).

$\text{LSL by } n: \ x \times 2^{n}, \qquad \text{LSR by } n: \ \left\lfloor \frac{x}{2^{n}} \right\rfloor$LSL by n: x×2n,LSR by n: ⌊2nx​⌋

This is far cheaper for hardware than a general multiply, which is why compilers replace x * 8 with x << 3.

The speed advantage is fundamental: a shift can be implemented as nothing more than re-wiring which bit lines feed which output positions, completing in a single clock cycle, whereas a general multiplication requires a much larger and slower circuit. This is why bitwise operations sit at the heart of performance-critical code — graphics routines, hash functions, compression, encryption and device drivers all lean heavily on shifts and logical operations precisely because they are among the cheapest things a processor can do. Understanding them is therefore not an academic curiosity; it is how real systems extract speed from limited hardware. The same reasoning explains why a programmer who needs to multiply or divide by a power of two in a tight loop may reach for a shift, and why exam questions frequently frame shifts in terms of "an efficient way to multiply/divide".

Information loss

Shifting is lossy at the boundaries:

• Shifting left, a 1 that moves past the MSB is lost — so the result wraps/overflows. Shift $\texttt{10010110}$10010110 ($150$150) left by 1: the leading 1 falls off, giving $\texttt{00101100} = 44$00101100=44, not $300$300 (which needs 9 bits).
• Shifting right, bits that move past the LSB are lost — this is the discarded remainder of the division. Shift $\texttt{00001011}$00001011 ($11$11) right by 1: the rightmost 1 is lost, giving $\texttt{00000101} = 5 = \lfloor 11/2 \rfloor$00000101=5=⌊11/2⌋. The information that 11 was odd is gone.

Exam Tip: When asked for the value after a shift, state both the resulting bit pattern and whether information was lost (a 1 fell off the end). "Divide by 2" is only exact when the bit shifted out is 0.

Arithmetic shift

An arithmetic shift preserves the sign of a two's complement number so that a right shift correctly divides signed values by powers of two.

• Arithmetic shift left behaves like logical shift left (0 in at the right) — multiplying by 2.
• Arithmetic shift right copies the sign bit into the vacated leftmost position (sign extension) instead of inserting a 0.

Arithmetic shift right of $\texttt{11110100}$11110100 (which is $-12$−12 in two's complement) by 1:

	$-2^7$−27	$2^6$26	$2^5$25	$2^4$24	$2^3$23	$2^2$22	$2^1$21	$2^0$20
Before	1	1	1	1	0	1	0	0
After (ASR 1)	1	1	1	1	1	0	1	0

The new leftmost bit is a copy of the old sign bit (1), not a 0. The result $\texttt{11111010}$11111010 decodes as $-128 + 64 + 32 + 16 + 8 + 2 = -6 = \lfloor -12 / 2 \rfloor$−128+64+32+16+8+2=−6=⌊−12/2⌋. A logical right shift would have inserted a 0, giving $\texttt{01111010} = +122$01111010=+122 — completely wrong for a signed division. This is why the distinction matters.

Circular (cyclic) shift

A circular shift (rotate) loses nothing: the bit that falls off one end re-enters at the other.

Circular shift left of $\texttt{10010110}$10010110 by 1: the MSB (1) wraps around to the LSB:

	$b_7$b7​	$b_6$b6​	$b_5$b5​	$b_4$b4​	$b_3$b3​	$b_2$b2​	$b_1$b1​	$b_0$b0​
Before	1	0	0	1	0	1	1	0
After (rotate left 1)	0	0	1	0	1	1	0	1

The result is $\texttt{00101101}$00101101 — every bit is preserved, just rotated. A circular shift does not correspond to multiplication or division; it is used in cryptography and checksums where no information may be discarded.

Circular shift right is the mirror image: the LSB wraps round to become the new MSB. Rotating $\texttt{00101101}$00101101 right by 1, the rightmost bit (1) wraps to the left, giving $\texttt{10010110}$10010110 — which is exactly the byte we started the rotate-left example with, confirming that a right rotation by 1 perfectly undoes a left rotation by 1. This reversibility is the whole point: because no bit is ever lost, a rotate is invertible, whereas a logical or arithmetic shift that pushes a bit off the end is not. That is precisely why cryptographic round functions and cyclic redundancy checks (CRCs) use rotations — they thoroughly rearrange bits while guaranteeing the operation can be reversed and no information is destroyed in the mixing.

graph TD
    A["Shift type"] --> B["Logical: fill with 0, lose end bits"]
    A --> C["Arithmetic: copy sign bit on right shift"]
    A --> D["Circular / rotate: wrap end bit around, lossless"]
    B --> E["Unsigned multiply/divide by 2^n"]
    C --> F["Signed division by 2^n"]
    D --> G["Crypto, checksums"]

(The mermaid above is illustrative; treat the labels as shorthand for the precise rules stated in the text.)

---

Bitwise Logical Operations

A bitwise operator applies a logic gate to each pair of bits in the same column independently — there are no carries between columns (unlike addition). Recall the single-bit truth tables:

A	B	A AND B	A OR B	A XOR B
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

A	NOT A
0	1
1	0

The defining behaviours: AND gives 1 only when both bits are 1; OR gives 1 when either is 1; XOR (exclusive OR) gives 1 when the bits differ; NOT inverts every bit.

Worked example over a byte

Let $A = \texttt{11001010}$A=11001010 and $B = \texttt{10110110}$B=10110110. Applying each operator column by column:

	$b_7$b7​	$b_6$b6​	$b_5$b5​	$b_4$b4​	$b_3$b3​	$b_2$b2​	$b_1$b1​	$b_0$b0​
$A$A	1	1	0	0	1	0	1	0
$B$B	1	0	1	1	0	1	1	0
$A$A AND $B$B	1	0	0	0	0	0	1	0
$A$A OR $B$B	1	1	1	1	1	1	1	0
$A$A XOR $B$B	0	1	1	1	1	1	0	0
NOT $A$A	0	0	1	1	0	1	0	1

So $A \text{ AND } B = \texttt{10000010}$A AND B=10000010, $A \text{ OR } B = \texttt{11111110}$A OR B=11111110, $A \text{ XOR } B = \texttt{01111100}$A XOR B=01111100, and $\text{NOT } A = \texttt{00110101}$NOT A=00110101.

The identities that make masking predictable

Masking works reliably because each operator has fixed "do nothing" and "force" behaviours when one operand is a known 0 or 1. These single-bit identities are worth committing to memory — they are the entire logic behind which operator to choose:

Identity	Effect
$x \text{ AND } 1 = x$x AND 1=x	AND with 1 leaves a bit unchanged
$x \text{ AND } 0 = 0$x AND 0=0	AND with 0 forces a bit to 0 (clear)
$x \text{ OR } 0 = x$x OR 0=x	OR with 0 leaves a bit unchanged
$x \text{ OR } 1 = 1$x OR 1=1	OR with 1 forces a bit to 1 (set)
$x \text{ XOR } 0 = x$x XOR 0=x	XOR with 0 leaves a bit unchanged
$x \text{ XOR } 1 = \overline{x}$x XOR 1=x	XOR with 1 inverts a bit (toggle)
$x \text{ XOR } x = 0$x XOR x=0	XOR of a value with itself is zero

The last identity, $x \text{ XOR } x = 0$x XOR x=0, together with $x \text{ XOR } 0 = x$x XOR 0=x, is what makes XOR self-inverse: applying the same XOR mask twice returns the original value. That single property powers the XOR swap trick, simple stream ciphers (the Vernam cipher in the encryption topic) and parity calculations. Recognising that "unchanged where the mask bit is the operator's identity element, forced/flipped where it is not" lets you derive the correct mask operation rather than memorising four separate recipes.

Worked use of XOR's self-inverse property

Encrypt the byte $\texttt{01101001}$01101001 with the key byte $\texttt{00111100}$00111100 using XOR, then decrypt it:

$\text{cipher} = \texttt{01101001} \oplus \texttt{00111100} = \texttt{01010101}$cipher=01101001⊕00111100=01010101 $\text{plain} = \texttt{01010101} \oplus \texttt{00111100} = \texttt{01101001}$plain=01010101⊕00111100=01101001

XOR-ing the cipher with the same key recovers the original byte exactly — a direct application of $(x \oplus k) \oplus k = x \oplus (k \oplus k) = x \oplus 0 = x$(x⊕k)⊕k=x⊕(k⊕k)=x⊕0=x. This is the mathematical core of the one-time pad and connects bitwise logic straight to the cryptography content of the data-representation topic.

---

Masks

A mask is a chosen bit pattern combined with data using a bitwise operator to act on specific bit positions while leaving others untouched. There are four canonical mask operations, each pairing an operator with a mask whose 1-bits mark the positions of interest.

Setting bits (force to 1) — use OR

OR-ing with a 1 forces that bit to 1; OR-ing with a 0 leaves the bit unchanged (because $x \text{ OR } 0 = x$x OR 0=x). To set bits 0 and 2 of $\texttt{01000001}$01000001, use mask $\texttt{00000101}$00000101:

	$b_7$b7​..$b_3$b3​	$b_2$b2​	$b_1$b1​	$b_0$b0​
Data	01000	0	0	1
Mask	00000	1	0	1
Data OR Mask	01000	1	0	1

Result $\texttt{01000101}$01000101 — bit 2 has been turned on, bit 0 was already 1 (unchanged), every masked-0 position untouched.

Clearing bits (force to 0) — use AND

AND-ing with a 0 forces that bit to 0; AND-ing with a 1 leaves the bit unchanged ($x \text{ AND } 1 = x$x AND 1=x). The mask has 0s where you want to clear and 1s elsewhere. To clear bit 6 of $\texttt{11010011}$11010011, use mask $\texttt{10111111}$10111111:

	$b_7$b7​	$b_6$b6​	$b_5$b5​..$b_0$b0​
Data	1	1	010011
Mask	1	0	111111
Data AND Mask	1	0	010011

Result $\texttt{10010011}$10010011 — only bit 6 changed.

Testing / checking a bit — use AND

To find out whether a particular bit is set, AND with a mask that has a 1 in only that position. A non-zero result means the bit was 1. To test bit 4 of $\texttt{00011000}$00011000, use mask $\texttt{00010000}$00010000:

$\texttt{00011000} \text{ AND } \texttt{00010000} = \texttt{00010000} \neq 0$00011000 AND 00010000=00010000=0

Non-zero, so bit 4 is set. The same AND against $\texttt{00000100}$00000100 would give $\texttt{00000000}$00000000 (zero), telling us bit 2 is clear.

Flipping / toggling bits — use XOR