bit-manipulation - 位操作的时间复杂度

Question

由于一些原始研究和需要为其开发工具，我想出了一些新的，我希望能更好/更快地执行某些数学运算。 Atm 我正在研究伪代码，将它们发布在网站上，以回答已经提出的问题。

然而，在我这样做之前，我想尽可能地优化它们，所以我需要有人从时间复杂度的角度阐明位操作是如何工作的。

例如说我想评估两个 8 位整数中哪个更大。我以 8 位为例，但实际上它们可能更大。

10000100

10100000

就目前而言，可以通过比较 6 个 MSB 来评估关系运算符。
从理论上讲，我可以从两者中减去 10000000 而不影响不等式。

00100000

00000100

一季度。这将加速关系运算符的评估，如果
读取从 MSB 开始，但这样做或做前导 0
无论如何都必须评估？明显的减法不值得做
因为减去 10000000 本身就是一个 8 位操作，但是说
相反，我可以使用单个或两个设置 MSB 或特定位
位操作那么它可能是值得的。

Q2。我能想到的两种可能符合要求的方法是
左移然后右移以破坏前导 1 或使用
一个面具，但还有其他方法吗？我特别感兴趣
可能让您设置任何位而不仅仅是前导位的那些。如果
它特定于某种语言，请让我知道。

Q3。由于掩码是 N 位，因此使用的是掩码而不是 N 位
操作本身？

第 4 季度。如何评估特定位，存在哪些方法以及
操作的时间复杂度如何？所有进行的位都必须
首先读入，以便它是 N 位操作，或者您可以“跳转”
到某一点？

Q5 从时间复杂度共轭的两个字符串
看法。这是通过关联两个内存地址来实现的吗
或者一个字符串是否被读取并复制到另一个字符串中
这是一个 String.length 操作？

谢谢。

进一步澄清。
我一直在重读我从几个地方提取的笔记，虽然杜克林确认了我认为应该是这样的情况，但我需要三重检查。以简单的乘法算法为例。我在很多地方都看到声称这是一个 Log^2(N) 操作，并且它是 Log^2(N) 操作的给定原因是由于它由 Log(N) 的 Log(N) 加法组成数字。我对此的问题是，虽然这是真的，但它忽略了这样一个事实，即每个 Log(N) 数字都是位移的结果，到最后我们将至少位移 Log(N) 次。由于位移 1 是 Log(N) 操作，因此单独考虑位移会给我们 Log^2(N) 操作。因此，当我看到它进一步声称实际上乘法实际上并不使用 Log^2(N) 运算时，这对我来说毫无意义，因为各种方法可以减少所需的加法次数。由于仅位移位就给了我们 Log^2(N) 我对这种说法如何成真感到困惑。

Answer 1

必须评估前导 0 位，除非您存储 MSB 的索引并编写自己的例程来进行比较。

位移位是 N 位操作。

屏蔽也是 N 位操作。

取决于你在内部如何表示它，跳转到正确的 相对容易。字节 ，但高级语言(如果您正在使用)通常不允许您直接访问特定位，您需要进行一些操作(例如位移(仅该字节))来获得该位。

连接字符串需要 O(m+n)，其中 m 和 n 是各个字符串的长度。我知道的所有字符串都在内存中按顺序表示。您也不一定有权访问任何一个字符串之后的内存(除非您通过分配足够的内存来强制执行此操作)，因此必须将两者都复制到新位置。尽管没有什么能阻止您创建自己的数据结构。

所以......只是一个直接的逐位或逐字节比较(可能与 1 中提到的起始位置优化)可能是你得到的最好的。

PS - 任何发布的研究都应该显示足够的证据(以某种形式)作为动机，说明为什么它比其他东西更好。