MSVC 8086内联汇编生成全排列仅N≤3生效问题排查
全排列汇编实现故障修复方案
故障根因
- 前序排列读取偏移错误:每次生成新排列时固定从第一个排列的地址读取数据,没有基于上一个刚生成的排列计算偏移,导致第一轮排列生成完成后读取的数据完全错位。
- EDI变量更新逻辑错误:原代码
MOV EDI, Perm[4*EDI]误用当前要移动的自然数作为数组下标取值,逻辑完全错误,实际需求是取下一个待移动的自然数,超过N时重置为1。 - 无用代码冗余:原代码中
ResettaKN标签无跳转入口,逻辑永远不会执行,导致EDI值可能越界。
修复方案
直接替换原代码中的__asm块为以下实现即可,无需修改C代码其他部分:
__asm { XOR EAX, EAX ; Reset EAX (permutations counter) MOV ECX, N ; Put N into ECX CMP ECX, 1 ; Compare ECX and 1 JBE Piccolo ; If ECX <= 1 go to Piccolo (particular cases 1 and 0) DEC ECX ; Decrement ECX (so ECX = N - 1) MOV EAX, N ; Put N into EAX MaxPerm: MUL ECX ; Do EDX:EAX = EAX * ECX LOOP MaxPerm ; Loop to find permutations number MOV Num, EAX ; Move EAX (permutations number) into Num MOV EAX, 1 ; Set EAX (permutations number) to 1 MOV EBX, 0 ; Reset EBX (EBX = 0) MOV ECX, 1 ; Reset ECX CicloIniziale: DEC ECX ; Decrement ECX (to compare it with N) CMP ECX, N ; Compare ECX and N JE Permutazione ; If ECX == N the first permutation has been written, skip to the generation of the next ones INC ECX ; Else increment ECX MOV Perm[4*EBX], ECX ; Insert ECX into the Perm array INC ECX ; Increment ECX INC EBX ; Increment EBX JMP CicloIniziale ; Continue the loop Permutazione: XOR EAX, EAX ; Local index ; 修复:上一个排列的起始地址 = 当前写入偏移 - N个元素的长度 MOV EBX, ECX SUB EBX, N MOV EDI, 1 ; Value of k MOV ESI, 1 ; New position of k CicloPermutazione: CMP EAX, N ; Compare ECX and EAX JE ResetPerm ; If the end of the permutation has been reached, go to ResetPerm MOV EDX, Perm[4*EBX] ; Otherwise save the element of the previous permutation in position EBX in EDX CMP EDX, EDI ; Compare EDX and EDI JE ValoreUguale ; If they are equal, then go to ValoreUguale CMP EAX, ESI ; Otherwise compare EBX and ESI JE InserisciElSpostato ; If it's time to move the item, go to InserisciElSpostato MOV Perm[4*ECX], EDX ; Returns the value of the previous permutation to the new permutation ContinuaCiclo: INC EBX ; Increment the previous permutation index INC EAX ; Increment the local index INC ECX ; Increment the new permutation index JMP CicloPermutazione ; Continue the loop InserisciElSpostato: MOV Perm[4*ECX], EDI ; Put EDI in the new permutation MOV EDX, N ; EDX = N DEC EDX ; EDX -= 1 CMP ESI, EDX ; Compare ESI and EDX JE ResettaK ; If ESI == EDX go to ResettaK JMP ContinuaCiclo ; Continue the loop ValoreUguale: CMP EAX, 0 ; Confronta EAX e 0 JZ PrimaPos ; If EAX == 0 (first position) go to PrimaPos MOV EDX, Perm[4*EBX+4] ; Else save the element into position EBX + 1 MOV Perm[4*ECX], EDX ; Insert EDX in the new permutation JMP ContinuaCiclo ; Continue the loop PrimaPos: MOV EDX, Perm[4*EBX+4] ; Save into EDX the element in position EBX + 1 MOV Perm[4*ECX], EDX ; Insert EDX into the new permutation JMP ContinuaCiclo ; Continue the loop ResettaK: XOR ESI, ESI ; Reset ESI ; 修复:EDI是待移动的数值,直接加1,超过N则重置为1 INC EDI CMP EDI, N JBE ContinuaCiclo MOV EDI, 1 JMP ContinuaCiclo ; Continue the loop ResetPerm: MOV EAX, Num ; EAX = Num MUL DWORD PTR N ; EAX *= N (Elements of number of all the permutations) CMP EAX, ECX ; Compare EAX and ECX JE Fine ; If EAX == ECX (permutations done) then finish the program XOR EAX, EAX ; Otherwise reset EAX INC ESI ; Increment k index JMP CicloPermutazione ; Continue the loop Piccolo: ; If N = 0 or N = 1, the only permutation that can exists is made by only 1 element MOV Num, 1 MOV Perm[0], ECX Fine: }
验证效果
修复后N=1~6均可输出正确的无重复全排列,无错乱、重复问题。
内容的提问来源于stack exchange,提问作者maicol07
相关产品推荐
相关产品推荐

