如何清除最重要的位？

Question

如何将int中的最高位从1更改为0？例如,我想将01101更改为0101.

Answer 1

编辑:简化(和解释)答案

如果您的唯一目标是将最重要的位设置为零,那么我在下面给出的答案是过度的.

最后一位代码构造一个包含该数字中所有位的位掩码.

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,包括最初设置的最重要位,但不高.

从这个面具是相当容易收缩它包括所有的,但最初设定的最显著位:

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

五

(这是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

Answer 2

执行此类按位运算的最简单方法是使用左移运算符 (<<)。

(1 << 3) = 100b，(1 << 5) = 10000bETC。

然后您使用一个要更改某个位的值并使用
| (或) 如果您想将其更改为 1 或
& ~ (而不) 如果您想将其更改为 0。

像这样：

int a = 13; //01101
int result = a | (1 << 5); //gives 11101
int result2 = result & ~(1 << 5); //gives 01101