Lesson 7: Bitwise Manipulation and Masks

Introduction to Bit Manipulation

Bit Manipulation is a fundamental low-level programming technique that allows direct control of individual bits within binary data. This is a key advantage of assembly language and is essential for systems programming, hardware control, and performance optimization.

Two Primary Methods of Bit Manipulation

1. Shift Instructions: Move bits left or right within a binary number

• Logical shifts (left and right)
• Arithmetic shifts (right only)
• Used for multiplication and division by powers of 2

2. Logical Instructions with Masks: Use Boolean operations to modify specific bits

• AND, OR, XOR, NOT operations
• Bit masks to target specific bits
• Used to extract, clear, set, or toggle bits

Logical Binary Shifts

A logical binary shift moves all bits in a binary number left or right. This is a very efficient way for a computer to perform multiplication or division by powers of 2.

Logical Left Shift (Multiply)

Each left shift multiplies the number by 2. Bits move to the left, a '0' is added at the rightmost position, and the leftmost bit is discarded if it goes beyond the fixed number of bits.

When a binary number is shifted left logically, the most significant bit (MSB) is discarded and a 0 is shifted in to its place. The carry bit is set to the value of the MSB that was discarded.

Logical Right Shift (Divide)

Each right shift divides the number by 2 (integer division, remainder is discarded). Bits move to the right, a '0' is added at the leftmost position, and the rightmost bit is discarded.

When a binary number is shifted right logically, the least significant bit (LSB) is discarded and a 0 is shifted in to its place. The carry bit is set to the value of the LSB that was discarded.

Arithmetic Shifts?

A Logical Shift applies to both left and right shifts. In a left shift, bits are moved left, and the vacated least significant bit (LSB) is filled with a zero. In a right shift, bits are moved right, and the vacated MSB is also filled with a zero. Logical shifts treat the binary number as a sequence of bits without considering its signedness.

Arithmetic Shifts only applies to right shifts. Similar to a left logical shift, bits are moved right. However, the vacated MSB is filled with a copy of the original MSB (sign bit). This preserves the sign of the number during the shift. Arithmetic shifts are crucial for signed number operations, especially when dealing with negative numbers in two's complement representation.

Arithmetic Shift Right

Underflow and Overflow

Overflow occurs when the result of a calculation is too large to be held in the number of bits allocated.

For example, adding two integers in an 8-bit byte (ignore the sign bit). The result 260 cannot be stored in 8 bits (max 255), causing overflow.

Underflow occurs when a number is too small to be represented in the number of bits allocated.

It may occur if a very small number is divided by a number greater than 1.

Example: Shows a 8 bit binary number shifting one space to the right. The fractional part (.5) is lost when using integer shifts, representing a form of underflow where precision is too fine for the representation.

Bitwise Operations and Masks

Logic Gates and Truth Tables

Electronic circuits called logic gates perform Boolean functions on binary inputs. These gates form the basis of all digital logic circuits and correspond directly to bitwise operations in programming.

Truth Tables show the results of Boolean equations from all possible combinations of inputs.

• Used to show all possible outcomes from Boolean equations
• Also used for logic gate diagrams
• Systematically lists every possible input combination and its corresponding output

AND Gate

For an AND Gate the output is TRUE only if ALL inputs are TRUE.

Symbol:

Truth Table:

A	B	Z
0	0	0
0	1	0
1	0	0
1	1	1

Boolean Algebra Notation:

• Z = A ∧ B
• Z = A . B
• Z = A AND B
• Z = AB

OR Gate

For an OR Gate the output is TRUE if EITHER or ALL inputs are TRUE.

Symbol:

Truth Table:

A	B	Z
0	0	0
0	1	1
1	0	1
1	1	1

Boolean Algebra Notation:

• Z = A ∨ B
• Z = A + B
• Z = A OR B

NOT Gate

For a NOT Gate the output is the OPPOSITE (inverse) of the input.

Symbol:

Truth Table:

A	Z
0	1
1	0

Boolean Algebra Notation:

• Z = ¬A
• Z = Ā
• Z = NOT(A)
• Z = A'

XOR Gate (Exclusive OR)

For an XOR Gate the output is TRUE if only ONE input is TRUE.

Symbol:

Truth Table:

A	B	Z
0	0	0
0	1	1
1	0	1
1	1	0

Boolean Algebra Notation:

• Z = A ⊻ B
• Z = A ⊕ B
• Z = A XOR B

Boolean Logic and Masks

The instructions AND, OR and XOR can be summarised in the table below:

Input B is a mask, which in combination with the Boolean operator, will set, clear or toggle the input bits. Masking allows you to isolate, extract and edit a sequence of bits.

Bitwise - AND

The AND operator can be used to clear a particular set of bits, leaving the other bits unchanged.

To clear the rightmost 4 bits. We would use the Mask (11110000) with the AND operator.

Bitwise - OR

The OR operator may be used to set a particular bit, leaving the other bits unchanged. To set the bit 1, 4 and 8 (furthest left bit is bit 1). We would use the Mask (10010001) with the OR operator.

Bitwise - XOR

The XOR operator can be used to toggle a particular bit, leaving the other bits unchanged. To toggle the rightmost 4 bits. Leaving the leftmost 4 bits unchanged. We would use the Mask (00001111) with the XOR operator.

Real-World Applications

Subnet Masking in Networking

One of the most practical applications of bit masking is in computer networking, specifically for subnet masking. Network engineers use this technique to:

• Efficiently route traffic across complex networks
• Isolate specific sections of an IP address to distinguish between network and host portions
• Segment networks into smaller, manageable subnetworks

This fundamental concept enables efficient IP address management and forms the backbone of modern network architecture.

Lesson Summary

• Logical Shifts: Move bits left (multiply by 2) or right (divide by 2) for unsigned numbers
• Arithmetic Shifts: Right shifts that preserve sign bit for signed numbers
• Bitwise AND: Clears bits where mask is 0 - used for extracting/isolating bits
• Bitwise OR: Sets bits where mask is 1 - used for combining bit patterns
• Bitwise XOR: Toggles bits where mask is 1 - used for flipping/inverting bits
• Bit Masks: Binary patterns that determine which bits are affected by operations
• Overflow/Underflow: Occur when results exceed representable range in allocated bits
• Real Applications: Subnet masking, graphics, embedded systems, data compression
• Logic Gates: Hardware implementations of Boolean operations (AND, OR, NOT, XOR)