[FrontPage] [TitleIndex] [WordIndex]

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Sometimes it is convenient to consider a block of chars as really being a block of bits. This requires using C's bit operators to get at individual bits.

Here are some simple macros for extracting a particular bit from a char array, thought of as a large vector of bits. These assume that the bytes are stored in little-endian order, which means that the least significant bytes come first (see Endianness). This may produce odd results if you feed them a char * that has been converted from a larger integer type.

```   1 #define BITS_PER_BYTE (8)
2
3 /* extract the n-th bit of x */
4 #define GET_BIT(x, n) ((((x)[(n) / BITS_PER_BYTE]) & (0x1 << ((n) % BITS_PER_BYTE))) != 0)
5
6 /* set the n-th bit of x to 1 */
7 #define SET_BIT(x, n) ((x)[(n) / BITS_PER_BYTE]) |= (0x1 << ((n) % BITS_PER_BYTE))
8
9 /* set the n-th bit of x to 0 */
10 #define RESET_BIT(x, n) ((x)[(n) / BITS_PER_BYTE]) &= ~(0x1 << ((n) % BITS_PER_BYTE))
11
```

If you want to get multiple bits, use the right-shift operator to shift them over to the right end of the word and then mask with bitwise AND. For example:

```   1 #define BITS_PER_BYTE (8)
2
3 /* this rather nasty expression constructs an all-ones byte */
4 #define BYTE_MASK ((1 << BITS_PER_BYTE) - 1)
5
6 /* extract the n-th byte from a word */
7 #define GET_BYTE(x, n) (((x) >> BITS_PER_BYTE * (n)) & BYTE_MASK)
8
9 /* extract n bits starting at position i from x */
10 #define GET_BITS(x, i, j) (((x) >> (i)) & ((1 << n) - 1))
11
12 /* another definition of GET_BIT */
13 #define GET_BIT2(x, n) GET_BITS(x, n, 1)
14
```

Many much more sophisticated techniques for doing bit-fiddling can be found at http://www.jjj.de/bitwizardry/bitwizardrypage.html.

2014-06-17 11:57