9618 AS Computer Science
Bit manipulation is one of the fastest operations a computer can perform. By using simple binary tricks, we can achieve substantial processing efficiency in control systems. Each bit in a byte can represent a different device or feature - turning lights on, checking sensors, or flagging errors!
A binary shift is an operation that moves all the bits in a binary number left or right by a certain number of positions. This is often used in programming for fast multiplication or division by powers of 2.
| Shift Type | Description | Best For |
|---|---|---|
| Logical Shift | Moves bits left/right, fills gaps with 0s | Unsigned numbers, raw bit manipulation |
| Arithmetic Shift | Moves bits, preserves sign bit (MSB) | Signed numbers (two's complement) |
| Cyclic Shift | Rotates bits around, nothing is lost | Encryption, checksums, bit rotation |
Remember: Left shift multiplies by 2 for each position shifted. Right shift divides by 2 for each position shifted. This is why shifts are much faster than actual multiplication or division operations!
Logical shifts move bits left or right and fill the empty positions with zeros. These are used for unsigned binary numbers or raw bit manipulation.
In a logical left shift, each bit is moved to the left. The empty space on the right is filled with zero, and the leftmost bit (MSB) that falls off is discarded.
Original: 000110 (binary) = 6 (decimal)
Shift left by 2: 000110 << 2
Result: 011000 (binary) = 24 (decimal)
Notice: 6 × 2² = 6 × 4 = 24 ✓ Each left shift doubles the value!
In a logical right shift, each bit is moved to the right. The empty space on the left (MSB position) is filled with zero, and the rightmost bit (LSB) that falls off is discarded.
Original: 0011001 (binary) = 25 (decimal)
Shift right by 1: 0011001 >> 1
Result: 0001100 (binary) = 12 (decimal)
Notice: 25 ÷ 2 = 12.5 → 12 (integer division) ✓ Each right shift halves the value!
| Logical Shift Direction | What Happens | Effect on Value |
|---|---|---|
| Left (<<) | All bits shift left, 0 fills rightmost bit | Multiplies by 2 for each position |
| Right (>>) | All bits shift right, 0 fills leftmost bit | Divides by 2 for each position |
Some processors do not have a built-in logical right shift - they only have an arithmetic right shift. Understanding the difference is crucial for handling signed vs unsigned numbers!
For a left shift of n positions: Value × 2ⁿ
For a right shift of n positions: Value ÷ 2ⁿ (integer division)
Arithmetic shifts are similar to logical shifts but preserve the sign bit (MSB) when shifting right. This is essential for working with signed binary numbers using two's complement representation.
Arithmetic left shifts work identically to logical left shifts. The bit is shifted to the left, zeroes are added at the right, and the sign bit (if any) is discarded.
In an arithmetic right shift, the bit is shifted to the right, but the most significant bit (sign bit) is copied to maintain the sign. The LSB is discarded.
Original: 10110100 (binary) = -76 in two's complement
Shift right by 3: 10110100 >> 3
Result: 11110110 (binary) = -10 in two's complement
The sign bit (1) is preserved - it gets copied into the new leftmost positions!
Original value: 11101000 = -24 (two's complement)
Each arithmetic right shift divides by 2, rounding towards negative infinity while preserving the sign bit.
| Shift Type | Left Shift | Right Shift | Used For |
|---|---|---|---|
| Logical | Shift bits left, fill with 0 | Shift bits right, fill with 0 | Unsigned numbers |
| Arithmetic | Same as logical left | Shift right, preserve sign bit | Signed numbers (two's complement) |
When asked about arithmetic vs logical shifts, always mention: (1) Logical shifts are for unsigned numbers, (2) Arithmetic shifts preserve the sign bit for signed numbers, (3) Arithmetic left shift is identical to logical left shift!
Cyclic shifts (also called rotations) move bits in a circular fashion - bits that fall off one end are reintroduced at the other end. No bits are lost during a cyclic shift!
Original: 10101111 (binary)
Cyclic left shift by 3:
Original: 10110001 = 177 (decimal)
Cyclic left by 3: 10001101 = 141 (decimal)
Cyclic right by 3: 00110010 = 50 (decimal)
| Shift Type | Left Shift | Right Shift | Application |
|---|---|---|---|
| Logical | Shift bits left, fill with 0 | Shift bits right, fill with 0 | Unsigned numbers, raw bits |
| Arithmetic | Same as logical left | Shift right, preserve sign bit | Signed numbers (two's complement) |
| Cyclic | Rotate bits left (no loss) | Rotate bits right (no loss) | Encryption, checksums, bit rotation |
Cyclic shifts are used in:
Logical/Arithmetic: Bits can be lost (fall off the end)
Cyclic: No bits lost - they wrap around!
Bit masking is the process of using binary patterns (masks) to test, set, clear, or toggle specific bits without affecting the others. This is essential for device control and monitoring systems.
A mask is a number used with logical operators (AND, OR, XOR, NOT) to identify, remove, or set a single bit or group of bits in an address or register.
| Operation | Operator | Purpose | Example Use |
|---|---|---|---|
| Check Bit | AND (&) | Test if a specific bit is 1 | Check if a sensor is active |
| Set Bit | OR (|) | Set specific bits to 1 | Turn ON a device |
| Clear Bit | AND with inverted mask | Set specific bits to 0 | Turn OFF a device |
| Toggle Bit | XOR (^) | Flip bits (0↔1) | Switch device state |
Advantage: Speeds up processing and requires less memory. Instead of using full bytes for each flag, we can pack 8 flags into a single byte!
The bitwise AND operation compares each bit position. It returns 1 only when BOTH bits are 1. This is used to test if specific bits are set.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Scenario: Check if heater (Bit 5) and light (Bit 4) are both ON
Binary: 10111001
Mask: 00110000 (1s at positions 5 and 4)
Result: 00110000 (non-zero = both ON)
Use AND to isolate specific bits. If result is non-zero, the bits were set. If result is zero, the bits were not set. AND with 1 preserves the bit; AND with 0 always gives 0.
The bitwise OR operation returns 1 if EITHER or BOTH bits are 1. Used to SET specific bits to 1 without changing others.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Scenario: Turn ON alarm (Bit 6) and door lock (Bit 5)
Binary: 11001010
Mask: 01100000 (1s at positions 6 and 5)
Result: 11101010 (bits 6 and 5 now set to 1)
The bitwise XOR (exclusive OR) returns 1 only when bits are DIFFERENT. Used to TOGGLE specific bits (flip 0↔1).
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Scenario: Toggle fan (Bit 5) and heating (Bit 4)
Binary: 10101010
Mask: 00110000 (1s at positions 5 and 4)
Result: 10011010 (bits 5 and 4 flipped)
XOR = "eXclusive OR" = Only ONE can be 1
Bit manipulation in assembly language uses specific instructions to work with individual bits in registers. ACC denotes Accumulator, IX denotes Index Register, # denotes a denary number, B denotes binary, & denotes hexadecimal.
LDD 0034 ; Load byte into ACC from address 0034
AND #B00000000 ; AND with all zeros - clears all bits
STO 0034 ; Store altered byte back to address 0034
Any bit ANDed with 0 becomes 0!
LDD 0034 ; Load byte into ACC from address 0034
OR #B00000100 ; OR with bit 2 set - sets bit 2 to 1
STO 0034 ; Store altered byte back to address 0034
Any bit ORed with 1 becomes 1. Other bits unchanged!
LDD 0034 ; Load byte into ACC from address 0034
XOR #B00000001 ; XOR with bit 0 set - toggles bit 0
STO 0034 ; Store altered byte back to address 0034
XOR with 1 flips the bit. XOR with 0 leaves bit unchanged!
LDD 0034 ; Load byte into ACC from address 0034
AND #B00000010 ; AND with mask - keeps bit 1, clears all others
STO 0034 ; Store altered byte back to address 0034
Result: Bit 1 preserved, all other bits become 0. Useful for checking a single flag!
| Operation | Mask Pattern | Effect |
|---|---|---|
| Clear all bits | B00000000 | All bits become 0 |
| Set bit 2 | B00000100 | Only bit 2 becomes 1 |
| Toggle bit 0 | B00000001 | Only bit 0 flips |
| Check bit 1 | B00000010 | All bits cleared except bit 1 |
Bits are numbered from right to left, starting at 0:
| Term | Definition |
|---|---|
| Binary Shift | An operation that moves all bits in a binary number left or right by a certain number of positions |
| Logical Shift | A shift where bits are moved and empty positions are filled with zeros; used for unsigned numbers |
| Arithmetic Shift | A shift that preserves the sign bit (MSB) when shifting right; used for signed numbers |
| Cyclic Shift | A rotation where bits that fall off one end are reintroduced at the other end; no bits lost |
| Bit Mask | A binary pattern used with logical operators to test, set, clear, or toggle specific bits |
| MSB | Most Significant Bit - the leftmost bit with highest positional value (bit 7 in an 8-bit number) |
| LSB | Least Significant Bit - the rightmost bit with lowest positional value (bit 0) |
| AND Operation | Bitwise operation that returns 1 only when both bits are 1; used to check/clear bits |
| OR Operation | Bitwise operation that returns 1 if either or both bits are 1; used to set bits |
| XOR Operation | Bitwise operation that returns 1 only when bits are different; used to toggle bits |
| Toggle | To switch a bit from 0 to 1 or from 1 to 0 (flip the bit) |
| Flag | A single bit used to indicate the status of a condition or device (on/off, true/false) |
| ACC | Accumulator - a register used for arithmetic and logical operations |
Answer:
Additional: The two leftmost bits (00) were discarded, and two zeros were added on the right.
Answer:
Additional: Arithmetic right shift divides negative numbers correctly while preserving sign; logical right shift treats all numbers as unsigned.
Answer:
Additional: Original value = 175 decimal, Result = 125 decimal (values change but all bits preserved).
Answer:
LDD address ; Load byte into ACC
OR #B00001000 ; OR with mask to set bit 3
STO address ; Store back to memory
Additional: OR with 1 sets the bit to 1; OR with 0 leaves other bits unchanged.
Answer:
Additional: This technique is useful for toggling device states (ON↔OFF) in control systems.
Answer:
Additional: In assembly: LDD address, AND #B00100000, then check if ACC = 0 (bit clear) or ≠ 0 (bit set).
Answer:
Additional: -24 ÷ 2 = -12, -12 ÷ 2 = -6. The arithmetic shift correctly preserves the negative sign.
Answer:
LDD address ; Load byte into ACC
AND #B11001111 ; AND clears bits 4 and 5
STO address ; Store result
Answer:
Answer:
First operation (AND):
Second operation (OR):
Overall effect: Clear lower nibble, then set specific bits. This is useful for configuring device states where some bits must be cleared before setting new values.
| Topic | Key Point |
|---|---|
| Logical Left Shift | Bits move left, 0 fills right, MSB discarded → Multiply by 2 |
| Logical Right Shift | Bits move right, 0 fills left, LSB discarded → Divide by 2 |
| Arithmetic Right Shift | Same as logical but sign bit preserved |
| Cyclic Shift | Bits rotate, nothing lost |
| AND | Check bits (result ≠ 0 = set) or Clear bits (AND with 0) |
| OR | Set bits to 1 (OR with 1) |
| XOR | Toggle bits (XOR with 1) |
Bit manipulation is one of the most fundamental and efficient operations in computing. Understanding how to manipulate individual bits gives you powerful control over hardware, enables optimization of algorithms, and forms the foundation for cryptography and data compression!