c语言 - 将二进制链表转换为其等效的十进制数

Question

我想将一个二进制链表(每个节点包含一个比特)转换成它的十进制等价物。例子:

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

我在网上找到了一个代码来解决这个问题，但是我在理解某一行时遇到了困难。

/* 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;
}

我无法理解re = (res << 1) + head->data在这段代码中的使用。我的意思是它如何在这条直线上乘以2 ?谁能告诉我这个行函数并显示它是工作的?

Answer 1

res << 1将res的位模式向左移位(更有效的数字)。

由于整数使用二进制记数法存储在内存中，向左移动将使数字加倍-与res * 2相同。

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

res << 1在没有溢出和负数的情况下与res * 2工作相同。

对于OP的目的，下面是相同的。

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

在任何一种情况下，健壮的代码都会注意溢出。

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

Answer 2

从视觉上考虑——在每次循环迭代中，您都将所有的位推到左边，打开一个新的槽。然后，加法运算符填充右边的槽。