代码之家 › 专栏 › 技术社区 › Areg Sarvazyan

从无符号int中提取位的函数

bit-shift bit bit-manipulation c

0

Areg Sarvazyan · 技术社区 · 8 年前

编写一个名为 bitpat_get() 提取一组指定的位。让它包含三个参数:第一个和 unsigned int ,第二个是整数起始位号,第三个是位计数。使用位编号开始的约定 0 使用最左边的位,从第一个参数中提取指定数量的位并返回结果。所以这个电话

bitpat_get(x, 0, 3)

从中提取最左边的三个位。电话

bitpat_get(x, 3, 5)

从左侧第四位开始提取五位。

我真的不知道作者所说的提取位是什么意思,所以我几乎可以肯定我的代码是错误的,它返回的任何内容都不是预期的返回值。不过,我还是会发布它:

#include <stdio.h>

unsigned int bitpat_get(unsigned int from, int start, int n);

int main(void)
{
    unsigned int x = 0xe1f4;

    printf("%x\n", bitpat_get(x, 0, 3));
    printf("%x\n", bitpat_get(x, 3, 5));
}

unsigned int bitpat_get(unsigned int from, int start, int n)
{
    unsigned int result = from;
    int bits;

    for (bits = 0; (from >> bits) != 0; ++bits)
        continue;

    unsigned int mask = (((1U << n) - 1) << (bits - n - start));

    result = from ^ mask;

    return result;
}

输出:

1f4
fef4

1 回复 | 直到 6 年前

1

2

paxdiablo 8 年前

我真的不知道作者所说的提取比特是什么意思。

让我们先解决这个问题。假设有一个16位无符号整数,则位位置为:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

所以表达式 bitpat_get(x, 0, 3) 应该给出从偏移量0开始的三位,或者 abc . 同样地, bitpat_get(x, 3, 5) 会给你偏移量3的5位,或者 defgh 。

这应该足以懂你需要做什么。

在你需要的方面做要实现这一点,需要两步操作。第一个是将位实际右移 ^(a) 这样你所需要的人就处于最正确的位置。这取决于三条信息:

的位宽度 unsigned int ;
要提取的偏移量;和
要提取的位数。

移动距离为 bitWidth - offset - bitsNeeded . 对于你的第一个病例 16 - 0 - 3 = 13 您可以看到,将位右移13将把所需的位放在最右边的部分:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|0|0|a|b|c|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

第二种情况下,右移 16 - 3 - 5 = 8 为您提供:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|a|b|c|d|e|f|g|h|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

第二步是屏蔽掉左边实际上不需要的部分。我们先做第二种情况,因为这有实际效果。

掩码基本上是右侧一个位的序列,可以从零和开始获得左边为您需要的每个位位置移动一个位。对于需要5位的情况,序列将是二进制的 0 ,则, 1 ,则, 11 ,则, 111 ,则, 1111 和 11111 . 按位并将其与值相加将得到:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|a|b|c|d|e|f|g|h| <- value
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1| <- "and" with
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|d|e|f|g|h| <- gives
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

对于第一种需要三位的情况,掩码将是二进制的 111 因此不会对原始值产生影响,因为所有最左边的位都是已经零

请注意,您不需要在循环中执行此操作,因为正如代码所示,您可以使用单个表达式进行计算 2 ⁿ - 1 :

unsigned mask = (1U << n) - 1U;

就您发布的代码而言,我发现了一些问题。

首先,我认为 for..continue 第节旨在找出 无符号整型 ,基于您以后对该值的使用。但是,您根据传入的值计算它,这是不正确的。你怎么了应该它的基础是位模式,其中最左边的位是一位。

换言之,如果传入的值为3(二进制),请考虑当前循环将执行的操作 11 )-位宽度将计算为2,因为仅在两次移位后,最终将得到一个零值。因此,更好的方法是:

unsigned testVal = ~0U; // all one bits
for (bits = 0; testVal != 0; ++bits, testVal = testVal >> 1)
    ;

其次是你的面具计算。您的代码被设置为提取到位的位,这意味着您只需将它们周围的所有其他位设置为零。最好将它们移到右侧进行提取 ^(a) 。

第三,你应该意识到 ^ 是异或如果与所有一位的掩码一起使用,则将倒转而不是按原样提取它们。你要找的接线员是 & 。

例如,使用xor运算符 bitpat_get(21, 11, 5) 将提供:

                     1 1 1 1 1 1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|1|0|1|0|1| <- value (21)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1| <- "xor" with
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|0|0|0|1|0|1|0| <- `01010` (10): NOT the correct `10101`
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

话虽如此,我还是将函数编写为:

unsigned bitpat_get(unsigned from, unsigned start, unsigned count) {
    // Only need calculate this once, first time it's called.

    static unsigned bitWidth = 0;
    if (bitWidth == 0) {
        unsigned testVal = ~0U;
        while (testVal != 0) {
            bitWidth++;
            testVal = testVal >> 1;
        }
    }

    // Get the value you need to shift by.

    unsigned shiftCount = bitWidth - start - count;

    // Use this line if in-place bits needed.
    // unsigned mask = ((1U << count) - 1U) << shiftCount;

    // Or use these two lines if you need it on the right.
    from = from >> shiftCount;
    unsigned mask = (1U << count) - 1U;

    // Mask and return the bits.

    unsigned result = from & mask;

    return result;
}

唯一棘手的是使用静态 bitWidth 所以它只需要计算一次。这只是为了在后续通话中加快速度而进行的优化。如果您不想这样做(例如,如果您不熟悉这些概念,或者如果有可能第一次从多个线程同时调用此函数,从而导致数据争用),只需将其替换为:

unsigned bitWidth = 0;
unsigned testVal = ~0U;
while (testVal != 0) {
    bitWidth++;
    testVal = testVal >> 1;
}

^(a) 这是基于经验。它是 可能的 你可能想让他们就位,但在我漫长且(偶尔)杰出的职业生涯中,我总是发现让他们在移位部分更有用。例如,如果位11-13是某种类型的整数值,则实际上将其移动到最右边的位给予您了解价值 0..7 而不是集合中的值 {0, 4, 8, ..., 28} 。

那个也许事实并非如此,因此如果您只需注释掉另一种情况,那么我提供的代码将涵盖这两种情况。