时间戳

首页 > 解决方案 > log2 在位操作中的作用是什么？

c++ - log2 在位操作中的作用是什么？

问题描述

为什么我们使用 log2 来获取最右边设置位的位置？我无法理解。完整的代码在这里。非常感谢！

unsigned int getFirstSetBitPos(int n) 
{ 
    return log2(n & -n) + 1; 
}

标签： c++bit-manipulation

解决方案

来自维基百科上的二进制对数：

在数学中，二进制对数 (log 2  n ) 是必须将数字 2 提高才能获得值n的幂。也就是说，对于任何实数x，

     x = log 2 ⁡<em>n ⟺ 2 x = n。

例如，1的二进制对数为0，2的二进制对数为1，4的二进制对数为2，32的二进制对数为5。

因此，在您的代码中，n & -n首先关闭除最初设置为 1 的最右边位以外的所有位，然后取该结果数的 log 2以获得其 2 的幂（恰好与设置为 1 的位的从 0 开始的位置），最后在该结果上加 1 以获得从 1 开始的位位置（这很奇怪，因为位通常由它们的从 0 开始的位置来引用）。

例如，让我们看看5. 在二进制中，5 是位00000000000000000000000000000101（假设是 32 位int类型），并且-5是位11111111111111111111111111111011（假设负整数是使用2s-complement实现的）。请记住，&运算符执行按位AND运算，1仅当给定位1在两个输入数字中时才返回给定位的 a，否则返回 a 0。因此：

  00000000000000000000000000000101 (5)
& 11111111111111111111111111111011 (-5)
----------------------------------
  00000000000000000000000000000001 (1)

所以，5 & -5 = 1，然后log2(1) = 0，和0 + 1 = 1。

让我们看一个更复杂的数字，1041204192即 bits00111110000011111000001111100000和-1041204192bits 11000001111100000111110000100000：

  00111110000011111000001111100000 (1041204192)
& 11000001111100000111110000100000 (-1041204192)
----------------------------------
  00000000000000000000000000100000 (32)

所以1041204192 & -1041204192 = 32， 那么log2(32) = 5， 和5 + 1 = 6。

只是为了踢，让我们看看0：

  00000000000000000000000000000000 (0)
& 00000000000000000000000000000000 (-0)
----------------------------------
  00000000000000000000000000000000 (0)

所以0 & -0 = 0, and log2(0)is对于整数来说-INFINITY是未定义的。

这里是-1：

  11111111111111111111111111111111 (-1)
& 00000000000000000000000000000001 (--1)
----------------------------------
  00000000000000000000000000000001 (1)

所以(-1) & -(-1) = 1， 那么log2(1) = 0， 和0 + 1 = 1。

并且-2：

  11111111111111111111111111111110 (-2)
& 00000000000000000000000000000010 (--2)
----------------------------------
  00000000000000000000000000000010 (2)

所以(-2) & -(-2) = 2， 那么log2(2) = 1， 和1 + 1 = 2。

等等...

推荐阅读