B Basak B Basak - 2 months ago 8
C Question

Converting Binary Linked List Into It's Equivalent Decimal Number

I want to convert a binary linked list, with each node containing a single bit, into it's decimal equivalent. Example:

Input : 0->0->0->1->1->0->0->1->0
Output : 50


I found a code online to solve this problem but I am having difficulty in understanding a particular line.

/* Returns decimal value of binary linked list */
int decimalValue(struct Node *head)
{
// Initialized result
int res = 0;

// Traverse linked list
while (head != NULL)
{
// Multiply result by 2 and add
// head's data
res = (res << 1) + head->data;

// Move next
head = head->next;
}
return res;
}


I am unable to understand the use of
re = (res << 1) + head->data
in this code. I mean how is it multiplying 2 in this line? Can anyone please tell me this lines function and show it's working ?

Answer

res << 1 shifts the bit pattern of res to the "left" (more significant digits).

As integers are store in memory using binary notation, shifting left doubles the number - same as res * 2.

    MSbit         LSbit
    v                 v
    0000 1111 0011 0011  or  3891
    shifted left
    0001 1110 0110 0110  or  7782

res << 1 works just like res * 2 when there is no overflow nor negative numbers involved.

For OP's purpose, the below are the same.

res = (res << 1) + head->data;
res = (res * 2) + head->data;

In either case, robust code would watch out for overflow.

if (res > INT_MAX/2) { puts("Overflow"); exit(-1) }
res = (res * 2) + head->data;
...