Binary Number operations using Doubly Linked List (DLL) by Mr. Aditya Kumbhar (S.E. Computer, PCCoE)9/2/2016 Doubly Linked List Assignment The aim of this program is to accept a binary number into a doubly linked list with each node containing one bit, and to perform the following operations on it: 1. Display the accepted binary number. 2. Perform One’s Complement 3. Perform Two’s Complement 4. Add two binary numbers The binary number will be accepted from the user and stored in an integer array. Structure Declaration: A structure is declared for creating the doubly linked list. typedef struct node { int bd; struct node *next; struct node *prev; }node; This will create a prototype for the doubly linked list. Here, int bd will store the binary digit i.e, either 0 or 1. *next will store the address of the next node. *prev will store the address of the previous node. The head node and last node are required for traversing the doubly linked list. Hence they are declared in the class as node *hn, node *ln, as head node and last node respectively. They need to be initialized with NULL in the class constructor. Functions: 1. To create the doubly linked list: node * create() This function will create the doubly linked list, which basically means it will assign memory to each field of the structure (next,prev) and store the binary number entered in the field bd. The binary number is accepted from the user and is stored into an int array[]. For simplicity, the size (number of bits) of the binary number has been accepted from the user, and a for loop runs from 0 to size-1. Each iteration of the for loop will create a new node and store the bits from the array one by one, while simultaneously linking the new node to the previous node. Let ‘node *nn’ be a new node to be attached to the linked list. We first allocate memory to the new node ‘nn’ by using nn= new node; The number 0 or 1 is stored into the bd field of nn while next and previous fields are initialized with NULL. If the head node is NULL, the new node is made the head node (hn=nn). Otherwise, the new node is linked to the latest/current node (declared as node *cn) by the following steps: 1. Assign the address of the last added node to the prev field of nn 2. Assign the address of nn to the next field of cn. Finally, the latest added node is made the last node. (ln=nn) The head node hn is returned (return hn) which is why the the datatype of the function create() is node *. The returned hn is required in the function to add two binary numbers ( void add() ), in which create() is called for accepting the 2 separate numbers. 2. Function to find One’s Complement (void ones()) Theory: One’s complement of a binary number is simply the negation of each bit in the number. Eg, One’s complement of 1010 will be 0101. In the function void ones(), the already formed linked list is traversed from its head node (hn) and the bd field is checked while traversing. A variable node *cn is used for traversing, starting from cn=hn. A while loop can be used to traverse with the condition cn->next!=NULL. If bd is 1 then 0 is displayed directly. If bd is 0 then 1 is displayed. This is done simply by using if-else for checking the value of bd and displaying the negation of it. After checking cn is incremented to the next node by cn=cn->next; 3. Function to find Two’s Complement (void twos()) Theory: Two’s complement is used to represent a signed number in binary form. It is calculated by performing binary addition of One’s complement and 1, i.e, Two’s= one’s+1. Eg. One’s of 1001 is 0110. 0110 + 1 = 0111 --- Two’s complement Short-Cut Method Though the procedure to find the two’s is simple but while programming, the addition of 1 to one’s complement may generate a carry bit for which separate conditions need to be specified. To avoid the tedious task, the program uses a shortcut method to compute the two’s complement. The binary number is traversed from the right (last node). Each bit (bd) is checked. Until the number ‘1’ does not appear, the 0s are copied directly into the output array. When the number 1 appears, it is copied too, but all the remaining bits will be negated, i.e, if 1 appears, 0 is stored in the output array else if 0 appears, 1 is stored in the ouput array. A flag (int flag=0) is used, which is set to 1 when the first 1 appears. The method is summarized as follows: Consider input binary number 10100 (traverse from the right) Hence output array will have 00110. The reverse of this array is the required output: 01100. Verification: Input: 10100 One’s complement: 01011 Two’s complement: 01011 + 1 = 01100 4. Function to find Sum of two Binary numbers: Two binary numbers have been accepted from the user. They are traversed bit by bit from the L.S.B (Least significant bit, i.e. right side). The sum is stored in an array (int A[20]). This is done inside a while loop which runs until either one or both of the numbers end. A carry is required as an extra variable (int cy). Both numbers will be traversed together with the same index (i) which is incremented per iteration. The following conditions are checked: 1. If both bits are 1: The sum is 0 + previous carry and the new carry is 1. A[i]= cy //sum cy=1 //carry 2. If both bits are 0: A[i]= cy //sum cy=0 //new carry 3. Both bits are different (0,1) Here, two cases arises, since the sum now depends on the carry bit’s value. (i) If cy=0 Then, A[i]=1 and cy=0 (ii) If cy=1 Then, A[i]=0 and cy=1 After this two more while loops are executed to store the remaining bits of the larger binary number. But the carry from above is added to the current bit before storing in the similar way mentioned above. Finally, the array A is printed in the reverse order to display the required sum.
0 Comments
Leave a Reply. |
AuthorProf. Ketan Sanjay Desale Archives
April 2020
Categories |