当我发送变量时，我想在C预处理器包含语句中执行以下算术函数x。
#define calc_addr_data_reg (x) ( base_offset + ((x/7) * 0x20) + data_reg_offset)
我将如何使用位移来实现除法和乘法运算？在除法运算中，我只需要商。
问问题
434 次
1 回答
4
为了回答问题，
“这个表达式在 C 预处理器中正确吗？”
我看不出有什么问题。
我将如何使用位移来实现除法和乘法运算？在除法运算中，我只需要商。
在几乎所有情况下，编译器都会比您更好地优化您的代码。如果你不得不问 StackOverflow 如何做到这一点，那么你的知识还不足以胜过 GCC。我知道我当然不知道。但是因为你问这里是 gcc 如何优化它。
@EdHeal，
这需要更多的空间来正确响应。您在给出的示例（getter 和 setter）中是绝对正确的，但是在这个特定的示例中inline，假设它被调用了几次，该函数会稍微增加二进制文件的一侧。
GCC 将该函数编译为：
mov ecx, edx
mov edx, -1840700269
mov eax, edi
imul edx
lea eax, [rdx+rdi]
sar eax, 2
sar edi, 31
sub eax, edi
sal eax, 5
add esi, eax
lea eax, [rsi+rcx]
ret
这比用于调用函数并从函数获取返回值的程序集要多字节，这是 3 个push语句，一个调用，一个返回和一个 pop 语句（大概）。
使用 -Os 它编译成：
mov eax, edi
mov ecx, 7
mov edi, edx
cdq
idiv ecx
sal eax, 5
add eax, esi
add eax, edi
ret
这比调用返回推送和弹出的字节少。
因此，在这种情况下，内联时代码是更小还是更大，他使用什么编译器标志真的很重要。
再次操作：
解释那里的代码是什么意思：
这篇文章的下一部分直接来自： http: //porn.quiteajolt.com/2008/04/30/the-voodoo-of-gcc-part-i/
对这种怪物的正确反应是“等等”。我认为可以使用更多解释的一些具体说明：
movl $-1840700269, -4(%ebp)
-1840700269 = -015555555555 八进制（由前导零表示）。我将使用八进制表示，因为它看起来更酷。
imull %ecx
这将 %ecx 和 %eax 相乘。这两个寄存器都包含一个 32 位的数字，因此这种乘法可能会产生一个 64 位的数字。这不能放入一个 32 位寄存器，因此结果被分成两个：乘积的高 32 位放入 %edx，低 32 位放入 %eax。
leal (%edx,%ecx), %eax
这将添加 %edx 和 %ecx 并将结果放入 %eax。lea 表面上的目的是用于地址计算，将其写成两条指令会更清楚：一个 add 和一个 mov，但这需要两个时钟周期来执行，而这只需要一个。
另请注意，该指令使用前一条指令（存储在 %edx 中）乘法的高 32 位，然后覆盖 %eax 中的低 32 位，因此只使用乘法的高位。
sarl $2, %edx # %edx = %edx >> 2
从技术上讲，sar（算术右移）是否等同于 >> 运算符是实现定义的。gcc 保证运算符是有符号数的算术移位（“Signed `>>' 通过符号扩展作用于负数”），并且由于我已经使用过一次 gcc，让我们假设我在其余部分使用它这篇文章的（因为我是）。
sarl $31, %eax
%eax 是一个 32 位寄存器，因此它将对 [-231, 231 - 1] 范围内的整数进行操作。这产生了一些有趣的东西：这个计算只有两个可能的结果。如果数字大于或等于 0，则无论如何移位都会将数字减少到 0。如果数字小于 0，则结果将为 -1。
这是将此程序集直接重写为 C 的方法，为了安全起见，有一些整数宽度的偏执狂，因为其中一些步骤依赖于正好为 32 位宽的整数：
int32_t divideBySeven(int32_t num) {
int32_t eax, ecx, edx, temp; // push %ebp / movl %esp, %ebp / subl $4, %esp
ecx = num; // movl 8(%ebp), %ecx
temp = -015555555555; // movl $-1840700269, -4(%ebp)
eax = temp; // movl -4(%ebp), %eax
// imull %ecx - int64_t casts to avoid overflow
edx = ((int64_t)ecx * eax) >> 32; // high 32 bits
eax = (int64_t)ecx * eax; // low 32 bits
eax = edx + ecx; // leal (%edx,%ecx), %eax
edx = eax; // movl %eax, %edx
edx = edx >> 2; // sarl $2, %edx
eax = ecx; // movl %ecx, %eax
eax = eax >> 31; // sarl $31, %eax
ecx = edx; // movl %edx, %ecx
ecx = ecx - eax; // subl %eax, %ecx
eax = ecx; // movl %ecx, %eax
return eax; // leave / ret
}
现在这里显然有一大堆低效的东西：不必要的局部变量，一堆不必要的变量交换，以及 eax = (int64_t)ecx * eax1; 根本不需要（我只是为了完成而将其包括在内）。所以让我们清理一下。下一个清单只是消除了大部分杂物，每个块上方都有相应的组件：
int32_t divideBySeven(int32_t num) {
// pushl %ebp
// movl %esp, %ebp
// subl $4, %esp
// movl 8(%ebp), %ecx
// movl $-1840700269, -4(%ebp)
// movl -4(%ebp), %eax
int32_t eax, edx;
eax = -015555555555;
// imull %ecx
edx = ((int64_t)num * eax) >> 32;
// leal (%edx,%ecx), %eax
// movl %eax, %edx
// sarl $2, %edx
edx = edx + num;
edx = edx >> 2;
// movl %ecx, %eax
// sarl $31, %eax
eax = num >> 31;
// movl %edx, %ecx
// subl %eax, %ecx
// movl %ecx, %eax
// leave
// ret
eax = edx - eax;
return eax;
}
和最终版本：
int32_t divideBySeven(int32_t num) {
int32_t temp = ((int64_t)num * -015555555555) >> 32;
temp = (temp + num) >> 2;
return (temp - (num >> 31));
}
我还没有回答一个明显的问题，“他们为什么要这样做？” 答案当然是速度。第一个列表中使用的整数除法指令 idiv 需要 43 个时钟周期才能执行。但是 gcc 生成的无除法方法有更多的指令，那么总体上它真的更快吗？这就是我们有基准的原因。
int main(int argc, char *argv[]) {
int i = INT_MIN;
do {
divideBySeven(i);
i++;
} while (i != INT_MIN);
return 0;
}
遍历每一个可能的整数？当然！我为这两种实现运行了五次测试，并随着时间的推移对其进行计时。gcc 的用户 CPU 时间分别为 45.9、45.89、45.9、45.99 和 46.11 秒，而我使用 idiv 指令进行汇编的时间分别为 62.34、62.32、62.44、62.3 和 62.29 秒，这意味着天真的实现运行了大约 36%平均较慢。哟。
编译器优化是一件美妙的事情。
好的，我回来了，现在为什么会这样？
int32_t divideBySeven(int32_t num) {
int32_t temp = ((int64_t)num * -015555555555) >> 32;
temp = (temp + num) >> 2;
return (temp - (num >> 31));
}
我们来看看第一部分：
int32_t temp = ((int64_t)num * -015555555555) >> 32;
为什么是这个数字？
好吧，让我们把 2^64 除以 7，看看会出现什么。
2^64 / 7 = 2635249153387078802.28571428571428571429
看起来很乱，如果我们把它转换成八进制呢？
0222222222222222222222.22222222222222222222222
这是一个非常重复的模式，这肯定不是巧合。我的意思是我们记得 7 是0b111，而且我们知道当我们除以 99 时，我们往往会得到以 10 为底的重复模式。因此，当我们除以 7 时，我们会得到以 8 为底的重复模式是有道理的。
那么我们的号码是从哪里来的呢？
(int32_t)-1840700269是相同的(uint_32t)2454267027
* 7 = 17179869189
最后 17179869184 是2^34
这意味着 17179869189 是 7 2^34 的最接近的倍数。或者换句话说，2454267027 是适合的最大数字，uint32_t当乘以 7 时，它非常接近 2 的幂
这个八进制数是多少？
0222222222223
为什么这很重要？好吧，我们想除以 7。这个数字是 2^34/7... 大约。因此，如果我们乘以它，然后左移 34 次，我们应该得到一个非常接近确切数字的数字。
最后两行看起来像是为了修补近似误差而设计的。
也许在这个领域有更多知识和/或专业知识的人可以加入这一点。
>>> magic = 2454267027
>>> def div7(a):
... if (int(magic * a >> 34) != a // 7):
... return 0
... return 1
...
>>> for a in xrange(2**31, 2**32):
... if (not div7(a)):
... print "%s fails" % a
...
故障从 3435973841 开始，有趣的是 0b11001100110011001100110011010001
于 2013-03-07T01:25:45.757 回答