将算术右移改为逻辑右移

Question

以下代码是教科书(布莱恩特和奥哈拉隆:计算机系统--程序员的视角第二版)位级数据操作问题的解决方案(尝试用于挑战，而不是类)。函数srl不一定以实际的方式编写，而是在问题所需的约束范围内编写的。任务是将算术右移的结果转换为逻辑右移的结果。

问题

是否有一种更清晰、更直截了当的方式来在问题所需的约束范围内(也许是使用较少的~操作)来编写这个问题呢？

当k = 0时，需要避免左移位的未定义行为。在本例中，int_bits - k = int_bits会导致转换无法预测地工作。是否有更好的方法来处理移位操作的未定义行为，当移位大于交织器中的位数时？

这似乎是正确的，但我没有一个答案，因此，任何反馈的解决方案将不胜感激。

需求

• 在给定表达式/*Perform移位算术*/无符号xsra = (int) x >> k之外，不能使用额外的右移位或类型转换；
• 只能使用加法或减法，不使用乘法、除法或模。
• 没有比较运算符也没有条件
• 只能使用按位操作(除了进一步的右移)和逻辑运算符。

码

unsigned srl(unsigned x, int k) {
    /*Perform shift arithmetically*/
    unsigned xsra = (int) x >> k;

    unsigned int_bits = sizeof(int) << 3;//calculates the number of bits in int (assumes 8-bit byte)

    unsigned zero_or_all_bits = ~0 + !k;//for k = 0, corrects for the undefined behavior in
                                        //the left shift produced from int_bits - k = int_bits
                                        //if k != 0, !k == 0, and zero_or_all_bits == ~0
                                        //if k == 0, zero_or_all_bits == 0

    unsigned high_bit_mask = ~(zero_or_all_bits << (zero_or_all_bits & (int_bits - k)));
    /******************************************/
    //creates a mask of either all bits set in an unsigned int (UINT_MAX)
    //or a mask with k high bits cleared.
    //if k == 0, then high_bit_mask = ~(0 << 0) = ~0.
    //if k != 0, then high_bit_mask = ~(~0 << (~0 & (int_bits - k)))
    //ex. k == 3, high_bit_mask == 0x1FFFFFFF
    //ex. k == 0, high_bit_mask == 0xFFFFFFFF
    //ex. k == 31, high_bit_mask == 0xFFFFFFFE
    /******************************************/

    return xsra & high_bit_mask;
}

测试代码

printf("Test srl:\n");
printf("srl(-1, 1): 0x%.8x\n", srl(-1, 1));
printf("srl(-1, 4): 0x%.8x\n", srl(-1, 4));
printf("srl(-1, 5): 0x%.8x\n", srl(-1, 5));
printf("srl(-1, 31): 0x%.8x\n", srl(-1, 31));
printf("srl(-1, 0): 0x%.8x\n", srl(-1, 0));

printf("srl(0x7FFFFFFF, 1): 0x%.8x\n", srl(0x7FFFFFFF, 1));
printf("srl(0x7FFFFFFF, 4): 0x%.8x\n", srl(0x7FFFFFFF, 4));
printf("srl(0x7FFFFFFF, 5): 0x%.8x\n", srl(0x7FFFFFFF, 5));
printf("srl(0x7FFFFFFF, 31): 0x%.8x\n", srl(0x7FFFFFFF, 31));
printf("srl(0x7FFFFFFF, 0): 0x%.8x\n", srl(0x7FFFFFFF, 0));

printf("srl(0x80000000, 1): 0x%.8x\n", srl(0x80000000, 1));
printf("srl(0x80000000, 4): 0x%.8x\n", srl(0x80000000, 4));
printf("srl(0x80000000, 5): 0x%.8x\n", srl(0x80000000, 5));
printf("srl(0x80000000, 31): 0x%.8x\n", srl(0x80000000, 31));
printf("srl(0x80000000, 0): 0x%.8x\n", srl(0x80000000, 0));

printf("srl(0, 1): 0x%.8x\n", srl(0, 1));
printf("srl(0, 4): 0x%.8x\n", srl(0, 4));
printf("srl(0, 5): 0x%.8x\n", srl(0, 5));
printf("srl(0, 31): 0x%.8x\n", srl(0, 31));
printf("srl(0, 0): 0x%.8x\n", srl(0, 0));

printf("srl(1, 1): 0x%.8x\n", srl(1, 1));
printf("srl(1, 4): 0x%.8x\n", srl(1, 4));
printf("srl(1, 5): 0x%.8x\n", srl(1, 5));
printf("srl(1, 31): 0x%.8x\n", srl(1, 31));
printf("srl(1, 0): 0x%.8x\n", srl(1, 0));

输出

Test srl:     
srl(-1, 1): 0x7fffffff     
srl(-1, 4): 0x0fffffff     
srl(-1, 5): 0x07ffffff     
srl(-1, 31): 0x00000001     
srl(-1, 0): 0xffffffff     
srl(0x7FFFFFFF, 1): 0x3fffffff     
srl(0x7FFFFFFF, 4): 0x07ffffff     
srl(0x7FFFFFFF, 5): 0x03ffffff     
srl(0x7FFFFFFF, 31): 0x00000000     
srl(0x7FFFFFFF, 0): 0x7fffffff     
srl(0x80000000, 1): 0x40000000     
srl(0x80000000, 4): 0x08000000     
srl(0x80000000, 5): 0x04000000     
srl(0x80000000, 31): 0x00000001     
srl(0x80000000, 0): 0x80000000     
srl(0, 1): 0x00000000     
srl(0, 4): 0x00000000     
srl(0, 5): 0x00000000     
srl(0, 31): 0x00000000     
srl(0, 0): 0x00000000     
srl(1, 1): 0x00000000     
srl(1, 4): 0x00000000     
srl(1, 5): 0x00000000     
srl(1, 31): 0x00000000     
srl(1, 0): 0x00000001     

Answer 1

• 对于存在的所有实现定义的行为：
  • 在一般情况下，如果将负数右移导致算术移位或逻辑移位，则为实现定义。这取决于编译器的选择。
  • 在特定情况下，您可以从unsignedx类型转到签名类型(int)x。您有隐式的、实现定义的从符号类型到无符号类型和返回的转换。该程序允许在从大型unsigned int到int时发出信号。因此，这不是一个好主意，但没有办法绕过它，因为你的程序被编写。
  • 也就是说，当我们执行函数的第一行时，我们不知道变量或整个程序的状态。在一个特定的系统上，这是另一个故事，但你的问题是关于通用C。

• sizeof(int) << 3。用移位代替8是一种糟糕的做法，被称为“早熟优化”.永远不要这样做，让编译器来处理它。正确的代码应该是8 * sizeof(int)或CHAR_BIT * sizeof(int)。
• 关于~0 + !k。如果k是0，则结果是-1 + 1 = 0，假设是2的补数。否则，如果k不是0，则结果是-1，然后您将其隐式转换为无符号类型。写这样模糊的代码的原因是什么，你是想让代码更容易分支还是别的什么？在基准测试过程中发现瓶颈之前，不要这样做。相反，写: if(k==0) { zero_or_all_bits = 0；} zero_or_all_bits = ~0u；}

或者你愿意的话，unsigned int zero_or_all_bits = (k==0) ? 0u : ~0u。

至于如何将算术转换的结果转换为逻辑，而不存在任何可疑的转换或UB打嗝，只需：

int val = x >> y;                // some manner of arithmetic shift
...
const size_t int_bits = sizeof(int) * 8;
unsigned int mask = (1u << y)-1; // create a mask corresponding to the number of shifts
mask = mask << (int_bits-y);     // shift the mask in place from MSB and down
mask = ~mask;                    // then invert the whole integer, making mask bits zero, rest ones
val = val & mask;                // set the bits to zero

也就是说，只需清除由算术移位设置的位。这段代码是在几个步骤中有意编写的，以使其更容易理解。

例如，给定x = -8和y = 2：

• x = -8是0xFFFFFFF8十六进制(2's补码)。
• -8 >> 2算术移位给出了0xFFFFFFFE。两个零被移出，两个一个移进来。
• 相应的逻辑转移将是0x3FFFFFFE。两个零被移出，两个零被移入。
• (1u << 2)提供0x4。(1u << 2)-1给出了0x3，一个2位宽的掩码。
• 将掩码0x3移到适当位置，32-2=30位向左移动。临时值0xC0000000。
• 相反，我们得到了0x3FFFFFFF，这是所需的掩码。
• 数据和掩码给出：0xFFFFFFFE和0x3FFFFFFF = 0x3FFFFFFE。

Answer 2

LGTM.

一个建议是将unsigned zero_or_all_bits = ~0 + !k;分成两行，如下所示

    unsigned zero_or_all_bits = ~0;

    // for k = 0, corrects for the undefined behavior in
    // the left shift produced from int_bits - k = int_bits
    // if k != 0, !k == 0, and zero_or_all_bits == ~0
    // if k == 0, zero_or_all_bits == 0

    zero_or_all_bits += !k;

另外两个注释(// calculates和// creates mask)没有添加任何值。我建议把它们移除。