Comp arithmetic GFG

Question 1

Arithmetic logic unit (ALU

Answer 1

mathematical brain of a computer. The first ALU was INTEL 74181 implemented as a 7400 series is a TTL integrated circuit that was released in 1970.

The ALU is a digital circuit that provides arithmetic and logic operations. It is the fundamental building block of the central processing unit of a computer. A modern CPU has a very powerful ALU and it is complex in design. In addition to ALU modern CPU contains a control unit and a set of registers. Most of the operations are performed by one or more ALU’s, which load data from the input register. Registers are a small amount of storage available to the CPU. These registers can be accessed very fast. The control unit tells ALU what operation to perform on the available data. After calculation/manipulation, the ALU stores the output in an output register.

Question 2

The CPU can be divided into two sections:

Answer 2

the data section and the control section.

Question 3

The DATA section is also known as

Answer 3

data path

Question 4

Bus

Answer 4

In early computers “BUS” were parallel electrical wires with multiple hardware connections. Therefore a bus is a communication system that transfers data between components inside a computer, or between computers. It includes hardware components like wires, optical fibers, etc and software, including communication protocols. The Registers, ALU, and the interconnecting BUS are collectively referred to as data paths.

Question 5

Address bus

Answer 5

The buses which are used to carry address.

Question 6

data bus

Answer 6

The buses which are used to carry data.

Question 7

control bus

Answer 7

If the bus is carrying control signals.

Question 8

power bus

Answer 8

If it is carrying clock pulse, power signals it is known as a power bus, and so on.

Question 9

program counter

Answer 9

A program counter (PC) is a CPU register in the computer processor which has the address of the next instruction to be executed from memory. As each instruction gets fetched, the program counter increases its stored value by 1. It is a digital counter needed for faster execution of tasks as well as for tracking the current execution point.

Question 10

Instruction register

Answer 10

In computing, an instruction register (IR) is the part of a CPU’s control unit that holds the instruction currently being executed or decoded. The instruction register specifically holds the instruction and provides it to the instruction decoder circuit.

Question 11

memory address register

Answer 11

The Memory Address Register (MAR) is the CPU register that either stores the memory address from which data will be fetched from the CPU, or the address to which data will be sent and stored. It is a temporary storage component in the CPU(central processing unit) that temporarily stores the address (location) of the data sent by the memory unit until the instruction for the particular data is executed.

Question 12

memory data register

Answer 12

The memory data register (MDR) is the register in a computer’s processor, or central processing unit, CPU, that stores the data being transferred to and from the immediate access storage. Memory data register (MDR) is also known as memory buffer register (MBR).

Question 13

One bus organization
NOT A RECOMMENDED ARCHITECTURE

Answer 13

a single bus is used for multiple purposes. A set of general-purpose registers, program counters, instruction registers, memory address registers (MAR), memory data registers (MDR) are connected with the single bus. Memory read/write can be done with MAR and MDR. The program counterpoints to the memory location from where the next instruction is to be fetched. Instruction register is that very register will hold the copy of the current instruction. In the case of one bus organization, at a time only one operand can be read from the bus.

As a result, if the requirement is to read two operands for the operation then the read operation needs to be carried twice. So that’s why it is making the process a little longer. One of the advantages of one bus organization is that it is one of the simplest and also this is very cheap to implement. At the same time a disadvantage lies that it has only one bus and this “one bus” is accessed by all general-purpose registers, program counter, instruction register, MAR, MDR making each and every operation sequential.

Question 14

Two bus organizations

Answer 14

To overcome the disadvantage of one bus organization another architecture was developed known as two bus organization. In two bus organizations, there are two buses. The general-purpose register can read/write from both the buses. In this case, two operands can be fetched at the same time because of the two buses. One bus fetch operand for ALU and another bus fetch for register. The situation arises when both buses are busy fetching operands, the output can be stored in a temporary register and when the buses are free, the particular output can be dumped on the buses.

Question 15

Three bus organization

Answer 15

In three bus organizations we have three buses, OUT bus1, OUT bus2, and an IN bus. From the out buses, we can get the operand which can come from the general-purpose register and evaluated in ALU and the output is dropped on In Bus so it can be sent to respective registers. This implementation is a bit complex but faster in nature because in parallel two operands can flow into ALU and out of ALU. It was developed to overcome the “busy waiting” problem of two bus organizations. In this structure after execution, the output can be dropped on the bus without waiting because of the presence of an extra bus.

Question 16

main advantages of multiple bus organizations over the single bus are as given below.

Answer 16

Increase in size of the registers.

Reduction in the number of cycles for execution.

Increases the speed of execution or we can say faster execution.

Question 17

sign magnitude

Answer 17

very simple representation of negative numbers. In sign magnitude the first bit is dedicated to represent the sign and hence it is called sign bit.

Question 18

Sign bit ‘1’ represents ______ sign.

Answer 18

negative

Question 19

Sign bit ‘0’ represents _____ sign.

Answer 19

positive

Question 20

In sign magnitude representation of a n – bit number, the first bit will represent sign and rest n-1 bits represent magnitude of number.

Answer 20

+25 = 011001
-25 = 111001

Question 21

Range of number represented by sign magnitude method = -(2n-1-1) to +(2n-1-1) (for n bit number)

But there is one problem in sign magnitude and that is we have two representations of 0

Answer 21

+0 = 000000

– 0 = 100000

Question 22

2’s complement method

Answer 22

To represent a negative number in this form, first we need to take the 1’s complement of the number represented in simple positive binary form and then add 1 to it.

For example:

(-8)10 = (1000)2

1’s complement of 1000 = 0111

Adding 1 to it, 0111 + 1 = 1000

So, (-8)10 = (1000)2

Please don’t get confused with (8)10 =1000 and (-8)10=1000 as with 4 bits, we can’t represent a positive number more than 7. So, 1000 is representing -8 only.

Question 23

Range of number represented by 2’s complement

Answer 23

(-2^(n-1) to 2^(n-1) – 1)

Question 24

Normalization

Answer 24

Floating point numbers are usually normalized

Exponent is adjusted so that leading bit (MSB) of mantissa is 1

Since it is always 1 there is no need to store it

Scientific notation where numbers are normalized to give a single digit before the decimal point like in decimal system e.g. 3.123 x 103

Question 25

Number systems

Answer 25

Computers use different number systems to represent numerical quantities, including binary (base 2), decimal (base 10), and hexadecimal (base 16) systems. In binary system, each digit can only be either 0 or 1, while in decimal system, each digit can be any of the 10 digits from 0 to 9.

Question 26

Arithmetic operations

Answer 26

The basic arithmetic operations used in computer arithmetic are addition, subtraction, multiplication, and division. These operations are usually performed using arithmetic circuits within the CPU.

Question 27

Overflow

Answer 27

In computer arithmetic, overflow occurs when the result of an arithmetic operation is too large to be represented in the available number of bits. This can result in incorrect or unexpected results.

Question 28

Floating-point arithmetic

Answer 28

used to represent and perform operations on non-integer numbers. It involves representing a number as a combination of a mantissa (or significand) and an exponent.

Question 29

Round-off errors

Answer 29

Round-off errors occur in floating-point arithmetic due to the limited precision of the number representation. This can result in small inaccuracies in the computed results.

Question 30

Bitwise operations

Answer 30

Bitwise operations are used to manipulate individual bits in a number. The basic bitwise operations include AND, OR, XOR, and NOT.

Question 31

Two’s complement representation

Answer 31

Two’s complement representation is a method of representing negative numbers in binary. In this representation, the most significant bit is used as a sign bit, with 0 indicating a positive number and 1 indicating a negative number.

Question 32

floating point addition:
add 1.1 * 103 and 50

Answer 32

First, we need to align the exponent and then, we can add significant.

After aligning exponent, we get 50 = 0.05 * 103

Now adding significant, 0.05 + 1.1 = 1.15

So, finally we get (1.1 * 103 + 50) = 1.15 * 103

Here, notice that we shifted 50 and made it 0.05 to add these numbers.

Now let us take example of floating point number addition

We follow these steps to add two numbers:

1. Align the significant
2. Add the significant
3. Normalize the result
   Let the two numbers be

x = 9.75
y = 0.5625

Converting them into 32-bit floating point representation,

9.75’s representation in 32-bit format = 0 10000010 00111000000000000000000

0.5625’s representation in 32-bit format = 0 01111110 00100000000000000000000

Now we get the difference of exponents to know how much shifting is required.

(10000010 – 01111110)2 = (4)10

Now, we shift the mantissa of lesser number right side by 4 units.

Mantissa of 0.5625 = 1.00100000000000000000000

(note that 1 before decimal point is understood in 32-bit representation)

Shifting right by 4 units, we get 0.00010010000000000000000

Mantissa of 9.75 = 1. 00111000000000000000000

Adding mantissa of both

0. 00010010000000000000000

+ 1. 00111000000000000000000

————————————————-

1. 01001010000000000000000

In final answer, we take exponent of bigger number

So, final answer consist of :

Sign bit = 0

Exponent of bigger number = 10000010

Mantissa = 01001010000000000000000

32 bit representation of answer = x + y = 0 10000010 01001010000000000000000

Question 33

Floating point subtraction

Answer 33

Subtraction is similar to addition with some differences like we subtract mantissa unlike addition and in sign bit we put the sign of greater number.

Let the two numbers be

x = 9.75
y = – 0.5625

Converting them into 32-bit floating point representation

9.75’s representation in 32-bit format = 0 10000010 00111000000000000000000

– 0.5625’s representation in 32-bit format = 1 01111110 00100000000000000000000

Now, we find the difference of exponents to know how much shifting is required.

(10000010 – 01111110)2 = (4)10
Now, we shift the mantissa of lesser number right side by 4 units.

Mantissa of – 0.5625 = 1.00100000000000000000000

(note that 1 before decimal point is understood in 32-bit representation)

Shifting right by 4 units, 0.00010010000000000000000

Mantissa of 9.75= 1. 00111000000000000000000

Subtracting mantissa of both

0. 00010010000000000000000

– 1. 00111000000000000000000

————————————————

1. 00100110000000000000000

Sign bit of bigger number = 0

So, finally the answer = x – y = 0 10000010 00100110000000000000000

Question 34

Signed vs unsigned numbers

Answer 34

In computer arithmetic, numbers can be either signed or unsigned. Unsigned numbers only represent positive values, while signed numbers can represent both positive and negative values. Signed numbers are typically represented using two’s complement notation.

Question 35

shift operations

Answer 35

Shift operations are used to move the bits of a number left or right. A left shift multiplies the number by 2 raised to the power of the number of shifted bits, while a right shift divides the number by 2 raised to the power of the number of shifted bits.

Question 36

logical vs arithmetic shifts

Answer 36

Shift operations can be either logical or arithmetic. Logical shifts insert zeros into the vacant bit positions, while arithmetic shifts preserve the sign bit when shifting a signed number.

Question 37

carry and borrow

Answer 37

In addition and subtraction operations, carry and borrow refer to the bit that is carried over or borrowed from the next digit position when the result of an operation exceeds the number of bits available.

Question 38

Boolean algebra

Answer 38

Boolean algebra is a branch of mathematics that deals with logical operations on binary variables. It is widely used in computer arithmetic for operations such as bitwise AND, OR, and XOR.

Question 39

fixed-point arithmetic

Answer 39

Fixed-point arithmetic is used to perform arithmetic operations on numbers with a fixed number of decimal places. It is commonly used in applications such as digital signal processing.

Question 40

Division algorithms

Answer 40

There are various algorithms used to perform division in computer arithmetic, including the restoring division algorithm, non-restoring division algorithm, and SRT division algorithm.

Question 41

Multiplication algorithms

Answer 41

There are also various algorithms used to perform multiplication in computer arithmetic, including the Booth’s algorithm, the array multiplier, and the Wallace tree multiplier.

Question 42

1’s complement of a binary number is another binary number obtained by toggling all bits in it, i.e., transforming the 0 bit to 1 and the 1 bit to 0. Examples:

Answer 42

Let numbers be stored using 4 bits

1’s complement of 7 (0111) is 8 (1000)
1’s complement of 12 (1100) is 3 (0011)

Question 43

2’s complement of a binary number is 1 added to the 1’s complement of the binary number. Examples:

Answer 43

Let numbers be stored using 4 bits

2’s complement of 7 (0111) is 9 (1001)
2’s complement of 12 (1100) is 4 (0100)

Question 44

The main difference between 1′ s complement and 2′ s complement is that 1′ s complement has two representations of 0 (zero) — 00000000, which is positive zero (+0), and 11111111, which is negative zero (-0); whereas in 2′ s complement, there is only one representation for zero — 00000000 (0) because if we add 1 to 11111111 (-1), we get 100000000, which is nine bits long. Since only eight bits are allowed, the left-most bit is discarded(or overflowed), leaving 00000000 (-0) which is the same as positive zero. This is the reason why 2′ s complement is generally used.

Answer 44

Another difference is that while adding numbers using 1′ s complement, we first do binary addition, then add in an end-around carry value. But, 2′ s complement has only one value for zero and doesn’t require carry values.

Range of 1’s complement for n bit number is from -2n-1-1 to 2n-1-1 whereas the range of 2’s complement for n bit is from -2n-1 to 2n-1-1.

There are 2n-1 valid numbers in 1’s complement and 2n valid numbers in 2’s complement.

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Question 45

A division algorithm provides a quotient and a remainder when we divide two number.

Answer 45

They are generally of two type slow algorithm and fast algorithm. Slow division algorithm are restoring, non-restoring, non-performing restoring, SRT algorithm and under fast comes Newton–Raphson and Goldschmidt.

Question 46

Division algorithm for unsigned integer steps

Answer 46

Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)

Step-2: Then the content of register A and Q is shifted left as if they are a single unit

Step-3: Then content of register M is subtracted from A and result is stored in A

Step-4: Then the most significant bit of the A is checked if it is 0 the least significant bit of Q is set to 1 otherwise if it is 1 the least significant bit of Q is set to 0 and value of register A is restored i.e the value of A before the subtraction with M

Step-5: The value of counter n is decremented

Step-6: If the value of n becomes zero we get of the loop otherwise we repeat from step 2

Step-7: Finally, the register Q contain the quotient and A contain remainder

Question 47

Non-Restoring Division For Unsigned Integer steps

Answer 47

Step-1: First the registers are initialized with corresponding values (Q = Dividend, M = Divisor, A = 0, n = number of bits in dividend)

Step-2: Check the sign bit of register A

Step-3: If it is 1 shift left content of AQ and perform A = A+M, otherwise shift left AQ and perform A = A-M (means add 2’s complement of M to A and store it to A)

Step-4: Again the sign bit of register A

Step-5: If sign bit is 1 Q[0] become 0 otherwise Q[0] become 1 (Q[0] means least significant bit of register Q)

Step-6: Decrements value of N by 1

Step-7: If N is not equal to zero go to Step 2 otherwise go to next step

Step-8: If sign bit of A is 1 then perform A = A+M

Step-9: Register Q contains quotient and A contains remainder.

Question 48

N-bit 2’s Complement representation for signed Integer can represent numbers from

Answer 48

-2^(n-1) to 2^(n-1)-1

Question 49

4 Bit can represent numbers from ( -8 to 7 )
5 Bit can represent numbers from ( -16 to 15 ) in 2’s Complimentary System.

Answer 49

Overflow Occurs with respect to addition when 2 N-bit 2’s Complement Numbers are added and the answer is too large to fit into that N-bit Group.

A computer has N-Bit Fixed registers. Addition of two N-Bit Number will result in a max N+1 Bit number. That Extra Bit is stored in the carry Flag. But Carry does not always indicate overflow.

Question 50

Overflow occurs when

Answer 50

Two negative numbers are added and an answer comes positive or

Two positive numbers are added and an answer comes as negative.

Question 51

How the negative numbers are stored in memory?

Answer 51

Suppose the following fragment of code, int a = -34; Now how will this be stored in memory. So here is the complete theory. Whenever a number with minus sign is encountered, the number (ignoring minus sign) is converted to its binary equivalent. Then the two’s complement of the number is calculated. That two’s complement is kept at place allocated in memory and the sign bit will be set to 1 because the binary being kept is of a negative number. Whenever it comes on accessing that value firstly the sign bit will be checked if the sign bit is 1 then the binary will be two’s complemented and converted to equivalent decimal number and will be represented with a minus sign.

Let us take an example:
Example –
int a = -2056;
Binary of 2056 will be calculated which is:

00000000000000000000100000001000 (32 bit representation, according of storage of int in C)
2’s complement of the above binary is:
11111111111111111111011111111000.

So finally the above binary will be stored at memory allocated for variable a.
When it comes on accessing the value of variable a, the above binary will be retrieved from the memory location, then its sign bit that is the left most bit will be checked as it is 1 so the binary number is of a negative number so it will be 2’s complemented and when it will be 2’s complemented will be get the binary of 2056 which is:
00000000000000000000100000001000

The above binary number will be converted to its decimal equivalent which is 2056 and as the sign bit was 1 so the decimal number which is being gained from the binary number will be represented with a minus sign. In our case -2056.

Question 52

Conventional computing

Answer 52

Conventional computing is based on the classical phenomenon of electrical circuits being in a single state at a given time, either on or off.

Information storage and manipulation is based on “bit”, which is based on voltage or charge; low is 0 and high is 1.

The circuit behavior is governed by classical physics.

Conventional computing use binary codes i.e. bits 0 or 1 to represent information.

CMOS transistors are the basic building blocks of conventional computers.

In conventional computers, data processing is done in Central Processing Unit or CPU, which consists of Arithmetic and Logic Unit (ALU), processor registers and a control unit.

Question 53

Quantum Computing

Answer 53

Quantum computing is based on the phenomenon of Quantum Mechanics, such as superposition and entanglement, the phenomenon where it is possible to be in more than one state at a time.

Information storage and manipulation is based on Quantum Bit or “qubit”, which is based on the spin of electron or polarization of a single photon.

The circuit behavior is governed by quantum physics or quantum mechanics.

Quantum computing use Qubits i.e. 0, 1 and superposition state of both 0 and 1 to represent information.

Superconducting Quantum Interference Device or SQUID or Quantum Transistors are the basic building blocks of quantum computers.

In quantum computers, data processing is done in Quantum Processing Unit or QPU, which consists of a number of interconnected qubits.

Question 54

Advantages of conventional computing

Answer 54

Well-established: Conventional computing is well-established and widely used in many applications.

Cost-effective: Conventional computing is cost-effective and accessible to many users, as it does not require specialized hardware.

Fast for certain types of problems: Conventional computing is fast and efficient for problems that can be easily broken down into sequential steps and for problems that do not involve large numbers of variables.

Deterministic: Conventional computing is deterministic, meaning that given the same inputs, the output is always the same.

Question 55

Disadvantages of conventional computing

Answer 55

Limited parallel processing: Conventional computing can perform limited parallel processing, which can limit its performance for certain types of problems.

Inefficient for certain types of problems: Conventional computing can be inefficient for certain types of problems that involve large numbers of variables or complex relationships.

Limited by classical physics: Conventional computing is limited by classical physics, which can make certain types of problems impossible to solve or prohibitively difficult.

Question 56

Advantages of quantum computing

Answer 56

Massive parallel processing: Quantum computing can perform massive parallel processing, which can enable faster solutions for certain types of problems.

Efficient for certain types of problems: Quantum computing is efficient for certain types of problems that involve large numbers of variables or complex relationships.

Non-deterministic: Quantum computing is non-deterministic, which can enable the exploration of many potential solutions simultaneously.

Question 57

Disadvantages of quantum computing

Answer 57

Specialized hardware: Quantum computing requires specialized hardware, including cryogenic equipment to maintain the qubits at low temperatures and specialized control electronics to manipulate the qubits.

Expensive: Quantum computing is expensive, as it requires specialized hardware and expertise.

Limited applicability: Quantum computing is highly specialized and is suited for certain types of problems, making it less applicable for many applications.

Fragile: Quantum computing is fragile and sensitive to external disturbances, which can cause errors in computations.

Question 58

Booth algorithm gives a procedure for multiplying binary integers in signed 2’s complement representation in efficient way, i.e., less number of additions/subtractions required. It operates on the fact that strings of 0’s in the multiplier require no addition but just shifting and a string of 1’s in the multiplier from bit weight 2^k to weight 2^m can be treated as 2^(k+1 ) to 2^m. As in all multiplication schemes, booth algorithm requires examination of the multiplier bits and shifting of the partial product. Prior to the shifting, the multiplicand may be added to the partial product, subtracted from the partial product, or left unchanged according to following rules:

Answer 58

The multiplicand is subtracted from the partial product upon encountering the first least significant 1 in a string of 1’s in the multiplier

The multiplicand is added to the partial product upon encountering the first 0 (provided that there was a previous ‘1’) in a string of 0’s in the multiplier.

The partial product does not change when the multiplier bit is identical to the previous multiplier bit.

Question 59

Booths algorithm advantages

Answer 59

Faster than traditional multiplication: Booth’s algorithm is faster than traditional multiplication methods, requiring fewer steps to produce the same result.

Efficient for signed numbers: The algorithm is designed specifically for multiplying signed binary numbers, making it a more efficient method for multiplication of signed numbers than traditional methods.

Lower hardware requirement: The algorithm requires fewer hardware resources than traditional multiplication methods, making it more suitable for applications with limited hardware resources.

Widely used in hardware: Booth’s algorithm is widely used in hardware implementations of multiplication operations, including digital signal processors, microprocessors, and FPGAs.

Question 60

Booths algorithm disadvantages

Answer 60

Complex to understand: The algorithm is more complex to understand and implement than traditional multiplication methods.

Limited applicability: The algorithm is only applicable for multiplication of signed binary numbers, and cannot be used for multiplication of unsigned numbers or numbers in other formats without additional modifications.

Higher latency: The algorithm requires multiple iterations to calculate the result of a single multiplication operation, which increases the latency or delay in the calculation of the result.

Higher power consumption: The algorithm consumes more power compared to traditional multiplication methods, especially for larger inputs.

Best Case and Worst Case Occurrence: Best case is when there is a large block of consecutive 1’s and 0’s in the multipliers, so that there is minimum number of logical operations taking place, as in addition and subtraction. Worst case is when there are pairs of alternate 0’s and 1’s, either 01 or 10 in the multipliers, so that maximum number of additions and subtractions are required.