K&R Chapter 2. Types, Operators, and Expressions

发表于 | 分类于

《2.9 Bitwise operators》

逻辑位移和算术位移

<< 是左移，>> 是右移，右操作数（right operand）必须为正数。
左移都是寄存器二进制位整体向左移动，并在右边补0。
右移的话，如果左操作数是无符号数，如unsigned int、unsigned char等，则整体向右移，并在左边补0。如果左操作数是有符号数，如int、char、short等，则整体向右移后，某些机器会在左边补上符号数（算术位移），而某些机器会在左边补上0（逻辑位移）。

在汇编指令中，SHL和SHR表示逻辑左移和逻辑右移，SAR和SAL表示算术左移和算术右移。一般的说法是：如果左操作数是有符号数，编译产生的汇编指令是算术位移指令；如果是无符号数，编译产生的汇编指令则是逻辑位移指令。而根据K&R的说法，应该是：如果左操作数是有符号数，某些机器会生成算术位移指令，而某些机器会生产逻辑位移指令；如果是无符号数，编译产生的汇编指令则是逻辑位移指令。

示例：编写函数getbits(x,p,n)，返回x从位置p开始的n bit（向右对齐）。假设最右端是位置0，n和p都是正数。getbits(x,4,3)返回三个bit，分别是位置4、3、2。

1
2
3
4
5
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
    return (x >> (p+1-n)) & ~(~0 << n);
}

练习2-6：编写函数setbits(x,p,n,y)，将x中从第p位开始的n个(二进制)位设置为y中最右边n位的值，x的其余各位保持不变。
思路是：将x从第p位开始的n个位清零，x &~(~(~0<< n) << (p + 1 -n))；将y的最右边n位移到p位置，其他位清零，(y & ~(~0 <<n )) << (p + 1 - n)；两者相或。

1
2
3
4
5
/* setbits : set n bits of x at position p with bits of y */
unsigned setbits ( unsigned x, int  p, int n, unsigned y)
{
    return x &~(~(~0<< n) << (p + 1 -n)) | (y & ~(~0 <<n )) << (p + 1 - n)
}

练习2-7：编写函数invert(x,p,n)，将x从位置p开始的n bit取反，其他位不变。

1
2
3
4
unsigned invert(unsigned x, int p, int n)
{
    return x ^ ((~(~0<<n))<< p+1-n);
}

练习2-8：编写函数rightrot(x,n)，将x向右循环n个位置后返回。

1
2
3
4
5
6
7
8
9
10
11
unsigned rightrot(unsigned x, unsigned n)
{
    while (n > 0) {
        if ((x & 1) == 1)
            x = (x >> 1) | ~(~0U >> 1);
        else
            x = (x >> 1);
        n--;
    }
    return x;
}

显示 Gitment 评论