实现逻辑移位

Question

因此，我正在研究nand2tetris项目，并且我希望在软件级别上实现正确的转换逻辑，因为硬件不支持它。

我知道右移逻辑是除以二。因此，我第一次尝试实现它时，会计算出在值变为0或负值之前，我能够从初始值减去2的次数。如果数字为负数，则类似。

但是，我发现了一种不起作用的情况。我想右转-27139。移动后的二进制值是19199。应该是19198。因此，我正在寻找一种新的方式来实现这一转变。

我可以and值、or值、add和subtract，这是我所拥有的一切。

超临界水

下面是我在Hack实现的汇编语言中的代码：

//============================================================
// SLR: Shift Logical Right (by 1)
//============================================================

(SLR)

@SLR.1              // Load value
D=M
@SLR.2
M=0                 // Clear variables
@SLR_POSITIVE_LOOP      // If value is positive, go to the positive loop
D;JGT


(SLR_NEGATIVE_LOOP)
@SLR.1              // Add 2 to value, since it's negative
M=M+1
M=M+1
@SLR.1              // If initial value was negative and current value is positive or zero, jump out of loop
D=M
@SLR_NEG
D; JGE
@SLR.2              // If value is negative, add 1 to SLR.2 (we're dividing)
M=M+1
@SLR.1              // If value is less than 0, restart the loop
D=M
@SLR_NEGATIVE_LOOP
D; JLT

(SLR_NEG)
@SLR.2
D=M
D=!D                // Invert the result
D=D+1               // Add 1 to finish converting
@32767              // And it with 0111111111111111 to clear the sign bit
D=D&A
@SLR.2
M=D                 // Set value
@SLR_END                        // Jump to end of loop
0;JMP

(SLR_POSITIVE_LOOP)
@SLR.1              // Subtract 2 from value
M=M-1
M=M-1
@SLR.1              // If initial value was positive and current value is negative or zero, jump out of loop
D=M
@SLR_END
D; JLE
@SLR.2              // If value is still positive, add 1 to SLR.2 (we're dividing)
M=M+1
@SLR.1              // If value is greater than 0, restart the loop
D=M
@SLR_POSITIVE_LOOP
D; JGT


(SLR_END)               // Loop is over. Set value of SLR.1 to that of SLR.2, for return purposes

@SLR.2                                  // Place result in correct place
D=M
@SLR.1
M=D

@SLR.0             // Return to calling function
A = M
0; JMP

Answer 1

数字左或右的逻辑移位等于将N位从N位的一个字复制到另一个字。因此：

unsigned int a = 0x1321;
unsigned int b = 0;
unsigned int mask1 = 1;
unsigned int mask2 = 1 << n;  // use repeated addition for left shift...
int i;
for (i = 0; i < N-n; i++) {
    if (a & mask2)
        b|= mask1;
    mask1 += mask1;
    mask2 += mask2;
}

交换mask1和mask2将实现左移(仅按位操作)。

Answer 2

如果将要转换的值视为无符号，则会变得更容易，因为逻辑右移位无论如何都不会保留该符号。然后你重复地减去2，直到结果小于2，此时减数是你的商(也就是右移值)。

C中的一个示例实现：

int lsr(int valueToShift)
{
    int shifted = 0;
    uint16_t u = valueToShift;

    while (u >= 2) {
        u -= 2;
        shifted++;
    }

    return shifted;
}

Answer 3

您应该使用二进制或十六进制，因为使用十进制使得很难想象数字表示。

如果你有算术移位，但没有逻辑移位，最明显的解决方案是清除顶部的位，如果它是负的

int LogicalRightShift(int x, int shift)
{
    return (x >> shift) & ((1U << (CHAR_BIT*sizeof(x) - shift)) - 1);
    // or
    return (x >> shift) & (~((~0) << (CHAR_BIT*sizeof(x) - shift)));
}

如果你没有算术右移，你也可以一点一点地复制它。

int LogicalRightShift(int x, int shift)
{
    // assuming int size is 32
    int bits[] = {  0x1,        0x2,        0x4,        0x8,        0x10,       0x20,       0x40,       0x80,
                    0x100,      0x200,      0x400,      0x800,      0x1000,     0x2000,     0x4000,     0x8000,
                    0x10000,    0x20000,    0x40000,    0x80000,    0x100000,   0x200000,   0x400000,   0x800000,
                    0x1000000,  0x2000000,  0x4000000,  0x8000000,  0x10000000, 0x20000000, 0x40000000, 0x80000000
    }
    int res = 0;
    for (int i = 31; i >= shift; i++)
    {
        if (x & bits[i])
            res |= bits[i - shift];
    }
    return res;
}

另一种方法是重复除以2，或者可以将2的幂存储在查找表中，然后除以该幂。这样，如果没有硬件除法器，它可能要比上面的位复制方法慢得多，但仍然比不得不像您的方法减去数千倍的速度更快。若要移动-27139 (38397)右1位，则需要从数字9599减去2，如果数字较大或需要移动不同的位数，则还要减去2。