如何使用位运算补足最右侧的比特位，同时保持前导零比特位为零？

Question

如何使用位运算补足最右侧的比特位，同时保持前导零比特位为零？

3

如何对具有前导零位的数值进行补充，使前导零位保持为零，并将其余的一和零位进行补码处理？我想仅使用按位操作来完成这个过程，而不是必须检查该值以确定该值中有多少前导零位。我可以使用哪些按位操作来隔离只包含一位或打开位的最低有效部分，并补足该值的仅该部分，使前导零位保持不变。

例如，给定一个数字9。

9将以32位无符号二进制形式表示为00...01001。

为了简单起见，仅考虑8位形式。 9 = 00001001

现在当我补足这个数字时，我会得到 11110110。

但这不是我想要的。

我希望原始表示法中的前导0保持不变，并补足其余部分。

即对于9 = 00001001，前导的4个零应该保持为零，下一部分应该被补足。因此我会得到00000110，即6。

我知道一种稍长的方法:

1.查找给定数字的位数，称为b 2.查找给定数字的补码，称为x 3.提取最后的b位

或者

3.从x中减去（0xFF << b）

- Bhavesh Munot

是的，这两种方法都应该可以工作。 - Oliver Charlesworth

@OliverCharlesworth，它们确实有效，我正在寻找一种更好的方法！ - Bhavesh Munot

2个回答

2

看起来你需要检查值中的位，以便构建一个只使用你想要的位的掩码。

以下代码似乎是可移植的最佳情况。它使用unsigned long作为函数类型，以允许升级和缩减，因此它可以与字节（8位或unsigned char）、字（16位或unsigned short）或双字（32位或unsigned long）变量一起使用。如果你需要64位，则可以在函数ulComplLeastSig()中使用unsigned long long，并对ulMask和ulBit进行适当的值更改。

这段代码构建了一个掩码，然后使用位运算来消除应该为零的前导位。通过查看Visual Studio版本生成的机器代码，可以发现代码循环中的变量保持在寄存器中，非常紧凑。

unsigned long ulComplLeastSig (unsigned long ulValue)
{
    unsigned long ulMask = 0xffffffff;
    unsigned long ulBit  = 0x80000000;

    for (; ulBit; ulBit >>= 1) {
        // beginning with the most significant bit, turn off bits in the mask
        // until we find the first on bit in the value. this creates our
        // mask to remove leading zeros after we complement.
        if (ulBit & ulValue) break; else ulMask ^= ulBit;
    }
    return (ulMask & (~ulValue));
}

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long  ulValue = 9;
    unsigned long  ulNewValue = 0;
    unsigned short usValue = 9;
    unsigned short usNewValue = 0;

    ulNewValue = ulComplLeastSig (ulValue);

    // use the function with an unsigned short. cast the return value
    // to remove compiler warnings. depend on promotion for the function
    // argument.
    usNewValue = (unsigned short)ulComplLeastSig (usValue);

    return 0;
}

编辑

我再仔细思考了一下，想知道是否可能在循环中只使用位运算来消除if语句，并想到了这个可能性。

unsigned long ulComplLeastSig_2 (unsigned long ulValue)
{
    unsigned long ulMask = 0xffffffff;
    unsigned long ulBit  = 0x80000000;

    // complement the value so that we are ready to start
    // creating our mask.  the goal is to create a mask
    // that will get rid of the leading ON bits from the
    // complemented value by starting with all the bits
    // of the mask turned on then moving through the
    // complemented value bit by bit turning off bits in the
    // mask until we need to stop.
    ulValue = ~ulValue;
    for (; ulBit; ulBit >>= 1) {
        ulBit &= (ulBit ^ (ulMask ^= (ulBit & ulValue)));
    }
    return (ulMask & ulValue);
}

- Richard Chambers

1

毫不冒犯，但是这种方法为什么比我的生成掩码的并行前缀更好呢？这将是一个相当长的循环，具有糟糕的预测分支。 - harold

@哈罗德，不确定从计算上讲是否更好。它易于理解和操作，并且应该可以在各种架构中轻松移植。例如，如果这是一个使用无符号短整型的应用程序，则可以通过更改类型大小来定制它，将unsigned long替换为unsigned short。我不确定问题是否来自某种嵌入式应用程序，使用廉价微控制器或单板计算机等。 - Richard Chambers

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

如果你有想要影响的所有位的掩码，那么简单地使用x ^ mask（将一个位与1异或会使其取反）即可实现。获取掩码并不困难：

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

这是针对32位的。如有需要，请使用更多（或更少）步骤。

该构造将最高位设置为所有较低位通过取已复制该位的所有位置，并将其OR到该块右侧的位中，如下所示：

任何位于最高位之右的置位位也会被复制，但它们不会干扰此过程，因为受它们影响的任何位都在最高置位之右，应该设置。

根据您所使用的机器，可能有更好的获取掩码的方法。以下是x64的一些选项。

使用shrx（Haswell+，可轻松修改以更具可移植性）

mov rdx, -1
bsr rax, rax
cmovz rdx, rax
xor eax, 63
shrx rax, rdx, rax

使用shrx和lzcnt（Haswell+）

lzcnt rax, rax
sbb rdx, rdx
not rdx
shrx rax, rdx, rax

使用 lzcnt 和 bzhi（Haswell+）

lzcnt rax, rax
mov edx, 64
sub edx, eax
mov rax, -1
bzhi rax, rax, rdx

如果您能够反转位，大致像这样：

rbit r0, r0
neg r1, r0
or r0, r1
rbit r0, r0

这依赖于2的补码取反的特性，即所有在最右边设置位之左的位都被补码取反^[1]。一个数与它的补码取反进行按位或运算结果为1，所以-x | x会将最右边的1传递到其左侧的所有位。这正好是我们需要的相反操作，但使用快速位翻转时非常有用。

[1]：证明概要：-x = ~x + 1，考虑到最右边的1及其上方的位，在进行补码取反后将变成01*的形式，加1后可以恢复原始的10*，而上面的位仍然是补码取反的状态。