二元加法

Question

我想了解位运算符在 C 中的工作原理，但我对 << 运算符有误解。

我有以下代码：

#include <stdio.h>

int Add(int x, int y);
int Add(int x, int y)
{
    while ( y != 0 )        /// Iterate till there is no carry
    {
        int carry = x & y;  /// carry now contains common set bits of x and y
        x = x ^ y;          /// Sum of bits of x and y where at least one of the bits is not set
        y = carry << 1;     /// Carry is shifted by one so that adding it to x gives the required sum
    }
    return x;
}

int main( void )
{
    printf( "%d", Add( 13, 17 ) );
    return 0;
}

如果我理解正确的话是这样的：

First Iteration:
|=======================================|
|                                       |
|   while ( y       !=      0     )     |
|   while ( 17      !=      0     )     |
|   while ( 10001   !=      00000 )     |
|                                       |
|   c       =   x       &   y;          |
|   1       =   13      &   17          |
|   00001   =   01101   &   10001       |
|                                       |
|   x       =   x       ^   y           |
|   28      =   13      ^   17          |
|   11100   =   01101   ^   10001       |
|                                       |
|   y       =   c      <<   1           |
|   17      =   1      <<   1           |
|   10001   =   00001  <<   00001       |
|   00010   =   00001  <<   00001       |
|                                       |
|=======================================|

Second Iteration:
|=======================================|
|                                       |
|   while ( y       !=      0     )     |
|   while ( 2       !=      0     )     |
|   while ( 00010   !=      00000 )     |
|                                       |
|   c       =   x       &   y;          |
|   0       =   28      &   2           |
|   00000   =   11100   &   00010       |
|                                       |
|   x       =   x       ^   y           |
|   30      =   28      ^   2           |
|   11110   =   11100   ^   00010       |
|                                       |
|   y       =   c      <<   1           |
|   2       =   0      <<   1           |
|   00010   =   00000  <<   00001       |
|   00000   =   00000  <<   00001       |
|                                       |
|=======================================|

然后Y变成0和Xreturns30.

现在在下面的代码中我遇到了一个问题：

#include <stdio.h>

int main( void )
{
    int x = 13;
    int y = x << 1; /// 11010 = 01101 << 00001
    x = 0 << 1;     /// 00000 = 00000 << 00001

    printf("y = %d\n", y ); /// 26  | 11010
    printf("x = %d\n", x ); /// 26  | 11010
    return 0;
}

如果我理解正确，我们将所有位向左移动一位：

int y = x << 1; /// 11010 = 01101 << 00001

但这里到底发生了什么：

x = 0 << 1;     /// 00000 = 00000 << 00001

是否 x 被清除并填充 0 << 1 的结果？

Answer 1

Does x get cleared and filled with the rezult of 0 << 1 ?

x 只是被赋予了表达式 0 << 1 的值。左移或右移任意量的零仍然是 0。

So this means that the representation of the First and Second Iteration is correct?

这是正确的，除了变量的旧值替换（在 lhs 上）有点混乱，如以下情况。

17      =   1      <<   1 
10001   =   00001  <<   00001

和

2       =   0      <<   1
00010   =   00000  <<   00001

而是将其描述为：

y      =   1      <<   1 
y      =   00001  <<   00001

和

y       =   0      <<   1
y       =   00000  <<   00001

Answer 2

n << k 实际上是 n * (2^k) 只要您有足够的可用位来保留所有结果位。所以 0 << k 是 0 * (2^k) = 0 无论 k 的（正整数）值是什么。

请注意，对于通常的 32 位整数，p = 17 位或更多位的数字，如 65537 (0x0001_0001)，一旦 k 大于或等于 (32+1)-p = (32+1)-17 = 16，将停止像乘法一样的行为，例如 65537 << 16 是 0x1_0001_0000，它使用 33 位并被截断为 0x0001_0000 = 65536。
使用 65536 << 15 您可能还会开始得到奇怪的结果，因为 0x1000_0000 正在更改最左边的位，如果您不使用无符号值，则为符号位...

二元加法

Binary addition

c

bit-shift