所以我正在进行nand2tetris项目，我想在软件级别上实现右移逻辑，因为硬件不支持它。
我知道右移逻辑是除以2。因此，我实现它的第一次尝试是计算在初始值变为0或负值之前，我能够从初始值减去2的次数。如果数字为负数，则类似。
但是，我发现了一个不起作用的场景。我想向右移动-27139。移位后的二进制值是19199。应该是19198年。因此，我正在寻找一种新的方式来实现这一转变。
我可以使用and、or、add和subtract，这就是我可以使用的全部内容。
OSFTW
以下是我在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
数字向左或向右的逻辑移位等于将N-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将实现左移位(仅使用逐位操作)。
为了与Nand2Tetris课程的性质保持一致，我尝试在这个答案中走一条线，给出了Hack汇编编码技术和通用算法的示例，但将最终代码作为练习。
Hack ALU没有任何连接位N和位N-1的数据路径。这意味着必须使用左旋转来实现右移和旋转。(注：左=最高有效位，右=最低有效位)
左移很容易，因为它只是乘以2，这本身就是自加法。例如：
// left-shift variable someVar 1 bit
@someVar // A = address of someVar
D = M // D = Memory[A]
M = M + D // Memory[A] = Memory[A] * 2
向左旋转有点困难。您需要保留最左边的位的副本，并在进行乘法运算后将其移到最右边的位。然而，请注意，在D寄存器中有一个"someVar"原始值的副本，您可以根据其值进行测试和跳转——如果D的最左边的位是1，那么D将小于零。此外，请注意，将"someVar"乘以2后，它的最右边的位将始终为0，这使得在不更改任何其他位的情况下进行设置变得容易。
一旦你有左旋转，右旋转是直接的；如果你想左旋转N位，你可以右旋转16-N位。注意，这假定N在0-15的范围内。
右移是最复杂的操作。在这种情况下，您需要首先进行右旋转，然后生成一个将N高位设置为零的掩码。"与"(AND)的结果与遮罩一起旋转。
生成掩码的基本方法是从-1(所有位都设置)开始，并将其添加到自身N次；这使得掩码的最右边的N个比特为0。然后左旋转此16-N次，以将所有0位移动到最左边的N位。
然而，这是一个很大的循环，当用汇编语言编程时，保存循环就是一切。你可以使用一些技巧。
第一种是使用地址算术来实现case语句的等价项。对于16个可能的旋转值中的每一个，您需要将一个16位掩码值加载到D寄存器中，然后跳到案例的末尾。您必须小心，因为使用@指令只能加载15位常量，但您可以在6条指令中执行加载和无条件跳转(4条加载完整的16位常量，2条跳转)。
所以，如果你有16个从位置(CASE)开始的，你只需要把N乘以6，加到@CASE上，然后跳到那个位置。当考虑如何乘以6时，请记住HACK指令集的一个非常可爱的功能；您可以将ALU运算的结果同时存储在多个寄存器中。
然而，最有效的解决方案是预计算掩码表。在程序初始化过程中，您生成16位掩码，并将其存储在内存中的某个固定位置，然后您只需将N添加到表开头的地址即可读取掩码。
由于HACK CPU除了获取指令外，无法访问程序ROM，因此无法将表存储在ROM中，因此每个表条目必须使用多条指令将值加载到D寄存器中，然后将其保存到RAM中。最后，我编写了一个简单的python脚本，生成初始化表的代码。
如果将要移位的值视为无符号，则会变得更容易，因为逻辑右移无论如何都不会保留符号。然后你只需重复减去2，直到结果小于2，这时减法的次数就是你的商(即右移值)。
在C:中的一个示例实现
int lsr(int valueToShift)
{
int shifted = 0;
uint16_t u = valueToShift;
while (u >= 2) {
u -= 2;
shifted++;
}
return shifted;
}
您应该使用二进制或十六进制，因为使用十进制会使数字表示难以想象。
如果你有算术移位，但没有逻辑移位，最明显的解决方案是在为负的情况下清除高位
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，如果数字较大或需要移位不同数量的，则需要减去更多
一种更快的方法可能是使用加法。例如：
uin32_t LSR(uint32_t value, int count) {
uint32_t result = 0;
uint32_t temp;
while(count < 32) {
temp = value + value;
if(temp < value) { // Did the addition overflow?
result = result + result + 1;
} else {
result = result + result;
}
value = temp;
count++;
}
return result;
}
其基本思想是将一个64位无符号整数左移"32计数"次，然后返回最高的32位。
在汇编中，上面的大多数代码(分支等)有望变成类似add value, value然后是add_with_carry result, result的代码。