如何清除最高有效位？

如何将 int 中的最高有效位从 1 更改为 0？例如，我想将01101更改为0101。

编辑：简化（并解释）答案

我在下面给出的答案是多余的，如果你only目标是将最高有效位设置为零。

代码的最后一位构造了一个位掩码，其中包含数字中的所有位。

mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;

以下是它对给定 32 位无符号整数执行的一系列计算：

mask = originalValue
mask:               01000000000000000000000000000000
mask |= mask >> 1:  01100000000000000000000000000000
mask |= mask >> 2:  01111000000000000000000000000000
mask |= mask >> 4:  01111111100000000000000000000000
mask |= mask >> 8:  01111111111111111000000000000000
mask |= mask >> 16: 01111111111111111111111111111111

由于它会向右移位（不会回绕），因此它永远不会将高于最高有效位的位设置为 1。由于它使用的是逻辑or，您永远不会将任何尚未为零的值显式设置为零。

从逻辑上讲，这将始终创建一个填充整个的位掩码uint，直到并包括最初设置的最高有效位，但不能更高。

从该掩码中可以很容易地将其缩小以包含所有内容but最初设置的最高有效位：

mask = mask >> 1: 00111111111111111111111111111111

然后做一个逻辑and与原始值相反，它将把数字中的所有最高有效位设置为零，直到并包括原始值的最高有效位：

originalValue &= mask: 00000000000000000000000000000000

我在这里使用的原始数字很好地显示了掩模构建过程，但它并没有很好地显示最后的计算。让我们用一些更有趣的示例值（问题中的值）来进行计算：

originalValue: 1101
mask = originalValue
mask:               00000000000000000000000000001101
mask |= mask >> 1:  00000000000000000000000000001111
mask |= mask >> 2:  00000000000000000000000000001111
mask |= mask >> 4:  00000000000000000000000000001111
mask |= mask >> 8:  00000000000000000000000000001111
mask |= mask >> 16: 00000000000000000000000000001111
mask = mask >> 1:   00000000000000000000000000000111

这是您正在寻找的值：

originalValue &= mask: 00000000000000000000000000000101

既然我们可以看到这是有效的，那么让我们将最终的代码放在一起：

uint SetHighestBitToZero(uint originalValue)
{
    uint mask = originalValue;

    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;

    mask = mask >> 1;

    return originalValue & mask;
}

// ...
Console.WriteLine(SetHighestBitToZero(13)); // 1101

5

（即0101）

我给出的原始答案

对于这类问题，我经常参考这篇文章：

“有点摆弄黑客”

您想要的特定部分称为“查找整数的以 2 为底的整数对数（也称为最高位集的位置）”。

这是一系列解决方案中的第一个（每个都比前一个更优化）：

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

文章中最终的解决方案是（转换为C#）：

uint originalValue = 13;
uint v = originalValue; // find the log base 2 of 32-bit v
int r;  // result goes here

uint[] MultiplyDeBruijnBitPosition = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = (int)MultiplyDeBruijnBitPosition[(uint)(v * 0x07C4ACDDU) >> 27];

一旦找到最高设置位，只需将其屏蔽即可：

originalValue &= ~(uint)(1 << r); // Force bit "r" to be zero