移位是 O(1) 还是 O(n)?

2023-12-29

是否轮班操作O(1) or O(n) ?

计算机通常需要更多的操作来移动 31 位而不是移动 1 位,这是否有意义?

或者说这是否有意义操作次数换档所需的是constant不管我们需要转移多少地方?

PS:想知道是否hardware是一个合适的标签..


某些指令集仅限于每条指令一位移位。某些指令集允许您在一条指令中指定要移动的任意数量的位,这在现代处理器上通常需要一个时钟周期(“现代”是一个故意模糊的词)。看dan04 的回答 https://stackoverflow.com/a/9083865/4098326关于桶形移位器,一种在一次操作中移位多个位的电路。

这一切都归结为逻辑算法。结果中的每一位都是基于输入的逻辑函数。对于单个右移,算法将类似于:

  • 如果指令是[右移]且输入的位1为1,则结果的位0为1,否则位0为0。
  • 如果指令是[右移],则位1 = 位2。
  • etc.

但逻辑方程也可以很容易地表示为:

  • 如果指令是[右移]并且数量操作数为1,则结果位0 = 移位的输入位1。
  • 如果金额为 2,则位 0 = 位 2。
  • 等等。

逻辑门是异步的,可以在一个时钟周期内完成所有这些工作。然而,如果您要比较的只是这两种类型的指令,那么单移确实可以实现更快的时钟周期和更少的门来稳定。或者替代方案是使其需要更长的时间才能稳定,因此指令需要 2 或 3 个时钟或其他时间,逻辑计数到 3,然后锁存结果。

例如,MSP430 仅具有单位右移指令(因为您可以使用另一条指令执行单位移位或左循环,我将留给读者自行解决)。

ARM 指令集允许立即数和基于寄存器的多位循环、算术移位和逻辑移位。我认为只有一个实际的旋转指令,另一个是别名,因为向左旋转1与向右旋转32相同,你只需要一个单向桶形移位器来实现多位旋转。

x86 中的 SHL 允许每条指令有多个位,但过去它需要多个时钟。

等等,您可以轻松检查其中列出的任何说明。

你的问题的答案是它不是固定的。有时是一次操作、一个周期、一条指令。有时它是一条指令多个时钟周期。有时它是多条指令、多个时钟周期。

编译器通常会针对此类事情进行优化。假设您有一个 16 位寄存器指令集,其中包含交换字节指令和带有立即数但只有单个位移位的 AND 指令。您可能认为移位 8 位需要 8 个移位指令周期,但您可以只交换字节(一条指令),然后将下半部分与零(这可能需要两条指令,或者可能是两个字的可变字长指令,或者它可能编码成一条指令),因此只需要 2 或 3 个指令/时钟周期而不是 8 个。对于 9 位的移位,您可以做同样的事情并添加一个移位,使其需要 9 个时钟而不是 3 或 4 个时钟周期.此外,在某些体系结构上,乘以 256 比移位 8 等更快。每个指令集都有其自己的限制和技巧。

甚至大多数指令集都提供多位或大多数限制为单个位的情况都不是这样。属于“计算机”类别的处理器,如 X86、ARM、PowerPC 和 MIPS,将倾向于一种操作来转换。扩展到所有处理器,但不一定是当今常用的“计算机”,并且它以另一种方式移位,我想说的是,其中更多的是单位而不是多位,因此需要多个操作来执行多位移位。

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

移位是 O(1) 还是 O(n)? 的相关文章

  • 什么时候函数名太长?

    在可能的情况下 我尝试对我的函数名称进行描述 这有时会导致函数名称在二十到三十个字符范围内 例如GetActionFromTypeName or GetSelectedActionType 在什么时候函数会变得太长而难以管理 对于编译器来说
  • 什么是微编码指令?

    我看过很多参考微编码指令的文献 这些是什么以及为什么使用它们 CPU 读取机器代码并将其解码为内部控制信号 将正确的数据发送到正确的执行单元 大多数指令映射到一个内部操作 并且可以直接解码 例如 在 x86 上 add eax edx只是将
  • 如何检测(心电图)波的模式?

    我正在尝试读取心电图图像并检测其中的每个主波 P 波 QRS 波群和 T 波 我可以读取图像并获得向量 例如 4 2 4 4 4 9 4 7 我需要一种算法来遍历这个向量并检测每个波何时开始和结束 一个例子 如果它们总是具有相同的大小 或者
  • 您能解释一下流的概念吗?

    我知道流是字节序列的表示 每个流都提供了向其给定的后备存储读取和写入字节的方法 但流的意义何在 为什么我们与之交互的不是后备存储本身 不管出于什么原因 这个概念并不适合我 我读过很多文章 但我想我需要一个类比或其他东西 选择 流 这个词是因
  • 找出数组中重复的元素

    有一个大小为 n 的数组 数组中包含的元素在 1 到 n 1 之间 每个元素出现一次 只有一个元素出现多次 我们需要找到这个元素 尽管这是一个非常常见的常见问题解答 但我仍然没有找到正确的答案 大多数建议是我应该将数组中的所有元素相加 然后
  • 是否可以通过括号来防止死亡?

    有时 我会编写一些带有比我喜欢的更多括号的代码 if new Day new Date millisecondsPerDay 75 instanceof oldDay Bonus points if that condition made
  • 3 维装箱算法

    我面临着 3 维装箱问题 目前正在进行一些初步研究 了解哪些算法 启发式方法目前能产生最佳结果 由于问题是 NP 难问题 我不希望在每种情况下都能找到最佳解决方案 但我想知道 1 最好的精确求解器是什么 分支定界 我期望使用合理的计算资源可
  • 语法分析和语义分析有什么区别?

    据我了解 Parser由词法分析 句法分析和语义分析三个阶段组成 Lexical 它将我的输入分割成标记 例子 123 100 0 gt 123 100 0 语法 它将研究标记并检查它们是否彼此有意义 我遇到的问题是理解最后阶段的 语义解析
  • 有没有办法获取正在运行或新打开的资源管理器窗口的 IExplorerBrowser 接口以供后续 BrowseToXXX 调用?

    这么问是因为在上一个问题 https stackoverflow com questions 6220899 answer 6221898我是指向 IExplorerBrowser 的指针 但是它创建了一个子窗口 而我想模拟资源管理器的 查
  • 如何使用 Trie 进行拼写检查

    我有一个根据单词词典构建的特里树 我想用它来进行拼写检查 并建议字典中最接近的匹配项 也许对于给定数量的编辑x 我想我会在目标单词和字典中的单词之间使用 levenshtein 距离 但是有没有一种聪明的方法可以遍历 trie 而不需要对每
  • C++ 中的 CPUID 实现

    我想知道这里是否有人有一些可以从任何托管 net 语言引用的 C CPUID 实现的好示例 另外 如果情况并非如此 我是否应该注意 X86 和 X64 之间的某些实现差异 我想使用 CPUID 来获取运行我的软件的机器上的信息 崩溃报告等
  • 在二维平面中找到距离 P 点最近的 K 个点

    资料来源 亚马逊面试问题 解决方案1制作大小为 K 的堆并按最小距离收集点O NLogK 复杂 解决方案2 取大小为 N 的数组并按距离排序 应该使用QuickSort 霍尔修改 取前 K 点作为答案 这太复杂了 NlogN 但可以优化到近
  • for循环内递归函数的时间复杂度

    如果我们有一个函数 int x 0 int fun int n if n 0 return 1 for int i 0 i
  • 普通的 x86 或 AMD PC 是直接从 ROM 运行启动/BIOS 代码,还是先将其复制到 RAM? [关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 我知道现代计算机已经修改了哈佛架构 它们可以从保存数据的地方以外的地方读取指令 这一事实是否允许它们直接从 ROM 芯片获取指令 他们是先
  • 替代位置基础系统(十六进制、八进制、二进制)如何工作?如何将它们转换为十进制?

    我以前在编程课上没有学过这一点 但现在我需要知道它 有哪些学习这些数字以及如何转换它们的好资源 我几乎会像记住乘法表一样记住这些 在我们日常的十进制系统中 基数或radix http en wikipedia org wiki Radix
  • 递归和大O

    我最近正在完成一项涉及递归和大 O 表示法的计算机科学作业 我相信我很好地理解了这一点 虽然当然不是完美的 但是有一个问题给我带来了最多的问题 奇怪的是 一看就知道是作业上最简单的一个 使用大哦符号提供最佳增长率来解决以下递归问题 T 1
  • 什么是悲观主义?

    该问题有评论可以使用C 11的吗auto提高性能 https stackoverflow com questions 32510183 can the use of c11s auto improve performance这获得了很多选票
  • 需要帮助解决 Project Euler 问题 200 [已关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 我正在尝试制定一个算法来解决 We
  • 获取总体 CPU 百分比使用率的可能性有哪些

    我有以下问题 在UWP中 我们如何获取总体CPU使用率 RAM使用率 可用RAM 正在运行的进程等 UWP 中的任务管理器需要它 您好 经过一番查看后 您似乎无法获得设备 CPU RAM 和可用 RAM 或正在运行的进程 您可以获得 CPU
  • 快速约会算法

    我在一家咨询公司工作 大部分时间都在客户所在地 正因为如此 我很少见到同事 为了更好地了解彼此 我们将安排一个晚宴 会有很多小桌子 方便人们聊天 为了在聚会期间与尽可能多的不同的人交谈 每个人都必须每隔一段时间 比如每小时 换一张桌子 如何

随机推荐