B Basak - 1 year ago 47

C Question

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`

Answer Source

`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;
...
```