通过内嵌汇编把堆空间作为栈空间使用

相信搞过OI的都遇到过递归栈溢出的情况，一般的解决方法无非两种：改变算法或者强行手动模拟栈。

今天突发奇想，发现了一种另类的解决办法：内嵌汇编语句，改变esp指针，使用一个预先申请好的全局数组的空间作为栈空间使用。

一个例子如下：

#include <cstdio> int func(int n) { if (n <= 2) return 3; int a = 0; a = func(n - 1); a <<= 1; a >>= 1; return a; } const int N_MAX = 10000000; int main() { static int stack[N_MAX * 5], bak; asm __volatile__ ( "movl %%esp, %0/n/t" "movl %1, %%esp/n/t": "=g"(bak): "g"(stack + N_MAX * 5 - 1): ); static int x; x = func(N_MAX); asm __volatile__ ( "movl %0, %%esp/n/t" : : "g"(bak) ); printf("%d/n", x); }

例如，在POI 2006 met(subway)中，如果直接dfs递归建树，有两个点会栈溢出；而通过如下的call_dfs_mktree来调用dfs_mktree函数，则在linux与windows下均测试通过：

void Solve::dfs_mktree(int v0) { Node &n0 = tree[v0]; n0.ml_dep = 0; n0.ml_vtx = v0; for (int i = graph[v0]; i; i = arc[i].next) if (arc[i].usable) { arc[i ^ 1].usable = 0; int t = arc[i].tvtx; tree[t].par = v0; tree[t].sibling = n0.child; n0.child = t; dfs_mktree(t); if (tree[t].ml_dep > n0.ml_dep) { n0.ml_dep = tree[t].ml_dep; n0.ml_vtx = tree[t].ml_vtx; } } n0.ml_dep ++; } void Solve::call_dfs_mktree(int v0) { const int STACK_SIZE = NVTX_MAX * 5; static int stack[STACK_SIZE], bak; __asm__ __volatile__ ( "movl %%esp, %0/n/t" "movl %1, %%esp/n/t" : "=g"(bak): "g"(stack + STACK_SIZE - 1): ); dfs_mktree(v0); __asm__ __volatile__ ( "movl %0, %%esp/n/t": : "g"(bak): ); }

当然，这个方法也有局限性，就是要能申请到足够大的堆空间。。

最后

以上就是苹果嚓茶为你收集整理的通过内嵌汇编把堆空间作为栈空间使用的全部内容，希望文章能够帮你解决通过内嵌汇编把堆空间作为栈空间使用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。