😚 🧝🏿 👈 O中的整数对数2（1） ♏️ 👸🏽 🏇🏼

通常必须计算任何整数对数2的全部。

正面决策是要进行循环，并在该循环中不断将数字除以2，直到变为零为止。对数的值就是发生了多少这样的除法。是的，这种方法有效并且具有生命权，但是我想展示如何在没有任何周期和复杂结构的情况下完成该方法。

因此，我们要计算以下公式：

y = [l o g_{2} (x)], x - ц е л о е, п о л о ж и т е л ь н о е

$y = [log_2(x)], x - ,$

决断

对于那些对推理不感兴趣的人，我将立即提供现成的函数来计算对数：

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

说明

首先，让我们将数字x转换为一定长度的二进制符号。

例如，length = 8，但这并不重要，数字的长度可以是任意长度。

现在，请记住将数字转换为二进制表示法的依据。将数字表示为2的幂。度数将确定位的位置，即1。例如：

45 = 32 + 8 + 4 + 1 = 2^{5} + 2^{3} + 2^{2} + 2^{0}

$45 = 32 + 8 + 4 + 1 = 2^5 + 2^3 + 2^2 + 2^0$ ... 那些。分别对5、3、2和0进行幂运算。这意味着第5、3、2、0位等于1。它们之间的其余位等于0。位从右侧开始。结果表明

45_{10} = 101101_{2}

$45_{10} = 101101_2$

可以注意到，转换为二进制表示法与指数密切相关，对数是指数的倒数，并且等于指数。

2^{y} = x, y = l o g_{2} (x)

$2^y = x, y = log_2(x)$

此外，您需要提高2的指数是二进制表示法中的单个位数。事实证明，如果我们找到单个位的数目，那么我们将对数值的整数部分以2为底。例如，如果32 = 100000，则一位在第五位，因此对数是5。

但是由于可能有多个而不是1，因此出现了要找出对数的哪一位的问题。答案是从数字记录的右侧开始的最后一位的数字，因为确定对数的整个部分的是两位的最高幂，其余部分构成了对数的小数部分。

考虑另一个例子-一个数字

45_{10} = 101101_{2}

$45_{10} = 101101_2$ ... 最后一位在第5位，因此对数45的整数部分是5。实际上

l o g_{2} (45) = 5.4919

$log_2(45)=5.4919$ ... 我们丢弃小数部分并保留5。

它也可以与其他数字一起使用。

结果，我们得到了对数的整数部分等于从右数到最后一位的数字。问题：如何找到最后一位的编号？

为此，有一些基于按位运算的函数，我在G. Warren的书中找到了“程序员的算法技巧”。

向下舍入为2的幂（或突出显示数字的二进制表示法的最后一位）。实际上，您可以四舍五入，但是对数值也会四舍五入。
计算数字的二进制表示法中的单个位数

这两个函数在这里都有很好的描述，我之前已经给出了它们的代码。

使用这两个函数，用于计算算法的算法如下：

选择数字的最后一位。现在数字已写为100000
从结果中减去一个。然后数字将像这样：011111
计算单位位数，这将是对数的整数值

特殊情况

当x = 0时，对数具有特殊情况。理论上，这种算法不存在（或在极限条件下等于-∞）。但是，由于我们在编程中偏离了数学定律，因此即使函数的输入为零，这些函数仍然可以工作。在这种情况下，对数的值为32（如果数字为32位）。这是因为舍入到最接近的2的幂的函数将给出0，然后我们从零中减去1并得到数字0xFFFFFFFF，并且该数字中有32个单位，因此对数将为32。

是的，从数学的角度来看，这是错误的，但是在某些情况下，从编程的角度来看很有用。

计算二进制代码的长度

这种函数不太可能用于计算数学对数，因为通常考虑实数的对数，而不是整数。

但是，在实践中，计算二进制代码的长度是更常见的任务。

给出一定长度的二进制代码。例如，这可能是二叉树中的路径。如果在此代码的前面写了一位，则可以通过取整数对数来计算该代码的长度而无需使用辅助变量。

例如，给定代码0001110110，例如，它写在32位单元格中，我们经常需要读取该代码的长度。为此，在代码之前再添加一位。

我们得到：10001110110。现在我们可以通过整数对数安全地计算该代码的长度，而无需在其他地方单独存储此代码的长度。

如果我们考虑代码的长度（全为零），则该函数将返回长度= 32，这可能是不正确的，因此必须预见这种情况。在某些情况下，该函数返回32是有用的，而在其他情况下，例如返回零。

资料来源

G. Warren“程序员的算法技巧”。修订版。，2004年

O中的整数对数2（1）

决断

说明

特殊情况

计算二进制代码的长度

资料来源

More articles: