Lab Report On

Addition and Subtraction of two unsigned binary

numbers
Aadesh Manandhar Anuja Gyawali Anupa Ranabhat Asmit Phuyal
079BCT001 079BCT020 079BCT021 079BCT024

Abstract—This report explores the fundamentals of integer TABLE I

addition and subtraction in binary, focusing on the algorithms T RUTH TABLE OF FULL ADDER CIRCUIT
used by computer processors at the hardware level. It details our
lab experiment where we implemented these algorithms using Inputs Outputs
A B C-in Sum C-Out
Python. The report includes the source code and output of our
0 0 0 0 0
implementation. Our main goal was to replicate the process as 0 0 1 1 0
closely as possible to how it occurs in a computer’s Arithmetic 0 1 0 1 0
Logic Unit (ALU), aiming to deepen our understanding of 0 1 1 0 1
computer architecture. The document covers both the theoretical 1 0 0 1 0
aspects of binary arithmetic algorithms and their practical 1 0 1 0 1
application through programming. 1 1 0 0 1
1 1 1 1 1
I NTRODUCTION
A. Addition of two unsigned binary number
B. Subtraction of two unsigned binary number
Adding unsigned binary numbers relies on full adder cir-
cuits. A full adder is a combinational logic circuit that per- Subtraction is the basic arithmetic operation. In digital
forms arithmetic addition on three input bits. Two of these computers, complement is used for simplifying subtraction.
inputs are the binary digits to be added, typically labeled ’A’ There are two types of complements for base 2 system: 1’s
and ’B’. The third input, ’Cin’, represents the carry from the complement and 2’s complement.
previous lower significant bit position. After processing these The 1’s complement of a binary number is obtained by
three inputs, the full adder produces two outputs: the sum subtracting each digit from 1. However, the subtraction of a
’S’ and the carry-out ’Cout’. The relationship between all binary digit from 1 causes the bit to change from 0 to 1 or from
possible input combinations and their corresponding outputs 1 to 0. Therefore, the 1’s complement of a binary number is
is illustrated in a truth table. formed by changing 1’s into 0’s and 0’s into 1’s. For example,
The mathematical expression for the full adder circuit is 1’s complement of 0111 is 1000.
given by: 2’s complement can be formed by leaving all least signifi-
cant 0’s and first 1 unchanged, and then replacing 1’s by 0’s
S = (A + B + C) mod 2 (1) and 0’s by 1’s in all other higher significant bits.
Each exclusive-OR gate receives input M and one of the
  input bits of Y. We have:
A+B+C
Cout = (2)
2 Y +1=Y′ (5)
The logical expression for a full adder is:
C0 = 1 (6)
S = A ⊕ B ⊕ Cin (3)
The Y inputs are all complemented, and a 1 is added through
the input carry. The circuit performs the operation X plus the
Cout = AB + (A ⊕ B) · Cin (4)
2’s complement of Y. For unsigned numbers, this gives:
An N-bit full adder is constructed by cascading n number • X - Y if X ≥ Y
of full adders, where the output carry from one full adder is • The 2’s complement of (Y - X) if X < Y
the input carry for the next full adder.
 I MPLEMENTATION IN P YTHON P ROGRAM C ODE
To simulate binary addition and subtraction at the bit level, A. Addition of two unsigned binary numbers
we implemented a Bit class in Python. This class represents The following Python code implements the addition of two
individual binary bits with value ”0” or ”1” and overloads unsigned binary numbers. This complements the earlier Bit
operators to perform logical bit operations akin to those used class.
in hardware full adders.
1 from bit import Bit, BitType
1 2
2 from __future__ import annotations 3 def full_adder(a: BitType, b: BitType, c: BitType):
3 from typing import Literal 4 if (type(a) == str):
4 5 a = Bit(a)
5 BitType = Literal["0", "1"] 6
6 7 if (type(b) == str):
7 class Bit: 8 b = Bit(b)
8 9
9 def __init__(self, bit_value: BitType): 10 if (type(c) == str):
10 if (bit_value not in ["0", "1"]): 11 c = Bit(c)
11 raise ValueError("Invalid Bit value") 12
12 13
13 self.value: str = bit_value 14 S = a ˆ b ˆ c
14 15 C = (a & b) | (b & c) | (c & a)
15 def __str__(self): 16
16 return self.value 17 return {"sum": S.value, "carry": C.value}
17 18
18 def __repr__(self): 19 def n_bit_adder(A: str, B: str, n:int = 8):
19 return self.value 20
20 21 A = A.rjust(n, "0")[::-1][:n]
21 def __or__(self, another: Bit) -> Bit: 22 B = B.rjust(n, "0")[::-1][:n]
22 return Bit("1") if (self.value == "1" or 23
another.value == "1") else Bit("0") 24
23 25 for char in (A + B):
24 def __add__(self, another: Bit) -> Bit: 26 if char not in ["0", "1"]:
25 return (self | another) 27 raise ValueError("Invalid Bit Value")
26 28
27 def __sub__(self, another: Bit) -> Bit: 29 output = ""
28 return (self | another) 30 carry_value = "0"
29 31 for i in range(n):
30 def __and__(self, another: Bit) -> Bit: 32 result = full_adder(A[i], B[i], carry_value)
31 return Bit("1") if (self.value == "1" and 33 carry_value = result["carry"]
another.value == "1") else Bit("0") 34 output = result["sum"] + output
32 35
33 def __mult__(self, another: Bit) -> Bit: 36 return { "sum": output, "carry": carry_value }
34 return (self & another)
35 Listing 2. Addition of two unsigned binary numbers
36 def __eq__(self, another: Bit):
37 return self.value == another.value
38
B. Subtraction of two unsigned binary numbers
39 @property The following Python code implements the subtraction of
40 def NOT(self) -> Bit:
41 return Bit("1") if (self.value == "0") else two unsigned binary numbers. This complements the earlier
Bit("0") Bit class.
42
43 def __xor__(self, another) -> Bit: 1 from bit import Bit
2
44 return Bit("1") if self.value != another.
value else Bit("0") 3 def full_subtractor(x: Bit, y: Bit, b: Bit):
4
45
46 def convert_to_decimal(number: str): 5 if (type(x) == str):
47 number = number[::-1] 6 x = Bit(x)
7
48 decimal = 0
49 for i, char in enumerate(number): 8 if (type(y) == str):
50 decimal += 2 ** i if char == "1" else 0 9 y = Bit(y)
10
51 return decimal
11 if (type(b) == str):
Listing 1. Bit class implementation in Python 12 b = Bit(b)
13

The Bit class enables simulation of bitwise logic oper- 14 D = x ˆ y ˆ b

15 B = (x.NOT & y) | (y & b) | (b & x.NOT)
ations necessary for understanding and implementing binary 16
arithmetic at a low level, closely mirroring hardware behavior 17 return { "diff": D.value, "borrow": B.value }
in the ALU. The convert_to_decimal function assists 18
19 def n_bit_subtractor(A: str, B: str):
in validating binary results by converting binary strings to 20 n = max(len(A), len(B))
decimal numbers. 21
22 B. Subtraction of Two Unsigned Binary Numbers
23 A = A.rjust(n, "0")[::-1]
24 B = B.rjust(n, "0")[::-1] Test 1: Subtracting smaller number from a larger number
25
26
Input A = 00001010 (decimal 10)
27 for char in (A + B): Input B = 00000101 (decimal 5)
28 if char not in ["0", "1"]:
29 raise ValueError("Invalid Bit Value")
30
Output:
31 output = "" Difference = 00000101 (decimal 5)
32 borrow_value = "0" Borrow = 0
33 for i in range(n):
34 result = full_subtractor(A[i], B[i], This test subtracts 5 from 10 successfully. The difference is
borrow_value)
35 borrow_value = result["borrow"] 00000101 which equals decimal 5. No borrow occurs since
36 output = result["diff"] + output the minuend is larger.
37
38 return { "diff": output, "borrow": borrow_value
}
Test 2: Subtracting equal numbers

Listing 3. Subtraction of two unsigned binary numbers

Input A = 00001111 (decimal 15)
Input B = 00001111 (decimal 15)

R ESULTS AND O UTPUT Output:

A. Addition of two unsigned binary numbers Difference = 00000000 (decimal 0)
Borrow = 0
Test 1: Adding two positive 8-bit binary numbers
Here, subtracting the same number results in zero difference
Input A = 00000101 (decimal 5)
and no borrow, indicating correct zero detection and no
Input B = 00000011 (decimal 3)
underflow.
Output: Test 3: Subtracting larger number from a smaller number
Sum = 00001000 (decimal 8) (underflow)
Carry = 0
Input A = 00000100 (decimal 4)
This test adds 5 and 3 using the 8-bit adder. The correct binary Input B = 00001000 (decimal 8)
sum is 00001000, which corresponds to decimal 8. There is
no carry out, indicating the sum fits within 8 bits. Output:
Difference = 1111100 (two's complement
Test 2: Adding numbers with carry generation
representation)
Input A = 11111111 (decimal 255) Borrow = 1
Input B = 00000001 (decimal 1) Overall Interpretation:
The implementations of the full adder and full subtractor,
Output: along with their respective n-bit adder and subtractor func-
Sum = 00000000 (decimal 0) tions, accurately perform basic binary arithmetic operations on
Carry = 1 fixed-length inputs. The n-bit adder correctly computes sums
Here, adding 255 and 1 results in overflow beyond 8 bits. The and carries, handling cases that fit within the bit-width as well
sum wraps around to zero and the carry bit is set to 1, correctly as those that overflow, with proper bitwise carry propagation.
reflecting the overflow from the most significant bit. Similarly, the n-bit subtractor precisely computes differences
and borrow signals, managing normal subtraction without
Test 3: Adding zero to a number borrow, zero difference, and underflow cases where a borrow
is required. The borrow propagation correctly indicates when
Input A = 00000000 (decimal 0)
the minuend is insufficient for subtraction. Together, these
Input B = 10101010 (decimal 170)
components demonstrate robust, low-level binary arithmetic
suitable for unsigned numbers, providing reliable building
Output:
blocks for more complex binary operations.
Sum = 10101010 (decimal 170)
Carry = 0
Adding zero leaves the other number unchanged, as expected.
There is no carry, confirming no overflow or additional carry
propagation.
 D ISCUSSION AND C ONCLUSION
A. Discussion
Our laboratory experiment focused on implementing binary
addition and subtraction algorithms using Python. The binary
addition process produced accurate results, with one exception:
when the sum exceeded 8 bits, the carry was omitted, and
only the least significant 8 bits were displayed. For binary
subtraction, we employed two’s complement representation for
negative numbers. This representation could be easily con-
verted to signed notation by applying the two’s complement
to the result. Our work demonstrated that binary addition and
subtraction can be effectively implemented using the logical
expressions associated with full adder and full subtractor cir-
cuits. Additionally, we explored the two’s complement method
for binary subtraction, which mirrors the approach used in ac-
tual computer architectures. This experiment provided insights
into the fundamental arithmetic operations performed at the
hardware level in computers.
B. Conclusion
The lab was concluded successfully with the implementa-
tion of binary addition and subtraction algorithms with the
preferred programming language being Python. The results
were accurate and demonstrated a clear understanding of
binary arithmetic operations, showcasing the effectiveness of
the developed algorithms in performing fundamental compu-
tational tasks.
ACKNOWLEDGMENT
We, the students of the Department of Electronics and
Computer Engineering, would like to express our heartfelt
gratitude to Prof. Dr. Subarna Sakya Sir, Bikal Adhikari
Sir, and everyone who supported us—both directly and in-
directly—throughout the successful completion of this lab
session. Their guidance and encouragement have been instru-
mental in maintaining the quality and accuracy of our work.
We also sincerely thank our classmates, whose valuable
discussions and collaborative spirit helped deepen our under-
standing of several concepts. This shared learning environment
has significantly enriched our academic experience, and we
truly appreciate the collective effort that made this lab both
meaningful and rewarding.
R EFERENCES
[1] M. Morris Mano, Computer System Architecture,3rd Edition.
[2] S. Shakya, Lab Manual on Computer Architecture and Design
 Lab Report On
Multiplication of Signed Binary number
using Booth’s Algorithm
Aadesh Manandhar Anuja Gyawali Anupa Ranabhat Asmit Phuyal
079BCT001 079BCT020 079BCT021 079BCT024

Abstract—In this experiment, Booth’s Algorithm was imple- Q0 Q−1 Operation

mented to multiply signed binary numbers using two’s com- 0 0 No operation
plement form. The algorithm helps make the multiplication 1 1 No operation
process more efficient, especially when the multiplier has a lot of 1 0 Subtract M from A (A = A − M )
consecutive 1s or 0s. It works by checking pairs of bits and then
doing arithmetic right shifts to calculate the result step by step.
0 1 Add M to A (A = A + M )
Doing this lab gave us a better understanding of how low-level
binary arithmetic works and how signed numbers are handled R EGISTERS U SED
in digital systems.
A Accumulator (initially 0)
Q Multiplier
I NTRODUCTION M Multiplicand
Booth’s algorithm is a binary multiplication algorithm de- Q−1 Extra bit (initially 0)
signed for signed integers using two’s complement repre- n Bit-width of the operands
sentation. It was introduced by Andrew Booth in 1951 and
is efficient in reducing the number of arithmetic operations A LGORITHM S TEPS
required during multiplication, especially when the multiplier 1) Initialize: A = 0, Q = multiplier, M = multiplicand,
has consecutive 1s. Q−1 = 0.
2) Repeat the following steps n times:
A DVANTAGES OF B OOTH ’ S A LGORITHM
• Check the pair (Q0 , Q−1 ) and perform the corre-
• Faster than traditional multiplication: Booth’s algo- sponding operation on A.
rithm is faster than traditional multiplication methods, • Perform arithmetic right shift on the combined
requiring fewer steps to produce the same result. [1] register: [A, Q, Q−1 ].
• Efficient for signed numbers: The algorithm is designed 3) After n cycles, the final product is in the combined
specifically for multiplying signed binary numbers, mak- register [A, Q].
ing it a more efficient method for multiplication of signed
numbers than traditional methods. [1]
• Lower hardware requirement: The algorithm requires D ISADVANTAGES OF B OOTH ’ S A LGORITHM
fewer hardware resources than traditional multiplication • Complex to understand: The algorithm is more complex
methods, making it more suitable for applications with to understand and implement than traditional multiplica-
limited hardware resources. [1] tion methods. [1]
• Widely used in hardware: Booth’s algorithm is widely • Limited applicability: The algorithm is only applicable
used in hardware implementations of multiplication oper- for multiplication of signed binary numbers, and cannot
ations, including digital signal processors, microproces- be used for multiplication of unsigned numbers or num-
sors, and FPGAs. [1] bers in other formats without additional modifications.
[1]
A LGORITHM P RINCIPLE • Higher latency: The algorithm requires multiple itera-
tions to calculate the result of a single multiplication
Booth’s algorithm examines two bits at a time:
operation, which increases the latency or delay in the
• Current bit (Q0 ) calculation of the result. [1]
• Previous bit (Q−1 ), initially 0 • Higher power consumption: The algorithm consumes
Based on the pair (Q0 , Q−1 ), the operation is chosen as more power compared to traditional multiplication meth-
follows: ods, especially for larger inputs. [1]
 32 return n_bit_adder(number, "1", len(number))["
sum"]
33
34
35 def n_bit_booths_multiplier(multiplicand: str,
multiplier: str, n: int = 8):
36 multiplier = multiplier[-n:].rjust(n, "0")
37 multiplicand = multiplicand[-n:].rjust(n, "0")
38 Q_neg_1 = "0"
39 A = "".rjust(n, "0")
40 Q = multiplier
41 add = 0
42 shift = 0
43 for _ in range(n):
44 if (Q_neg_1 == "0" and Q[-1] == "1"):
45 A = n_bit_adder(A, negation(multiplicand
), n)["sum"]
46 add += 1
47 elif (Q_neg_1 == "1" and Q[-1] == "0"):
48 A = n_bit_adder(A, multiplicand, n)["sum
"]
49 add += 1
50 Q_neg_1 = right_shifter(Q_neg_1, Q[-1])
51 Q = right_shifter(Q, A[-1])
52 A = right_shifter(A, A[0])
53 shift += 1
54 print(f"\n\nBooths Algorithm needed -> Shifts: {
shift}, Additions: {add}")
55 return A + Q
Fig. 1. Flowchart of Booth’s Algorithm
Listing 1. Booth’s Algorithm and Partial Product Algorithm in Python

C ODE R ESULTS AND O UTPUT

The modules bit and nBitAdder are included in lab report A. Program Output and Interpretation
no 1. Input 1: Multiplicand = 3, Multiplier = 2
1 from bit import BitType, convert_to_decimal Partial Product Algorithm needed -> Shifts: 8, Addi
2 from nBitAdder import n_bit_adder 3 x 2 =
3
4
The product is: 0000000000000110
5 def left_shifter(number: str) -> str: In Decimal it is: 6
6 number = "".join([*number[1:], "0"])
7 return number
8
Booths Algorithm needed -> Shifts: 8, Additions: 2
9 3 x 2 =
10 def n_bit_partial_multiplier(multiplicand: str, The product is: 0000000000000110
multiplier: str, n: int = 8):
11 multiplier = multiplier[-n:].rjust(n, "0")[::-1]
In Decimal it is: 6
12 multiplicand = multiplicand[-n:].rjust(2 * n, "0
")
In this case, both algorithms produced the correct result, 3 ×
13 product = "".rjust(2 * n, "0") 2 = 6. The Booth’s Algorithm required one more addition
14 add = 0 due to its handling of signed bit patterns. The partial product
15 shift = 0
16 for char in multiplier:
method required only one addition, since only one bit in the
17 if char == "1": multiplier was high. This confirms that both algorithms are
18 product = n_bit_adder(product, working correctly for positive numbers.
multiplicand, 2 * n)["sum"]
19 add += 1
20 multiplicand = left_shifter(multiplicand) Input 2: Multiplicand = 3, Multiplier = −5
21 shift += 1
22 print(f"\n\nPartial Product Algorithm needed -> Booths Algorithm needed -> Shifts: 8, Additions: 3
Shifts: {shift}, Additions: {add}") 3 x -5 =
23 return product The product is: 1111111111110001
24
25
Here, Booth’s algorithm successfully handles the multipli-
26 def right_shifter(number: str, bit: BitType):
27 number = "".join([bit, *number[:-1]]) cation of a positive number with a negative number using
28 return number two’s complement representation. The result in binary is
29
1111111111110001, which corresponds to −15 in deci-
30 def negation(number: int):
31 number = "".join(["0" if char == "1" else "1" mal. The correctness of the result demonstrates the strength
for char in number]) of Booth’s algorithm in signed multiplication scenarios.
 Input 3: Multiplicand = −3, Multiplier = −5 session. Their guidance and encouragement have been instru-
mental in maintaining the quality and accuracy of our work.
Booths Algorithm needed -> Shifts: 8, Additions: 3
We also sincerely thank our classmates, whose valuable
-3 x -5 =
discussions and collaborative spirit helped deepen our under-
The product is: 0000000000001111
standing of several concepts. This shared learning environment
In this case, the Booth’s algorithm yields a binary product has significantly enriched our academic experience, and we
of 0000000000001111, which equals 15 in decimal. This truly appreciate the collective effort that made this lab both
confirms that the implementation correctly handles multiplica- meaningful and rewarding.
tion of two negative numbers, where the final result is positive
R EFERENCES
as expected.
[1] GeeksforGeeks. Booth’s algorithm in computer organization, 2025.
Overall, the output confirms that Booth’s algorithm works Accessed: June 30, 2025.
correctly for all combinations of signed integers, including
positive-positive, positive-negative, and negative-negative mul-
tiplication. It also demonstrates that although more additions
may be required, the algorithm offers consistent and reliable
handling of sign bits.
I. D ISCUSSION AND C ONCLUSION
A. Discussion
While working on Booth’s Algorithm, we got to understand
how binary multiplication of signed numbers actually works
under the hood. After testing with both positive and negative
values, the results mostly matched what we expected, which
showed that the algorithm handles two’s complement correctly.
One thing we noticed was that Booth’s Algorithm reduced
the number of operations when the multiplier had a group of
1s or 0s. Instead of doing multiple additions or subtractions, it
did less steps, which made it a bit faster in those cases. But at
the same time, writing the logic to check bit pairs and decide
what to do made the code slightly more tricky than regular
multiplication.
Even though it works well, Booth’s method takes a few
more cycles because of the shifting and checking at each step.
So, it’s a trade-off between how simple the hardware can be
and how long it takes to get the final result.
B. Conclusion
In this lab, we were able to implement and test Booth’s
Algorithm for multiplying signed binary numbers. The algo-
rithm showed that it can handle both positive and negative
inputs properly and can also make multiplication a bit more
efficient when there are repeating bits.
Although the algorithm was more complex to write than the
regular method, it gave us a better idea of how these things
are actually done inside digital systems. Overall, it was a good
learning experience to see how signed multiplication is done
at the lower level, and it also helped us improve our logic
building while coding it.
ACKNOWLEDGMENT
We, the students of the Department of Electronics and
Computer Engineering, would like to express our heartfelt
gratitude to Prof. Dr. Subarna Sakya Sir, Bikal Adhikari
Sir, and everyone who supported us—both directly and in-
directly—throughout the successful completion of this lab
 Division of Two Unsigned Integer Binary
Numbers by Restoring and Non-Restoring
Algorithm
Aadesh Manandhar Anuja Gyawali Anupa Ranabhat Asmit Phuyal
079BCT001 079BCT020 079BCT021 079BCT024

Abstract—This report explains two common binary division al- 3) If MSB of A is 1, set the LSB of Q to 0; otherwise set
gorithms for unsigned integers: the Restoring and Non-Restoring it to 1.
methods. These methods are used at the processor level in 4) Decrement n.
computer architecture. Both are implemented in Python to closely
model how an Arithmetic Logic Unit (ALU) works, avoiding 5) Repeat until n = 0.
built-in arithmetic for the main steps. By simulating these 6) If MSB of A is 1, add M to A to obtain the final
algorithms, we get a clear idea of how division is handled inside remainder.
digital systems. 7) Q holds the quotient and A holds the remainder.

I Introduction
Binary division is a basic arithmetic operation handled by
processors. For unsigned integers, two widely used methods
are Restoring Division and Non-Restoring Division. Both
use registers: A (accumulator), Q (quotient register), and M
(divisor register), plus a counter for the number of bits. The
algorithms work by repeating shift and add/subtract steps.

I-A Restoring Division Algorithm

The restoring algorithm shifts, subtracts, and restores the
accumulator when the subtraction produces a negative result.
Steps:
1) Initialize registers: Q = dividend, M = divisor, A = 0,
n = number of bits in the dividend.
2) Shift A and Q left as a single unit.
3) Subtract M from A and store the result in A.
4) If the most significant bit of A is 0, set the least
significant bit of Q to 1. If it is 1, set the least
significant bit of Q to 0 and restore A to its value before
subtraction.
5) Decrement n.
6) Repeat from step 2 until n = 0.
7) Q holds the quotient and A holds the remainder.

I-B Non-Restoring Division Algorithm

The non-restoring algorithm avoids the restore step when a
subtraction makes A negative. Instead, it corrects in the next
iteration by adding.
Steps:
1) Initialize registers: Q = dividend, M = divisor, A = 0,
n = number of bits in the dividend.
2) If the MSB of A is 1, shift left A and Q, then add M
to A. If MSB is 0, shift left A and Q, then subtract M
from A. Fig. 1: Flowchart of Restoring Division method
 II Implementation
Below is the complete Python code used in this lab. Code
is included exactly as provided.

II-A Restoring Division

 
1 def AND(a, b):
2 return ’1’ if a == ’1’ and b == ’1’ else ’0’
3 def OR(a, b):
4 return ’1’ if a == ’1’ or b == ’1’ else ’0’
5 def XOR(a, b):
6 return ’1’ if a != b else ’0’
7 def NOT(a):
8 return ’0’ if a == ’1’ else ’1’
9
10 def SUM(a, b, c):
11 return XOR(XOR(a, b), c)
12
13 def CARRY(a, b, c):
14 return OR(OR(AND(a, b), AND(b, c)), AND(a, c
))
15
16 def binary_adder(a, b):
17 carry = ’0’
18 result = ’’
19 a, b = a.zfill(len(b)), b.zfill(len(a))
20 for i in range(len(a)-1, -1, -1):
21 s = SUM(a[i], b[i], carry)
22 carry = CARRY(a[i], b[i], carry)
23 result = s + result
24 return result[-len(a):]
25
26 def twos_complement(bin_str):
27 ones = ’’.join(NOT(b) for b in bin_str)
28 return binary_adder(ones, ’1’.zfill(len(
bin_str)))
29
30 def left_shift(A, Q):
31 shifted = A[1:] + Q[0]
32 new_Q = Q[1:] + ’0’
33 return shifted, new_Q
34
35 def subtract_binary(a, b):
36 b_neg = twos_complement(b)
37 return binary_adder(a, b_neg)[-len(a):]
38
39 def restoring_division(Q, M):
40 n = len(Q)
41 A = ’0’ * n
42 for _ in range(n):
43 A, Q = left_shift(A, Q)
44 A_temp = subtract_binary(A, M)
45 if A_temp[0] == ’0’:
46 A = A_temp
47 Q = Q[:-1] + ’1’
48 else:
49 A = binary_adder(A_temp, M)[-n:]
50 Q = Q[:-1] + ’0’
51 return Q, A
52
53 dividend = ’00001111’
54 divisor = ’00000111’
55
56 q, r = restoring_division(dividend, divisor)
57 print(f"Dividend:{dividend}")
58 print(f"Divisor: {divisor}")
59 print("Restoring Division Result:")
60 print(f"Quotient:{q}")
61 print(f"Remainder:{r}")
 
Listing 1: Restoring Division in Python

Fig. 2: Flowchart of Non-Restoring Division method

 II-B Non-Restoring Division III Results
 
1 def AND(a, b):
2 return ’1’ if a == ’1’ and b == ’1’ else ’0’
3 def OR(a, b):
4 return ’1’ if a == ’1’ or b == ’1’ else ’0’
5 def XOR(a, b):
6 return ’1’ if a != b else ’0’
7 def NOT(a):
8 return ’0’ if a == ’1’ else ’1’
9 def SUM(a, b, c):
10 return XOR(XOR(a, b), c)
11 def CARRY(a, b, c):
12 return OR(OR(AND(a, b), AND(b, c)), AND(a, c Fig. 3: Output of Restoring Division
))
13
14 def binary_adder(a, b):
15 carry = ’0’
16 result = ’’
17 a, b = a.zfill(len(b)), b.zfill(len(a))
18 for i in range(len(a)-1, -1, -1):
19 s = SUM(a[i], b[i], carry)
20 carry = CARRY(a[i], b[i], carry)
21 result = s + result
22 return result[-len(a):]
23
24 def twos_complement(bin_str):
25 ones = ’’.join(NOT(b) for b in bin_str) Fig. 4: Output of Non-Restoring Division
26 return binary_adder(ones, ’1’.zfill(len(
bin_str)))
27 IV Discussion and Conclusion
28 def left_shift(A, Q):
29 combined = A + Q Both algorithms produce the same quotient and remainder
30 shifted = combined[1:] + ’0’ for the same inputs. The restoring method is simpler to
31 return shifted[:len(A)], shifted[len(A):] understand but may perform extra work because it restores
32
33 def is_negative(binary): the accumulator when subtraction goes negative. The non-
34 return binary[0] == ’1’ restoring method skips this immediate restore, fixing the
35
value in a later step. This makes non-restoring better suited
36 def non_restoring_division(Q, M):
37 n = len(Q) for hardware where minimizing steps and control complexity
38 A = ’0’ * n is important. For small software examples, both are acceptable,
39 M = M.zfill(n) but non-restoring is often preferred in real hardware designs.
40 M_neg = twos_complement(M)
41
42 for _ in range(n): Acknowledgment
43 # Left shift A and Q We sincerely thank Prof. Dr. Subarna Sakya and Asst. Prof.
44 A, Q = left_shift(A, Q)
45
Bikal Adhikari for their invaluable guidance and support.
46 # Subtract M A = A - M We are also grateful to our classmates for their insightful
47 A = binary_adder(A, M_neg)[-n:] discussions and collaborative efforts, which greatly enhanced
48
49 if is_negative(A): our understanding of the concepts. Additionally, we appre-
50 Q = Q[:-1] + ’0’ ciate everyone who contributed, directly or indirectly, to the
51 else: successful completion of this lab session.
52 Q = Q[:-1] + ’1’
53
54 if is_negative(A): References
55 A = binary_adder(A, M)[-n:] [1] GeeksforGeeks, Restoring Division Algorithm for Unsigned
56
Integer,” https://www.geeksforgeeks.org/computer-organization-
57 return Q, A architecture/restoring-division-algorithm-unsigned-integer/.
58
[2] B. Acharya, COA — Division — Restoring and Non-restoring Division,”
59 dividend = ’00001111’ https://www.youtube.com/watch?v=H6EHzU9SY7M.
60 divisor = ’00000111’
61
62 q, r = non_restoring_division(dividend, divisor)
63 print(f"Dividend:{dividend}")
64 print(f"Divisor:{divisor}")
65 print("Non-Restoring Division Result:")
66 print(f"Quotient:{q}")
67 print(f"Remainder:{r}")
 
Listing 2: Non-Restoring Division in Python
 Lab Report On
Simulation of Page Replacement Algorithms (FIFO
and LRU) in Python
Aadesh Manandhar Anuja Gyawali Anupa Ranabhat Asmit Phuyal
079BCT001 079BCT020 079BCT021 079BCT024

Abstract—In this lab, two common page replacement algo- Steps:

rithms—FIFO (First-In-First-Out) and LRU (Least Recently 1) Initialize an empty list or dictionary to track pages and
Used)—were simulated using Python. Page replacement is a
memory management scheme that deals with the selection of their last used time.
pages to remove when memory is full. The aim was to compare 2) For each page in the reference string:
the efficiency of FIFO and LRU by measuring hits, misses, • If the page is already in memory, it’s a hit. Update
and hit ratios. This simulation provided a better understanding its last used time.
of how operating systems manage memory in multi-tasking
• If not:
environments.
– If memory is not full, insert the new page and
I NTRODUCTION store the current time as last used.
Page replacement algorithms are essential in operating – If memory is full, find the page with the earliest
systems for efficient memory management. These algorithms last used time and replace it with the new page.
select which memory pages should be changed when a new 3) Count hits and misses during the process.
page is brought. Least Recently Used (LRU) and First-In-First-
C ODE I MPLEMENTATION
Out (FIFO) are two popular page replacement algorithms.
• FIFO: Evicts the page that was loaded first. 1 class PageTable:
2 def __init__(self, frame_size):
• LRU: Evicts the least recently used page.
3 self.frame_size = frame_size
This lab aims to demonstrate these algorithms through simula- 4 self.frames = []
tion and compare their efficiency on a sample page reference 5 self.page_data = {}
6 self.time = 0
string. 7 self.hits = 0
8 self.misses = 0
A LGORITHM D ESCRIPTION 9 self.replacementAlg = "FIFO"
10
FIFO (First-In-First-Out) 11 def use_page(self, page):
The FIFO page replacement algorithm maintains the order 12 self.time += 1
13 if page in self.frames:
in which pages are added to memory. When the memory is 14 self.hits += 1
full and a new page needs to be loaded, it evicts the page that 15 self.page_data[page][’last_used’] = self
was loaded the earliest (i.e., the front of the queue). .time
16 self.page_data[page][’uses’] += 1
Steps: 17 else:
1) Initialize an empty queue for the page frames. 18 self.misses += 1
19 if len(self.frames) < self.frame_size:
2) For each page in the reference string: 20 self.frames.append(page)
• If the page is already in memory, it’s a hit. 21 self.page_data[page] = {
22 ’inserted’: self.time,
• If not:
23 ’last_used’: self.time,
– If memory is not full, insert the page at the end. 24 ’uses’: 1
}
– If memory is full, remove the page at the front 25 26 else:
(oldest) and insert the new page at the end. 27 self.replace_page(page)
28
3) Count hits and misses during the process.
29 def replace_page(self, new_page):
30 if self.replacementAlg == "FIFO":
LRU (Least Recently Used) 31 oldest = min(self.frames, key=lambda p:
The LRU algorithm replaces the page that has not been used self.page_data[p][’inserted’])
32 elif self.replacementAlg == "LRU":
for the longest period of time. It requires tracking each page’s 33 oldest = min(self.frames, key=lambda p:
usage time. self.page_data[p][’last_used’])
34 else: Process Involved in LRU page Replacement:
35 raise ValueError("Unknown algorithm")
36
37 self.frames[self.frames.index(oldest)] = Step Page Frame Content Hit/Miss Replaced Page
new_page 1 2 [2] Miss -
38 del self.page_data[oldest]
39 self.page_data[new_page] = { 2 3 [2, 3] Miss -
40 ’inserted’: self.time, 3 2 [2, 3] Hit -
41 ’last_used’: self.time, 4 1 [2, 3, 1] Miss -
42 ’uses’: 1
43 } 5 5 [2, 1, 5] Miss 3
44 6 2 [1, 5, 2] Hit -
45 sequence = [’2’, ’3’, ’2’, ’1’, ’5’, ’2’, ’4’, ’5’, 7 4 [5, 2, 4] Miss 1
’3’, ’2’, ’5’, ’2’]
46 frame_size = 3 8 5 [5, 2, 4] Hit -
47 9 3 [2, 4, 3] Miss 5
48 for algo in ["FIFO", "LRU"]: 10 2 [2, 4, 3] Hit -
49 print(f"\nUsing {algo}")
50 ptable = PageTable(frame_size) 11 5 [4, 3, 5] Miss 2
51 ptable.replacementAlg = algo 12 2 [3, 5, 2] Miss 4
52 for page in sequence:
53 ptable.use_page(page) D ISCUSSION
54 print("Final Frame:", ptable.frames)
55 print("Hits:", ptable.hits) As observed from the output, the LRU algorithm performed
56 print("Misses:", ptable.misses) better with a higher hit ratio (0.50) compared to FIFO (0.42).
57 print("Hit Ratio: {:.2f}".format(ptable.hits / ( LRU takes advantage of recent access history, which can result
ptable.hits + ptable.misses)))
in more hits when page references exhibit temporal locality.
Listing 1. Python Simulation of FIFO and LRU Page Replacement This proves that LRU performs better in reducing page faults
C ONCLUSION
S AMPLE O UTPUT
The experiment helped visualize how FIFO and LRU work
Using FIFO
in memory management. LRU generally provides better per-
Final Frame: [’2’, ’5’, ’3’]
formance but at a higher computational cost. FIFO is simpler
Hits: 5
but less optimal in scenarios with frequent page reuse. This
Misses: 7
simulation deepened our understanding of page replacement
Hit Ratio: 0.42
techniques used in operating systems.
Using LRU ACKNOWLEDGMENT
Final Frame: [’5’, ’2’, ’3’] We, the students of the Department of Electronics and
Hits: 6 Computer Engineering, would like to express our heartfelt
Misses: 6 gratitude to Prof. Dr. Subarna Sakya Sir, Bikal Adhikari
Hit Ratio: 0.50 Sir, and everyone who supported us—both directly and in-
directly—throughout the successful completion of this lab
R ESULTS AND O UTPUT session. Their guidance and encouragement have been instru-
mental in maintaining the quality and accuracy of our work.
Process Involved in FIFO page Replacement:
We also sincerely thank our classmates, whose valuable
discussions and collaborative spirit helped deepen our under-
Step Page Frame Content Hit/Miss Replaced Page standing of several concepts. This shared learning environment
1 2 [2] Miss - has significantly enriched our academic experience, and we
2 3 [2, 3] Miss - truly appreciate the collective effort that made this lab both
3 2 [2, 3] Hit - meaningful and rewarding.
4 1 [2, 3, 1] Miss -
5 5 [3, 1, 5] Miss 2 R EFERENCES
6 2 [1, 5, 2] Miss 3 [1] GeeksforGeeks. Page Replacement Algorithms in Operating Systems,
7 4 [5, 2, 4] Miss 1 Accessed: Aug. 2, 2025.
[2] M. M. Mano, Computer System Architecture, 3rd ed. Pearson Education,
8 5 [5, 2, 4] Hit - 2007.
9 3 [2, 4, 3] Miss 5
10 2 [2, 4, 3] Hit -
11 5 [4, 3, 5] Miss 2
12 2 [3, 5, 2] Miss 4