没有分支或移位的绝对值,只有加/减和布尔值

2024-02-04

我们在学校为想要自我测试的学生遇到了这个问题。我在这方面花了相当长的时间,但无法弄清楚。

AX 寄存器中有 16 位数字,该数字是有符号的。得到它的 绝对值,AX中的数字必须不变 (编辑:寄存器数量没有限制,并且 AX 寄存器可以更改,但在函数结束时它需要是原始数量),以及答案 应该在BX。您只能使用这些说明:
MOV、ADD、XOR、SUB、NOT、AND、OR、NEG。

按照编译器的方式使用 SAR 非常容易,但如果没有它,就不清楚如何获得以符号位为条件的任何行为。


愚蠢的想法#1:查找表。这不能在 16 位实模式下工作。即使对于一个表来说整个 64kiB 段也是不够的;我们需要两倍的时间才能在 2 字节结果中查找任何可能的 16 位值。

我们可以通过 32 位寻址轻松做到这一点,例如xor ebx, ebx / mov bx, ax / mov bx, [table + ebx*2],如果您可以证明 128kiB 的表数据合理。 :P

完全在规则范围内,您可以在 32 位或 64 位模式下在堆栈上构造表sub esp, 1<<17并将数据存储为mov word [esp+0], 0 / mov word [esp + 2], 1/ 等。完全展开,无循环,因此大约有 256kiB 的机器代码。但同样,这在实模式下不起作用,而且对效率来说完全是个笑话。


我们可以使用 x86 部分寄存器恶作剧将符号位隔离为 0 / 1 整数:

    xor  dx, dx           ; DX = 0
    mov  dl, ah           ; DX = AX>>8   (zero extended)
    add  dx, dx           ; DX <<= 1  shifts the sign bit alone into DH

    mov  dl, dh
    mov  dh, 0            ; DX = (AX<0) = sign bit of AX zero extended to 16-bit

    neg  dx               ; DX = 0 or -1

或者最后3条指令可以优化为2条

    neg  dh               ; 0 or -1 according to sign bit of AX
    mov  dl, dh           ; duplicate to the full DX = 0 or -1

大奖;我们有我们的sar ax,15 or cwd具有所有位 0 或所有位 1 的值,广播 AX 的符号位,准备与 2 的补码标识一起使用 (如何证明 C 语句 -x、~x+1 和 ~(x-1) 产生相同的结果? https://stackoverflow.com/questions/2278518/how-to-prove-that-the-c-statement-x-x1-and-x-1-yield-the-same-results) 就像编译器使用 (https://godbolt.org/z/n3yoUp https://godbolt.org/z/n3yoUp).

通常你会使用xor ax, dx / sub ax, dx来修改原始值。

我之前认为这个挑战要求你避免修改任何other寄存器,否则对 AX 不修改的限制是微不足道的,不值得作为挑战的一部分。但我认为如果内存或其他寄存器中没有额外的暂存空间,这是不可能的。编辑澄清说没有必要这样做。

    mov  bx, ax
    xor  bx, dx           ; ~x      or x
    sub  bx, dx           ; ~x + 1  or x

异或与-1像 NOT 一样翻转所有位。异或与0是一个空操作。

子带-1增加 1,SUB 与0是一个空操作。 (0是加法和异或的单位元。)

所以这有条件地应用 2 的补码-x = ~x + 1身份。


PS:我花了几分钟的时间思考这个问题,排除了任何全注册方法,我very熟悉 x86 并且非常熟悉位操作,例如用 x86 机器代码编写 codegolf.SE 答案,并使用 SIMD 做一些重要的事情。在我看来,这是一个有趣的艰巨挑战。

而且,您永远不会想在现实生活中编写这样的代码;cwd or cdq效率更高,或者对于 AX 之外的源寄存器,复制和sar。部分寄存器的内容甚至会导致某些乱序执行 CPU(例如 Intel PPro 通过 Nehalem)停顿。


例如,关于Godbolt 编译器浏览器 https://godbolt.org/z/cHkXdo对于这个来源:

unsigned absval(int x) {
    return x<0 ? 0U - x : x;
}

使用无符号返回值可以让我们避免最负 2 的补码整数的有符号整数溢出未定义行为。 (-INT_MIN是未定义的行为)。我认为我编写它的方式实际上依赖于 C 实现是 2 的补码,因为0U - x皈依者x未签名以匹配另一方before使用它作为二进制的操作数-。或者也许这就是我们想要的,对于未签名的0U-x生产0x8000从输入0x8000(对于 16 位整数)。

GCC 这样做是为了设置 EAX = abs(EDI)(x86-64 System V 调用约定)。

    mov     eax, edi
    cdq                      ; sign-extend EAX into EDX:EAX
    xor     eax, edx
    sub     eax, edx
    ret

clang 对 x86-64 执行此操作,使用从 NEG 读取标志的条件移动:

    mov     eax, edi
    neg     eax                 ; 0 - x
    cmovl   eax, edi            ; copy the original if 0 was < x
    ret

在某些 CPU 上这样做会更高效:

    ; shorter critical path on CPUs where mov is not zero latency
    xor     eax, eax
    sub     eax, edi            ; 0 - x
    cmovl   eax, edi            ; copy the original if 0 was < x
    ret

Sandybridge 消除了异或归零,但没有消除 mov,对于不这样做的 CPUmov消除这缩短了关键路径。mov eax,edi处于关键路径上,但是xor-归零不是。或者我们可以这样做mov eax, edi / neg edi / cmovnl eax, edi再次允许 MOV 和 NEG 并行运行。

CMOV 是 Broadwell 之前的 Intel CPU 上的 2 uop 指令。 (CMOVA 和 CMOVBE 在当前的 Intel 上仍然是 2 uops,因为它们读取 CFandZF,在不同组中分别更名。其他都是1 uop)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

没有分支或移位的绝对值,只有加/减和布尔值 的相关文章

  • DASM 汇编器中的 ASCII 到 C64 屏幕代码

    我正在通过 C64 模拟器学习 6502 micro 的汇编 目前正在尝试将字符串输出到屏幕 这是我的代码 processor 6502 org 1000 ldx 00 using x register as column counter
  • 装配中出现奇怪的字符?

    我写了以下代码 386 model small stack 100h data text db Paper 0 code start lea dx text mov ah 9h int 21h mov ah 4ch int 21h end
  • 汇编中如何计算负数

    我是汇编新手 我有一个关于如何表示负数的问题 我有三个 DWORDS 变量 比方说 result DWORD 0 i DWORD 3 j DWORD 5 我想计算这个公式 结果 i j 8 但是 当我执行 i j 时 由于符号 结果将是一个
  • ConstantTimeByteEq 如何工作?

    在大神的密码库里 找到了这个函数ConstantTimeByteEq http golang org src pkg crypto subtle constant time go s 897 936 L17 它有什么作用 如何工作 Cons
  • 在 REP MOVSW 之前 PUSH CS / POP DS 的目的是什么?

    为什么在下面的代码中我们压入代码段 PUSH CS 然后将其弹出到数据段 POP DS 我将这些行明确指定为 line1 和 line2 请告诉我 MOVSW 在这里是如何工作的 IF HIGHMEMORY PUSH DS MOV BX D
  • 按位移位(左移或右移)有什么作用以及它的用途是什么?

    我见过运营商 gt gt and lt lt 在我看过的各种代码中 我真正理解的都不是 但我只是想知道它们实际上做了什么以及它们的一些实际用途是什么 如果班次就像x 2 and x 2 与实际使用的真正区别是什么 and 运营商 有性能差异
  • 对二进制数的字符串表示进行按位运算 python 2.7

    我想对二进制数的两个字符串表示执行按位或 但我不知道如何将字符串转换为原始二进制 a 010110 b 100000 a b 应该产生 110110 然后我想计算 on 位的数量 这应该返回 4 您可以使用内置的将字符串转换为二进制int
  • 预取双类成员需要转换为 char*?

    我有一个正在使用的课程 mm prefetch 预先请求包含 double 类型的类成员的缓存行 class MyClass double getDouble return dbl other members double dbl othe
  • 为 Visual Studio 应用程序设置平台目标的目的是什么?

    对于任何 VS 项目 都可以在该项目的构建属性中设置平台目标 您可以将其设置为任何 CPU x86 x64 或 Itanium 我的问题是 如果我将此值设置为 x86 是否意味着我无法在 x64 计算机上运行该项目 如果是这样 为什么还要使
  • 在 x86 程序集中将整数打印到控制台

    当我在 16 位汇编中添加两个值时 将结果打印到控制台的最佳方法是什么 目前我有这个代码 CODE START mov ax 1 put 1 into ax add ax 2 add 2 to ax current value mov ah
  • 汇编-符号标志和奇偶校验标志

    我不明白什么时候设置标志标志 什么时候设置奇偶校验 据我所知 符号标志表示运算结果的符号 0表示正数 1表示负数 那么为什么在下一个代码中 mov al 5 sub al 124 SF为零 结果是负数 关于PF 为什么a和b中设置了PF a
  • 取消的分支与常规分支有何不同?

    特别是对于 SPARC Assembly 取消的分支与常规分支有何不同 我一直认为 当我需要填充分支指令的 nop 延迟槽时 需要取消分支指令 但是 我认为我在这一部分上是不正确的 因为您可以在不取消分支的情况下填充 nop 如果不采用分支
  • 内联 asm 中不支持的指令“mov”将控制寄存器移动到 uint32_t

    我在 C 函数中使用汇编代码 但海湾合作委员会给出unsupported instruction mov 以下代码的错误 uint32 t faulting address asm volatile mov cr2 0 r faulting
  • 为什么不能执行 mov [eax], [ebx] [重复]

    这个问题在这里已经有答案了 我可以做这个 mov eax ebx 和这个 mov eax ebx 甚至这个 mov eax ebx 但不是这个 错误C2415 mov eax ebx 只是wtf 为什么 它与 ptr1 ptr2 相同 为什
  • CALL指令是否总是将EIP指向的地址压入堆栈?

    x86架构中函数调用时是否存在返回地址不入栈的情况 No CALL根据定义 将在跳转到目标地址之前将返回地址压入堆栈 该返回地址是EIP or RIP sizeof call instruction 通常为 5 个字节 英特尔 64 和 I
  • 为什么 RISC-V S-B 和 U-J 指令类型以这种方式编码?

    我正在读一本书 计算机组织与设计RISC V版 我遇到了 S B 和 U J 指令类型的编码 我上面提到的那些类型有奇怪的编码立即字段 S B 类型将直接字段分为两部分 这是有道理的 因为所有指令编码都必须相似 但我无法理解为什么立即字段以
  • 在 x86-64 CPU 上通过交叉修改代码重现意外行为

    Question 对于可能在 x86 或 x86 x64 系统上触发意外行为的交叉修改代码有哪些想法 在这些系统中 交叉修改代码中的所有操作均已正确完成 但在执行处理器之前执行序列化指令除外修改代码 如下所述 我有一个 Core 2 Duo
  • 两个基本的 ANTLR 问题

    我正在尝试使用 ANTLR 来获取简单的语法并生成汇编输出 我在 ANTLR 中选择的语言是 Python 许多教程看起来非常复杂或详细阐述与我无关的事情 我真的只需要一些非常简单的功能 所以我有两个问题 将值从一个规则 返回 到另一规则
  • 使用 Easy 68K (68000) 组装范围内的随机数

    我正在使用 Easy 68K 模拟器创建一个简单的黑杰克游戏 需要使用随机数来分配牌 我的牌必须在 2 到 11 的范围内 我似乎每次都得到相同的数字 但它不在我预期的范围内 我的卡值需要以 D3 结束 因此我有以下随机数代码 CLR L
  • Nasm 打印到下一行

    我用 nasm Assembly 编写了以下程序 section text global start start Input variables mov edx inLen mov ecx inMsg mov ebx 1 mov eax 4

随机推荐

  • 当 Cassandra 不知道“cassandra”默认用户时,如何重置 Cassandra 超级用户?

    如何在不更改源代码的情况下重置默认 Cassandra 凭据 我已经检查过类似的问题如何重置丢失的 Cassandra 管理员用户密码 https stackoverflow com questions 18398987 how to re
  • Eclipse 崩溃并且无法重新启动。我不明白堆栈跟踪

    Eclipse 崩溃并且无法重新启动 有人可以帮助我了解问题所在吗 日志中的消息如下 我在 Win7 上并使用 Android SDK 进行开发并且我最近安装了 subclipse svn 非常感谢 ENTRY org eclipse co
  • 在更新面板中突出显示 gridview 行而不回发

    我在更新面板中有一个网格视图 其中包含以下代码来选择一行 这反过来又使用表单记录中的详细信息更新另一个更新面板 protected void gvMainGrid RowDataBound object sender GridViewRow
  • 如何使用测试客户端和 post 方法测试带有 ModelChoiceField 的 Django 表单

    如何使用 Django test client post 来测试具有 ModelChoiceField 的表单 传递给post方法的数据字典应该怎么写呢 我所做的方式根本不选择任何值 我有一个包含以下字段的表单 country forms
  • 在动画或 SlideUp/slideDown 中使用 stop() 时的 jQuery 高度

    我有一个带有隐藏子菜单的菜单 我正在制作子菜单的动画 当我将鼠标悬停在菜单项上时打开 并在鼠标移出时关闭 当用户将鼠标悬停在许多菜单项上时 所有动画都会排队 为了解决排队问题 我在动画之前添加了 stop 这导致了更严重的问题 子菜单的高度
  • 从文件而不是备份“挂载”PostgreSQL 数据库

    我接到一个从 PostgreSQL 数据库中提取数据的项目 我以前没有使用 PostgreSQL 的经验 但我的项目是修复现有代码的错误 因此连接到引擎并获取数据的所有逻辑都已经就位 我遇到的问题是数据库以直接来自源 HDD 的文件夹和文件
  • 如何删除actionscript中字符串的一部分?

    所以我的字符串类似于 BlaBlaBlaDDDaaa2aaa345 我想摆脱它的子字符串 BlaBlaBlaDDD 所以操作的结果将是一个字符串 aaa2aaa345 如何使用动作脚本执行这样的事情 我只想用字符串 替换 http live
  • 无法使用 pymssql 连接到 SQL Server 数据库,但可以使用底层 freetds tsql 连接

    我不知道为什么会收到此错误 并且找不到任何解决方案 我可以使用 freetds tsql 连接到 SQL Server 数据库 但在使用连接时不断收到错误pymssql connect 具体错误是 pymssql OperationalEr
  • 类型错误:无法读取未定义的属性“消息” - Twitter API

    以下是运行 app js 时的输出 当一切正常时 这种情况完全随机发生 绝对没有做任何改变 TypeError Cannot read property message of undefined at home ec2 user envir
  • 颤动键盘完成按钮导致文本字段内容消失

    我的表单中有 2 个文本字段 当我单击第二个文本字段中键盘上的 完成 按钮时 键盘会隐藏 两个文本字段都会变空 当我手动关闭键盘时也会发生同样的情况 然后文本字段的内容也会丢失 看起来每次发生这种情况屏幕都会刷新 为什么会这样呢 overr
  • Android - Matcher.find() 无限

    我已经实现了 AsyncTask 其中用户提供的正则表达式用于匹配巨大的 html 代码数据 然而 由于某些正则表达式包含大量量词 回溯 Matcher find 会变得无限 我尝试过使用可中断字符序列此处提供 当 Matcher find
  • Spring Boot 令牌认证

    我尝试为另一个应用程序登录 Spring Boot 应用程序并使用 Spring Security 生成令牌 我试图实现的目标 用户名和密码发送到 REST 控制器 如果用户名和密码正确 我想生成具有 30 分钟过期时间的令牌并将其发送回用
  • ASP.NET 站点地图,有多重要?

    我的网站已经完成了 至少我是这么想的 我没有站点地图 奇迹般地我错过了站点地图的整个概念 甚至不知道它是一件事 我想我要向我的计算机老师大喊一声 我一直在阅读它 动态生成站点地图似乎相当复杂 我必须这样做 因为我的页面基本上只是一个使用参数
  • WPF:如何创建自定义项目控制面板?

    我想设计一个自定义项目控制面板ListBox 有3个要求 It should have the properties int rows and int columns which would define the matrix of cel
  • 设置 DOWNLOAD_DELAY 时 scrapy CONCURRENT_REQUESTS 被忽略?

    查看 scrapy 统计数据 Crawled X pages at X pages min 在我看来 一旦 例如 DOWNLOAD DELAY 4 5 设置后 请求将变为连续的 无论什么CONCURRENT REQUESTS塞特林群岛 根据
  • 如何读取匿名类型的属性?

    我有一个返回的方法 return new System Web Mvc JsonResult Data new Status OK 我需要编写一个单元测试来验证这一点jsonResult Data status OK 如何读取状态属性 更新
  • couchDB 中的链式映射/归约

    在 couchDB 中 我有一组如下所示的项目 为了示例而简化 id 1 date Jul 1 user user1 id 2 date Jul 2 user user1 id 3 date Jul 3 user user2 etc 我想获
  • 实体框架修改分离对象

    我有一些困惑 源于此http msdn microsoft com en us library vstudio bb896248 v vs 100 aspx http msdn microsoft com en us library vst
  • Laravel 检查用户电子邮件是否已验证

    您好 我想检查用户电子邮件是否仅在控制器中的一个功能中进行验证 我不想在中间件或路径中设置检查 如下所示 public function construct this gt middleware verified 因为控制器可供访客访问 所
  • 没有分支或移位的绝对值,只有加/减和布尔值

    我们在学校为想要自我测试的学生遇到了这个问题 我在这方面花了相当长的时间 但无法弄清楚 AX 寄存器中有 16 位数字 该数字是有符号的 得到它的 绝对值 AX中的数字必须不变 编辑 寄存器数量没有限制 并且 AX 寄存器可以更改 但在函数