一个算法的说明设置，清除和测试单个位 [英] Explanation of an algorithm to set, clear and test a single bit

问题描述

嘿嘿，编程珍珠的书，有一个设置，清除和测试位给定索引的int数组源$ C ​​$ C，它实际上是一组重presentation。

Hey, in the Programming Pearls book, there is a source code for setting, clearing and testing a bit of the given index in an array of ints that is actually a set representation.

在code是以下内容：

The code is the following:

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1+ N/BITSPERWORD];

void set(int i)
{
    a[i>>SHIFT] |= (1<<(i & MASK));
}

void clr(int i)
{
    a[i>>SHIFT] &= ~(1<<(i & MASK));
}

int test(int i)
{
    a[i>>SHIFT] & (1<<(i & MASK));
}

有人能解释我的SHIFT和掩码定义的原因是什么？和他们有什么目的，在code？

Could somebody explain me the reason of the SHIFT and the MASK defines? And what are their purposes in the code?

我已经阅读过相关的<一的previous href=\"http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c\">question.

推荐答案

VonC发表的关于一般位掩码一个很好的答案。这里的一些信息更具体到code您发布。

VonC posted a good answer about bitmasks in general. Here's some information that's more specific to the code you posted.

由于重新presenting位整数，我们制定出哪个成员的数组认为位。那就是：在位0至31直播 A [0] ，位在 32〜63活一[1] 等所有这一切 I＆GT;＆GT;移确实是 I / 32 。这工作了哪些成员 A 位居住在。随着优化编译器，这些都可能是等价的。

Given an integer representing a bit, we work out which member of the array holds that bit. That is: Bits 0 to 31 live in a[0], bits 32 to 63 live in a[1], etc. All that i>>SHIFT does is i / 32. This works out which member of a the bit lives in. With an optimising compiler, these are probably equivalent.

显然，我们现在已经发现了其中 A 是位标志，住在成员，我们需要确保我们设置正确的位在整数。这是 1 LT;＆LT;我一样。然而，我们需要确保我们不要试图访问第33位的32位整数，所以移位操作是通过使用 1 LT约束;＆LT; （I和0x1F的）。这里的神奇的是， 0x1F的 31，所以我们永远不会离开移位再由 psented $ P $ I 超过31的地方（否则它应该去的的下一个成员 A ）。

Obviously, now we've found out which member of a that bitflag lives in, we need to ensure that we set the correct bit in that integer. This is what 1 << i does. However, we need to ensure that we don't try to access the 33rd bit in a 32-bit integer, so the shift operation is constrained by using 1 << (i & 0x1F). The magic here is that 0x1F is 31, so we'll never left-shift the bit represented by i more than 31 places (otherwise it should have gone in the next member of a).

这篇关于一个算法的说明设置，清除和测试单个位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！