如何设置、清除和切换单个位

3120
如何设置、清除和切换一个位?

90
阅读此链接:http://graphics.stanford.edu/~seander/bithacks.html,当您掌握了它后,请阅读此链接:http://realtimecollisiondetection.net/blog/?p=78。 - ugasoft
22
您可能还想查看The Bit Twiddler, Bit Twiddling HacksThe Aggregate Magic Algorithms. 这些网站会对您有所帮助。 - anon
这引出了一个问题,即多个位的规范问题是什么。 - Peter Mortensen
27个回答

27

位域(bitfield)方法在嵌入式系统领域中有其他优点。您可以定义一个结构体,直接映射到特定硬件寄存器中的位。

struct HwRegister {
    unsigned int errorFlag:1;  // one-bit flag field
    unsigned int Mode:3;       // three-bit mode field
    unsigned int StatusCode:4;  // four-bit status code
};

struct HwRegister CR3342_AReg;

你需要注意位的排列顺序 - 我认为是从高位到低位,但这可能取决于实现。此外,请验证编译器如何处理跨越字节边界的字段。

然后,您可以像以前一样读取、写入、测试单个值。


4
关于位域(bit-fields)的大部分内容都是由实现定义的。即使您成功地找出了有关特定编译器如何实现它们的所有细节,使用它们在您的代码中肯定会使其不可移植。 - Lundin
1
@Lundin - 确实如此,但是嵌入式系统位操作(特别是在硬件寄存器中,这正是我的答案所涉及的)永远不会有用地可移植。 - Roddy
1
不一定是在完全不同的CPU之间移植,但你很可能希望它在编译器和不同项目之间具有可移植性。还有很多嵌入式的“位操作”,与硬件无关,例如数据协议的编码/解码。 - Lundin
如果您养成使用位域在嵌入式编程中的习惯,您会发现X86代码运行得更快,而且更精简。这不是在简单的基准测试中,在那里您需要整个机器来压倒基准测试,而是在真实的多任务环境中,在那里程序竞争资源。CISC的优势在于其最初的设计目标是弥补CPU比总线和慢速存储器更快的缺陷。 - user1899861
C还是C++?语言版本有什么要求(如果有的话)? - undefined

22

更普遍地讲,适用于任意大小的位图:

#define BITS 8
#define BIT_SET(  p, n) (p[(n)/BITS] |=  (0x80>>((n)%BITS)))
#define BIT_CLEAR(p, n) (p[(n)/BITS] &= ~(0x80>>((n)%BITS)))
#define BIT_ISSET(p, n) (p[(n)/BITS] &   (0x80>>((n)%BITS)))

4
CHAR_BIT已经在limits.h中定义了,您不需要自己添加BITS(实际上,这样做会使您的代码变得更糟)。 - M.M

22

检查任意类型的变量中任意位置的一个二进制位:

#define bit_test(x, y)  ( ( ((const char*)&(x))[(y)>>3] & 0x80 >> ((y)&0x07)) >> (7-((y)&0x07) ) )

使用示例:

int main(void)
{
    unsigned char arr[8] = { 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF };

    for (int ix = 0; ix < 64; ++ix)
        printf("bit %d is %d\n", ix, bit_test(arr, ix));

    return 0;
}

注: 这是为了快速(考虑到其灵活性)和无分支而设计的。 当使用Sun Studio 8编译时,它会产生高效的SPARC机器代码; 我还在amd64上使用MSVC++ 2008进行了测试。 可以创建类似的宏以设置和清除位。 与此处的许多其他解决方案相比,该解决方案的关键区别在于它适用于几乎任何类型变量中的任何位置。


17

这个程序用来将任何数据位从0变为1或从1变为0:

{
    unsigned int data = 0x000000F0;
    int bitpos = 4;
    int bitvalue = 1;
    unsigned int bit = data;
    bit = (bit>>bitpos)&0x00000001;
    int invbitvalue = 0x00000001&(~bitvalue);
    printf("%x\n",bit);

    if (bitvalue == 0)
    {
        if (bit == 0)
            printf("%x\n", data);
        else
        {
             data = (data^(invbitvalue<<bitpos));
             printf("%x\n", data);
        }
    }
    else
    {
        if (bit == 1)
            printf("elseif %x\n", data);
        else
        {
            data = (data|(bitvalue<<bitpos));
            printf("else %x\n", data);
        }
    }
}

这不是一个完整的程序,只是一个片段。 - Peter Mortensen
有什么样的示例输出? - Peter Mortensen
好的,OP已经离开了:「最后一次出现是在11年前」。 - Peter Mortensen
这个回答看起来像是一个虚假的回答,发表在问题提出后的三年半之后。它是否有任何价值? - Peter Mortensen

15

如果你要进行大量的位操作,你可能想使用掩码来使整个过程更快。以下函数非常快,并且仍然灵活(它们允许在任何大小的位图中进行位操作)。

const unsigned char TQuickByteMask[8] =
{
   0x01, 0x02, 0x04, 0x08,
   0x10, 0x20, 0x40, 0x80,
};


/** Set bit in any sized bit mask.
 *
 * @return    none
 *
 * @param     bit    - Bit number.
 * @param     bitmap - Pointer to bitmap.
 */
void TSetBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] |= TQuickByteMask[n];        // Set bit.
}


/** Reset bit in any sized mask.
 *
 * @return  None
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
void TResetBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] &= (~TQuickByteMask[n]);    // Reset bit.
}


/** Toggle bit in any sized bit mask.
 *
 * @return   none
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
void TToggleBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] ^= TQuickByteMask[n];        // Toggle bit.
}


/** Checks specified bit.
 *
 * @return  1 if bit set else 0.
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
short TIsBitSet( short bit, const unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;    // Index to byte.
    n = bit % 8;    // Specific bit in byte.

    // Test bit (logigal AND).
    if (bitmap[x] & TQuickByteMask[n])
        return 1;

    return 0;
}


/** Checks specified bit.
 *
 * @return  1 if bit reset else 0.
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
short TIsBitReset( short bit, const unsigned char *bitmap)
{
    return TIsBitSet(bit, bitmap) ^ 1;
}


/** Count number of bits set in a bitmap.
 *
 * @return   Number of bits set.
 *
 * @param    bitmap - Pointer to bitmap.
 * @param    size   - Bitmap size (in bits).
 *
 * @note    Not very efficient in terms of execution speed. If you are doing
 *        some computationally intense stuff you may need a more complex
 *        implementation which would be faster (especially for big bitmaps).
 *        See (http://graphics.stanford.edu/~seander/bithacks.html).
 */
int TCountBits( const unsigned char *bitmap, int size)
{
    int i, count = 0;

    for (i=0; i<size; i++)
        if (TIsBitSet(i, bitmap))
            count++;

    return count;
}

注意,要将16位整数中的第'n'位设置为1,需执行以下操作:

TSetBit( n, &my_int);

你需要确保位数在传递的位图范围内。请注意,在小端处理器中,字节、字、双字、四字等在内存中正确地映射到彼此(这也是小端处理器“比”大端处理器好的主要原因,噢,我感觉一场战火即将爆发……)。


3
不要为可以用单个运算符实现的函数使用表格。TQuickByteMask [n] 等同于 (1<<n)。此外,让您的参数变短是一个非常糟糕的想法。/ 和 % 实际上将是除法,而不是位移/按位与,因为带符号除以2的幂不能按位实现。您应该将参数类型设为 unsigned int! - R.. GitHub STOP HELPING ICE
1
这样做有什么意义呢?它只会让代码变得更慢、更难理解。我看不出任何优点。对于C程序员来说,1u << n 更易读,并且希望可以翻译成单个时钟周期CPU指令。另一方面,您的除法将被转换为大约10个时钟周期,甚至可能达到100个时钟周期,这取决于特定架构处理除法的差异程度。至于位图功能,最好使用查找表将每个位索引转换为字节索引,以优化速度。 - Lundin
2
关于大/小端,大端将整数和原始数据(例如字符串)以相同的方式映射:从左到右的msb到lsb贯穿整个位图。而小端将整数映射为从左到右的7-0、15-8、23-18、31-24,但原始数据仍然是从左到右的msb到lsb。所以小端如何更适合您的特定算法完全超出了我的理解,它似乎是相反的。 - Lundin
3
@R.. 如果您的平台无法高效移位,例如旧的微控制器,则表格可能非常有用,但当然,此时样本中的除法绝对是低效的。 - jeb

13
使用这个:
int ToggleNthBit ( unsigned char n, int num )
{
    if(num & (1 << n))
        num &= ~(1 << n);
    else
        num |= (1 << n);

    return num;
}

7
它使用了低效的分支。 - asdf
5
编译器的任务是生成最高效的二进制代码,程序员的工作就是编写清晰易懂的代码。 - M.M
4
这是对测试、设置和清除特定位的很好演示。但这种方法用于切换位是非常不好的。 - Ben Voigt

13
如果你想在Linux内核中使用C编程来执行所有这些操作,我建议使用Linux内核的标准API。
请参阅《第2章:基本C库函数》。
set_bit  Atomically set a bit in memory
clear_bit  Clears a bit in memory
change_bit  Toggle a bit in memory
test_and_set_bit  Set a bit and return its old value
test_and_clear_bit  Clear a bit and return its old value
test_and_change_bit  Change a bit and return its old value
test_bit  Determine whether a bit is set

注意:在这里,整个操作都在一个步骤中完成。因此,即使在SMP计算机上,这些操作也都是原子性的,并且对于保持处理器之间的一致性非常有用。

12

bitset答案的基础上进行扩展:

#include <iostream>
#include <bitset>
#include <string>

using namespace std;
int main() {
  bitset<8> byte(std::string("10010011");

  // Set Bit
  byte.set(3); // 10010111

  // Clear Bit
  byte.reset(2); // 10010101

  // Toggle Bit
  byte.flip(7); // 00010101

  cout << byte << endl;

  return 0;
}

12
Visual C 2010,以及可能还有许多其他编译器,都直接支持布尔运算。一个位有两个可能的值,就像一个布尔值一样,所以我们可以使用布尔值来代替,即使在这种表示中它们占用的内存空间比一个单独的位要多。这是有效的,甚至sizeof()操作符也能正常工作。
bool IsGph[256], IsNotGph[256];

// Initialize boolean array to detect printable characters
for(i=0; i<sizeof(IsGph); i++) {
    IsGph[i] = isgraph((unsigned char)i);
}

所以,针对你的问题,IsGph[i] =1或者IsGph[i] =0可以方便地设置和清除布尔值。
要查找不可打印字符:
// Initialize boolean array to detect UN-printable characters,
// then call function to toggle required bits true, while initializing a 2nd
// boolean array as the complement of the 1st.
for(i=0; i<sizeof(IsGph); i++) {
    if(IsGph[i]) {
        IsNotGph[i] = 0;
    } 
    else {
        IsNotGph[i] = 1;
    }
}

请注意,这段代码并没有什么“特别”的地方。它将位视为整数——从技术上讲,确实如此。一个只能容纳两个值的1位整数。
我曾经使用这种方法来查找重复的贷款记录,其中贷款号是ISAM键,使用六位数的贷款号作为位数组的索引。 这种方法非常快速,并且在八个月后证明了我们从中获取数据的大型机系统实际上存在故障。位数组的简单性使得对其正确性的信心非常高——相比于搜索方法等其他方法。

1
大多数编译器确实将std::bitset实现为位。 - galinette
3
@galinette,同意。头文件#include <bitset>在这方面是个好资源。 此外,当需要更改向量大小时,特殊类vector<bool>也很有用。 Nicolai M. Josuttis的《C++ STL第二版》分别详细介绍了它们的内容,分别在第650页和第281页。 C++11为std::bitset添加了一些新功能,其中对我特别感兴趣的是unordered容器中的哈希函数。 感谢您的提示! 我将删除我的脑抽评论。 网络上已经有足够多的垃圾了。 我不想再增加。 - user1899861
4
每个bool至少需要一个字节的存储空间。对于使用int来实现bool的C89设置,甚至可能需要4个字节的存储空间。 - M.M
@MattMcNabb,你是正确的。在C++中,实现布尔类型所需的int类型大小未由标准指定。我在一段时间前意识到这个答案是错误的,但决定将其保留在这里,因为人们显然发现它很有用。对于那些想要使用位的人来说,galinette的评论非常有帮助,我的位库也在这里...https://dev59.com/G3I95IYBdhLWcg3wyRI0#16534995 - user1899861
2
@RocketRoy:也许值得修改那句声称这是“位运算”的例子的句子。 - Ben Voigt

8
int set_nth_bit(int num, int n){    
    return (num | 1 << n);
}

int clear_nth_bit(int num, int n){    
    return (num & ~( 1 << n));
}

int toggle_nth_bit(int num, int n){    
    return num ^ (1 << n);
}

int check_nth_bit(int num, int n){    
    return num & (1 << n);
}

1
check_nth_bit 的返回类型可以是 bool - Xeverous
1
@Xeverous 是的,这取决于调用者的意图。 - Sazzad Hissain Khan

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接