Tag: 算法

找到char变量中唯一’1’位的索引的最有效方法（在C中）: 这是一个面试问题：给你一个名为ch的char变量，当你知道它代表一个二进制forms的数字时，它的八位中只有一个将等于’1’。 IE， ch的唯一可能值是： 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80 。给定变量ch ，我需要编写最有效的代码来获得该’1’位的索引。例如：如果ch == 0x1 – >结果为0.如果ch == 0x4 – >结果为2。显而易见的方法是使用switch-case，但我需要更高效的东西。为了有效实施，您可以在这里进行任何操作吗？

伙伴分配算法 – 开始堆地址: 我目前正在尝试实现计算机程序设计Vol：1中描述的Buddy Allocator ，它利用了给定数据块及其相应伙伴的地址中的重要不变量。计算如下…… BUDDY(X): X + 2^i if x mod 2^i+1 = 0 X – 2^i if x mod 2^i-1 = 0 Where X is the address of the block; i is the current order 让伙伴系统表现得如此之好的原因在于，找到伙伴地址的这种计算可以简单地通过第i个顺序位的翻转来执行（通过用1 << i进行xor'ing）。如果给出左块地址，则返回右块。如果给出正确的块，则返回左侧块。但是，此方法假定堆以地址0开头。如果堆开始的地址位于i顺序范围内的位有一个，则执行上述计算将不会为您提供其伙伴的正确地址。因此，简单地说，有没有办法推广这个计算，以便它可以在任何起始堆地址执行？假设有一个最大订单的约束。 IE *如果最大订单是18，我们不会尝试执行任何大于或等于18的计算，因此您不需要找到它的伙伴。对此非常感谢的任何帮助或建议！

在动态编程中使用Bitmasking: 我正在学习TSP，我遇到了掩盖代表所有城市组合的比特。我不明白它背后的逻辑。请帮帮我。 #define size 10 //maximum 10 cities #define min(a,b) a>b?b:a #define sizePOW 1024 // 2^10 int n,npow,g[size][sizePOW],p[size][sizePOW],adj[size][size]; int compute(int start,int set) { int masked,mask,result=INT_MAX,temp,i; if(g[start][set]!=-1) return g[start][set]; for(i=0;i<n;i++) { mask=(npow-1)-(1<<i); masked=set&mask; if(masked!=set) { temp=adj[start][i]+compute(i,masked); if(temp<result) result=temp,p[start][set]=i; } } return g[start][set]=result; } void getpath(int start,int set) { if(p[start][set]==-1) return; int x=p[start][set]; int mask=(npow-1)-(1<<x); // […]

C程序检测直角三角形: 如果我在坐标系中给出100个点，我必须找到这些顶点中是否存在直角三角形。有没有办法可以检测这些顶点中的直角三角形，而不必选择所有3个顶点对，然后在它们上应用毕达哥拉斯定理？可以有更好的算法吗？谢谢你的帮助。 🙂

如何并行比较两个以上的数字？: 是否可以使用SSE4在一条指令中比较一对以上的数字？英特尔参考咨询有关PCMPGTQ的内容如下 PCMPGTQ – 比较大于的打包数据对目标操作数（第一个操作数）和源操作数（第二个操作数）中的压缩四字进行SIMD比较。如果第一个（目标）操作数中的数据元素大于第二个（源）操作数中的相应元素，则目标中的相应数据元素将设置为全1; 否则，设置为0。这不是我想要的，因为我希望能够决定哪个整数更大，哪个整数更小。例如，如果我需要比较 32 with 45 13 with 78 44 with 12 99 with 66 我打算将[32, 13, 44, 99]放在一个向量中，将[45, 78, 12, 66]放在另一个向量中，并在一条指令中使用SSE4进行比较，得到[0, 0, 1, 1] 0,0,1,1 [0, 0, 1, 1]结果（0 – 少，1 – 更大）但似乎这不是PCMPGTQ所做的。有关如何在此级别使用并行性来加速此比较的任何建议？

转置1维数组: 所以我有一个N维数值的一维数组，其中N是一个完美的正方形。我将这个一维数组可视化为二维数组（尽管它不是）。例如，值为int Array = { 0,1,2,3,4,5,6,7,8 } 那是 int *Array = new int [9]; for ( int i = 0 ; i < 9 ; i ++ ) Array[i] = i; // For example 打印为 0 1 2 3 4 5 6 7 8 所以，我想在一维数组中交换位置，以便我得到它的转置，… 例如… 0 3 6 1 4 7 2 5 […]

如何计算不同基数中的数字位数？: 我正在使用不同基础的数字（基数为10，基数为8，基数为16等）。我正在尝试计算每个数字中的字符数。例编号： ABCDEF 位数： 6 我知道基于对数的方法，但我遇到了一些问题。这个Python脚本输出它无法正确计算1,000,000个3,969个数字中的正确位数。我认为使用对数的方法可能相当慢链接：这个C程序必须非常慢（如果我有一个非常大的数字怎么办？）。它也不能处理不同基数的数字（例如，base-16）。这不是一个骗局，因为OP只询问基数为10 编辑：当然我可以计算一个字符串的长度，但最让我感兴趣的是，是否可以在没有常规字符串的情况下进行计算。我想知道的算法可以帮助我知道只需要知道源基和转换的基数。 Edit2： source-base是base-10 ，转换为的base可以是任何其他base。我们如何计算不同基数中的数字位数？如果我知道base-10中的数字，如何在不执行转换的情况下计算转换为base-16（base-8等）的相同数字的位数？注意：一些Python或C代码将不胜感激

这种独特的字符串函数的执行时间是否从简单的O（n ^ 2）方法中减少了？: 推断字符串是否包含所有唯一字符（并且不使用任何其他数据结构）的通用算法表示要遍历字符串，针对搜索匹配的整个字符串迭代每个字母。这种方法是O（n ^ 2）。下面的方法（用C语言编写）使用偏移量来迭代字符串部分，因为例如在短字符串中没有理由用第一个字符作为第一个字符测试最后一个字符。我的问题是：算法的运行时间是O（n！）还是O（nlogn）？ #include int strunique(const char *str) { size_t offset = 1; char *scout = (char *)str, *start; for (; *scout != ‘\0’; ++scout, ++offset) for (start = (char *)str + offset; *start != ‘\0’; ++start) if (*start == *scout) return 0; return 1; } int main(void) { printf(“%d\n”, […]

非线性颜色插值？: 如果我有一条从0到1的直线，那么我在线上的颜色为0（255,0,0），然后在0.3我有colorB（20,160,0）然后在线上我有colorC （0,0,0）。我怎么能找到0.7的颜色？谢谢

使用Sethi-Ullman算法的表达式代码生成器: 给一个AST树，我想生成一个类似汇编的语言。我正在尝试使用Sethi-Ullman算法，但我在算法实现中有一些问题。我用完寄存器后该怎么办？目前我做以下事情：发出一个push REG ，其中REG是右子树的寄存器，评估左子树，得到一个自由寄存器指定为右子树的寄存器，然后发出POP REG操作，其中REG也是右子树的寄存器。我该如何实现该function以获得免费注册？目前我正在使用这样的实现而不是基于堆栈： enum Reg { Reg_r0, Reg_r1 }; Reg regs[] = { Reg_r0, Reg_r1 }; Reg getreg() { static int c; if(c == sizeof(regs) / sizeof(int)) c = 0; return regs[c++]; } 这是一个伪代码（来自C语言）如何从我unsertood（包括label()函数）实现它 // K is the number of registers available int K = 2; void […]