1.概述

一些算法基于他们的想法二进制整数的表示。在本教程中,我们将演示两种查找整数中最高位的算法。

我们将首先提供一些定义,这些定义应该有助于我们理解所提供的方法。在那之后,我们将解释简单的方法,并使用一些事实来获得一个更好的方法,具有较低的时间复杂度。

2.定义

让我们快速介绍一个将非负整数从十进制转换为二进制格式的提示。在此之后,我们将介绍位操作和一个等式,我们稍后将需要它来优化简单方法。

2.1。从十进制到二进制表示

让我们提供一个例子来解释这个想法。假设这个数是89,我们想用二进制格式。

看看这些步骤:

我们执行多个步骤,直到数字达到零。在每一步中,我们把这个数除以2。同样,我们得到这个数除以2后的模,然后把它加到答案中。

最后,答案是0和1的列表我们用这个数除以2取模得到的。

注意,最高位是我们存储的最后一位。类似地,最低有效位是我们得到的第一个。

2.2。按位操作

大多数编程语言支持应用于非负整数的运算。这些运算的用途是对一个特定数字的二进制表示的位进行操作。

对于本文,我们感兴趣的是表示为的左移操作(\噢)。该操作将数字的二进制格式向左移动特定数量的位。例如,\ boldsymbol {(1 \ ll b)}表示将位移1\ boldsymbol {b}乘以左边。结果是\ boldsymbol {2 ^ {b}},因为它只有b \ boldsymbol {^ {th}}位被激活,而所有其他的都被关闭。

2.3。最重要的一点

关于二进制数的有趣之处在于如下等式:金宝搏官网188be

\ [\ boldsymbol {\ sum_ {i = 0} ^ {k} 2 ^{我}= 2 ^ {k + 1} - 1} \]

由这个方程我们可以得出:

\ [\ boldsymbol {\ sum_ {i = 0} ^ {k} 2 ^{我}< 2 ^ {k + 1}} \]

这意味着每一个比特k当被激活时,其值大于所有小比特的总和,即使所有小比特也被激活。当我们以后改进这种简单的方法时,这个观察结果将对我们有所帮助。

3.天真的方法

对于简单的方法,我们将一个一个地提取二进制表示的位。对于每个位,我们检查其值并存储最有意义的活动位。

看看朴素方法的实现:

呈现由QuickLaTeX.com

我们先初始化指数0表示当前位索引。我们还设置最高有效位为-1,这将存储最高位的索引。

之后,我们执行多个步骤。在每一步中,我们通过取除后的余数来获得当前位的值n由2。同时,我们将n2到下一步。请注意,这些步骤类似于获得我们在2.1节中解释过的数字的二进制表示。

对于每个比特,我们检查它是否被激活。如果是,则将其索引存储为迄今为止找到的最高位。同时,我们增加指数移到下一个位置。

一次n等于0,意味着我们遍历了n。此时,我们返回所需的索引。

值得注意的是,当n是零,然后呢而循环不会被执行。算法返回-1,表示n没有任何激活的比特。

天真方法的复杂性是\ boldsymbol {O (log (n))},在那里n是必需的非负数。

4.二分查找方法

首先,让我们解释一下使用二分查找解决此问题的算法。然后,我们可以实现算法。

4.1。一般的想法

在2.3节中,我们注意到每个比特的值都大于所有较低比特的值,即使所有比特都被激活。我们可以利用这个事实找到最高位的下一位。下一点,我们指的是这一点msb + 1,在那里最高有效位是最重要的一个。

而不是执行线性搜索为了找到这个位,我们可以使用二进制搜索算法。

一开始,我们需要知道可能是答案的最大索引。我们把这个值表示为马克斯。答案就在这个范围内[0,马克斯]

为了找到最高位旁边的位,我们检查搜索范围的中间。假设当前搜索范围为(左,右),中间值是中期

如果\ boldsymbol{(1 \会中期)}大于\ boldsymbol {n},那么这可能是必要的部分。在这种情况下,我们可以得出结论,这个比特要么是这个,要么是一个更小的比特。因此,它在这个范围内\黑体符号{[L,中- 1]}

然而,如果\ boldsymbol{(1 \会中期)}并不大于\ boldsymbol {n},那么这一点不可能是下一个最重要的。因此,搜索范围成为\黑体符号{[mid + 1, R]}因为我们需要尝试增加位的索引。

让我们使用这些思想来实现二分搜索方法。

4.2。实现

看看二进制搜索方法的实现:

呈现由QuickLaTeX.com

首先,我们进行初始化lR作为搜索范围。如我们所见,l从零开始,而R从最大可能的答案开始马克斯。我们加了1马克斯因为我们要找的是最高位的下一位。

同时,我们初始化最高有效位它将保存最有效位的索引。

在二分查找操作的每一步中,我们计算中点中期搜索范围的。然后,我们检查是否中期比特值大于n。如果是这样,那么我们有一个可能的答案。

在这种情况下,我们存储前面的位作为可能的答案到目前为止。我们还移动了搜索范围的右侧R \ boldsymbol {}中期\ boldsymbol {1}因为我们应该检查更小的值。

另一方面,如果值中期\ boldsymbol {}比特不大于\ boldsymbol {n},然后移动搜索范围的左边L \ boldsymbol {}中期\ boldsymbol {+ 1}。这是因为我们需要寻找更大的值。

最后,返回存储的答案最高有效位

天真方法的复杂性是\ boldsymbol {O (log (log (n)))},在那里n是所需的号码。原因是我们要对位进行二分查找n。因为位的数目nlog (n),我们执行二分查找操作,那么复杂度就是比特数的对数。

5.例子

让我们以2.1节中描述的相同的例子来看看这两种算法是如何计算最重要位的。在这个示例中,n等于89。

5.1。天真的方法

检查描述算法步骤的表:

呈现由QuickLaTeX.com

我们主要是提取部分n一个接一个。在每一步中,如果位等于1,我们存储电流指数随着最高有效位

最后,我们会得到结果最高有效位

5.2。二分查找方法

对于二分查找,我们将使用类似的n = 89,但我们假设马克斯= 8。让我们看看这个算法是如何工作的:

呈现由QuickLaTeX.com

在每一步中,我们计算范围的中点(左,右)。然后,我们比较(1 \会中期)n然后决定是在值域的左边还是右边。另外,当(1 \会中期)大于n,我们商店中期1与当前最高有效位

正如我们所看到的,在二叉搜索方法中,我们最终进行了较少的比较。

6.比较

正如我们所看到的,使用二叉搜索操作可以降低复杂度。然而,有一个主要的条件可以使用二分搜索操作。初始化的可能答案必须有一个上界R马克斯

如果我们不能估计最有效位索引的上界,那么我们应该采用简单的方法,它的复杂性并没有那么糟糕。

7.结论

在本教程中,我们讨论了寻找给定非负整数的最高位的问题。

我们提出了一些与给定非负整数的二进制表示有关的思想。基于这些想法,我们能够开发一个简单的方法,并优化它达到二分搜索方法。

最后,我们对两种方法进行了快速比较,并给出了使用二分搜索方法的要求。

对这篇文章的评论关闭!