Chuck Allison is a regular columnist with CUJ and a software architect for the Family History Department of the Church of Jesus Christ of Latter Day Saints Church Headquarters in Salt Lake City. He has a B.S. and M.S. in mathematics, has been programming since 1975, and has been teaching and developing in C since 1984. His current interest is object-oriented technology and education. He is a member of X3J16, the ANSI C++ Standards Committee. Chuck can be reached on the Internet at allison@decus.org, or at (801)240-4510.
The ability to manipulate the individual bits of an integer is essential in systems programming. In the MS-DOS file system, for example, each disk file has an associated attribute byte. You can delete-protect a file or even omit it from directory listings, depending on which attribute bits you set. Before the days of C, most programmers had to resort to assembly language to manipulate bits. Nowadays, with bitwise operators and the host system interface that most compilers provide, there is almost nothing that you cannot do with your operating system from within a C program. In this article I'll review common bit-twiddling techniques and extend them with a couple of useful abstract data types.
Bitwise Operators
There are six bitwise operators in C (see Table 1) . As the program in Listing 1 illustrates, the bitwise-OR operator sets a bit in the result if either one of the corresponding operand bits is "set" (has a value of 1). For example:
01010101 (== 0x55) | 11110000 (== 0xf0) ------------- = 11110101 (== 0xf5)The bitwise-AND operator sets only those bits whose corresponding operand bits are both set:
01010101 & 11110000 ------------- = 01010000 (== 0x50)The bitwise-EXCLUSIVE-OR operator sets those bits when one or the other (but not both) of the original operand bits is set:
01010101 ^ 11110000 ------------- = 10100101 (== 0xa5)The bitwise-NOT operator "flips" each bit by making each 1 a 0, and vice-versa. The cast to unsigned char in Listing 1 is necessary because Standard-conforming compilers always promote chars to ints before applying bitwise operations. Without the cast the output would be:
~a == FFAAsince printf never truncates significant values in numbers, and ints on my machine are two bytes wide.The shift operators shift all bits left or right by the number of positions specified in the right operand. Bits that "fall off the end" are lost. The left-shift operator sets vacated bits to zero. When shifting signed integers to the right, some machines zero-fill while others replicate the sign bit. It is common practice, therefore, to declare integers unsigned, which will always be zero-filled when you shift them to the right.
Accessing Individual Bits
Quite often you need to set, reset, or test individual bits. If not too many bits are involved, you might consider using bitfield structures. For example, suppose you are only interested in bits 4 and 5 of an integer. Logically, bits are numbered right-to-left, starting from 0. Each bit number represents a power of 2, signifying the weight of each digit in a number's binary representation. For example, bit 0 represents 20, bit 1 represents 21, bit 2 represents 22, and so on. On a little-endian machine, the following structure would typically be suitable:
struct bits4_5 { unsigned : 4; /* Skip bits 0-> 3 */ unsigned bit4 : 1; unsigned bit5 : 1; };A big-endian architecture typically calls for
struct bits4_5 { unsigned : 10; /* Skip bits 15 -> 6 */ unsigned bit5 : 1; unsigned bit4 : 1; };You can then process the bits via the named variables:
unsigned x; struct bits4_5 *xp = (struct bits4_5 *) &x; xp->bit4 = 0; xp->bit5 = 1; f(xp); /* May modify the bits */ if (xp->bi t4) . . .This technique is somewhat unattractive not only because it isn't very portable, but also because it is cumbersome with a large number of bits. The preferred method to manipulate arbitrary, individual bits is via the bitwise operators. For example, to set the ith bit of an integer, form a mask with a 1 in the ith bit position and zeroes elsewhere (I'll call it the "1-mask"), then bitwise-OR it into the number:
x | = (1u << i)To turn a bit off, form the complement of the above mask (the "0-mask") and bitwise-AND it in:
x &= ~(1u << i)The program in Listing 2 sets all the bits of an integer in turn, right-to-left (logically), and resets them in the same order. The quantity CHAR_BIT, from limits.h, is the number of bits in a byte.To toggle a bit, exclusive-OR the 1-mask into the number:
x ^= (1u << i)To see whether or not a bit is set, bitwise-AND the integer with the same mask:
x & (1u << i)This expression evaluates to 0 if the bit is not set, or non-zero (2 to the ith power, in particular) if it is. The following useful idiom yields a 0 or 1 only:
!!(x & (1u << i))in case you want to use the result as an index into an array.The header file in Listing 3 defines macros for non-destructive versions of these operations, and declares some useful functions. The function implementations in Listing 4 use the nbits macro to compute the size of an unsigned int in bits. The function fputb prints an unsigned integer in binary form with bit-0 rightmost and with leading zeroes if necessary. fgetb reads a string of bit characters and converts it into an unsigned. The curious statement
sprintf(format," %%%d [01]", nb);builds a scan format string that skips whitespace and then reads up to nb 1s and 0s, or reads until it scans a non-bit character. You might think that you could avoid the sprintf by using a variable-width format descriptor in the scan, such as:
fscanf(f," %*[01] ",nb,buf);Unfortunately, variable-width substitution doesn't work with scansets. (If this is Greek to you, see October 1992's Code Capsule, "Text Processing I".)The count function computes the number of 1-bits in a number by right-shifting one bit at a time and testing bit 0. The test program in Listing 5 illustrates these functions.
Large Bitsets
What if you need more bits than an integer holds? For example, suppose that you must create a "picklist" user interface object. A picklist is a scrollable, pop-up listbox that allows the user to choose multiple entries. The number of entries can easily exceed the number of bits in a long integer. The most efficient way to track the state of each entry is to associate a bitset with the picklist — if the user highlights the ith entry, then you set the ith bit.
You can of course use an array of unsigneds to hold the bits you need:
If you need n bits, then you need N = ceil (n / BLKSIZ) array elements, where BLKSIZ is the number of bits in an unsigned (or whatever integral type you derive the array from). If n is not a multiple of BLKSIZ, then there will be unused bits in the zeroth block (represented by XX in the preceding figure). Now, accessing a particular bit reduces to finding the particular block it resides in, and computing the offset for the mask to apply to that block. To find the right block, notice the following pattern:
bits in this range are in this block b/BLKSIZ --------------------------------------------------- [0 , BLKSIZ-1] N-1 0 [BLKSIZ , 2*BLKSIZ-1] N-2 1 . . . . . . . . . [(N-1)*BLKSIZ , n-1] 0 N-1If b is the bit number in question, then
B + b/BLKSIZ == N-1where B is the block we are after. Therefore,
B = N-1 - b/BLKSIZThe offset of bit b within block B is simply
offset = b % BLKSIZIf bits is the array name, then you can process the Bth bit with these expressions:
bits[B] |= (1u << offset); /* set */ bits[B] &= ~(1u << offset); /* reset */ bits[B] ^= (1u << offset); /* toggle */ !!(bits[B] & (1u << offset)); /* test */The header file in Listing 6 presents an interface for processing arbitrarily large bitsets. In addition to the functions already discussed, it adds conversions to and from unsigned, in case you are working only with word-sized bitsets and want to interface with your host environment. The statement
typedef struct bits Bits;declares struct bits as an incomplete type with synonym Bits. The definition of the structure is in the implementation file. (See Listing 7 — If incomplete types are Greek to you, see last month's installment.) If you want to use another integral type for the base array, just substitute it for unsigned int in line 11 of bits. c.A Bits object consists of the number of bits allowed, the array of integers, the number of elements in the array, and a mask to reset the unused bits to zero that have inadvertently been set by operations on other bits. The test program in Listing 8 shows how you might use a Bits object in an application.
Bit Strings
The storage scheme in a Bits object puts bit 0 last in the array, so bits are numbered right-to-left, just like they are in single integers. In situations where there is no numerical application of bitsets, like the picklist example above, it might seem more natural to number bits from left to right, like a string. It is trivial to modify bits.c to make this change in orientation. The orientation is represented as:
The block for the bth bit is now
B = b / BLKSIZand the offset is calculated from the left instead of the right of the block:
offset = BLKSIZ - b%BLKSIZ - 1Listing 9 and Listing 10 summarize the changes required to transform the header file and implementation respectively from a bitset into a bit string. The test program is in Listing 11.
Stay Tuned
There are a number of features we could and should add to these objects. It would be convenient to provide bitwise operations that apply to entire objects, for example
Bits *bp1, *bp2, *bp3; /* . . . */ bits_and(bp3,bp1,bp2); bits_shift_left(bp3,4); /* . . . */It would also seem natural to allow bit strings to grow and shrink, just like strings. Before we get too carried away, however, it's time to consider moving to C++. In C++, we can overload operators so that the above excerpt looks like:
Bits bp1, bp2; // . . . Bits bp3 = bp1 & bp2; bp3 <<= 4;The next two installments will cover the two bitset classes that were voted into the standard C++ library in March, 1993 in Portland.
Table 1 Bitwise operators
Operator Meaning ------------------------------ & bitwise AND | bitwise OR ^ bitwise EXCLUSIVE-OR ~ bitwise complement << shift left >> shift right
Listing 1 Illustrates bitwise operators
/* bit1.c */ #include <stdio.h> main() { unsigned char a = 0x55; unsigned char b = 0xf0; printf("a | b == %02X\n",a | b); printf("a & b == %02X\n",a & b); printf("a ^ b == %02X\n",a ^ b); printf("~a == %02X\n",(unsigned char)~a); printf("a << 1 == %02X\n",a << 1); printf("b >> 6 == %02X\n",b >> 6); return 0; } /* Output: a | b == F5 a & b == 50 a ^ b == A5 ~a == AA a << 1 == AA b >> 6 == 03 */ /* End of File */
Listing 2 Sets and resets individual bits
/* bit1.c: Set and reset individual bits */ #include <stdio.h> #include <limits.h> #define WORD unsigned int #define NBYTES sizeof(WORD) #define NBITS (NBYTES * CHAR_BIT) #define NXDIGITS (NBYTES * 2) main() { unsigned n = 0; int i; /* Set each bit in turn */ for (i = 0; i < NBITS; ++i) { n |= (1u << i); printf("%0*X\n",NXDIGITS,n); } /* Now turn them off */ for (i = 0; i < NBITS; ++i) { n &= ~(1u << i); printf("%0*X\n",NXDIGITS,n); } return 0; } /* Output 0001 0003 0007 000F 001F 003F 007F 00FF 01FF 03FF 07FF 0FFF 1FFF 3FFF 7FFF FFFF FFFE FFFC FFF8 FFF0 FFE0 FFC0 FF80 FF00 FE00 FC00 F800 F000 E000 C000 8000 0000 */ /* End of File */
Listing 3 Declarations for bit access functions
/* bit.h: Bitwise functions for unsigned ints */ #ifndef BIT_H #define BIT_H #include <stdio.h> #include <limits.h> #define mask1(i) (1u << i) #define mask0(i) ~(1u << i) #define set(n,i) ((n) | mask1(i)) #define reset(n,i) ((n) & mask0(i)) #define toggle(n,i) ((n) ^ mask1(i)) #define test(n,i) !!((n) & mask1(i)) #define nbits(x) (sizeof(x) * CHAR_BIT) unsigned fputb(unsigned, FILE *); unsigned fgetb(FILE *); unsigned count(unsigned); #endif /* End of File */
Listing 4 Implementation file for bit.h
/* bit.c: Bit operations for unsigned ints */ #include <stdio.h> #include <limits.h> #include <stdlib.h> #include <string.h> #include "bit.h" unsigned fputb(unsigned n, FILE *f) { int i; size_t nb = nbits(n); /* Print the binary form of a number */ for (i = 0; i < nb; ++i) fprintf(f,"%d",test(n,nb-1-i)); return n; } unsigned fgetb(FILE *f) { unsigned n = 0; size_t nb = nbits(n); size_t slen; char *buf = malloc(nb+1); char format[9]; int i; if (buf == NULL) return 0; /* Build read format (e.g., " %16[01]") */ sprintf(format," %%%d[01]",nb); if (fscanf(f,format,buf) != 1) return 0; /* Set corresponding bits in n */ slen = strlen(buf); for (i = 0; i < slen; ++i) if (buf[slen-1-i] == '1') n = set(n,i); free(buf); return n; } unsigned count(unsigned n) { unsigned sum = 0; while (n) { if (n & 1u) ++sum; n >>= 1; } return sum; } /* End of File */
Listing 5 Illustrates the bit access functions from bit.h
/* tbit.c: Use bit operations from bit.h */ #include <stdio.h> #include "bit.h" main() { int i; unsigned n = 0; size_t nb = nbits(n); /* Set the even bits */ for (i = 0; i < nb; i += 2) n = set(n,i); printf("n == %04X (",n); fputb(n,stdout); printf("), count == %d\n",count(n)); /* Toggle the upper half */ for (i = nb/2; i < nb; ++i) n = toggle(n,i); printf("n == %04X (",n); fputb(n,stdout); printf("), count == %d\n",count(n)); /* Reset the lower half */ for (i = 0; i < nb/2; ++i) n = reset(n,i); printf("n == %04X (",n); fputb(n,stdout); printf("), count == %d\n",count(n)); /* Read a bit string */ fputs("Enter a bit string: ",stderr); n = fgetb(stdin); printf("n == %04X (",n); fputb(n,stdout); printf("), count == %d\n",count(n)); return 0; } /* Sample Execution: n == 5555 (0101010101010101), count == 8 n == AA55 (1010101001010101), count == 8 n == AA00 (1010101000000000), count == 4 Enter a bit string: 101001000100001 n == 5221 (0101001000100001), count == 5 /* /* End of File */
Listing 6 Bits object interface
/* bits.h: Large bit sets */ #ifndef BITS_H #define BITS_H #include <stdio.h> typedef struct bits Bits; Bits * bits_create(size_t nbits); unsigned bits_to_uint(Bits *); Bits * bits_from_uint(Bits *, unsigned); Bits * bits_set(Bits *, size_t bit); Bits * bits_set_all(Bits *); Bits * bits_reset(Bits *, size_t bit); Bits * bits_reset_all(Bits *); Bits * bits_toggle(Bits *, size_t bit); Bits * bits_toggle_all(Bits *); int bits_test(Bits *, size_t bit); int bits_any(Bits *); size_t bits_count(Bits *); Bits * bits_put(Bits *, FILE *); Bits * bits_get(Bits *, FILE *); void bits_destroy(Bits *); #endif /* End of File */
Listing 7 Bits object implementation
/* bits.c */ #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <string.h> #include <assert.h> #include "bits.h" /* Pick the base integral type */ typedef unsigned char Block; /* Some implementation specifics */ #define BLKSIZ (CHAR_BIT * sizeof(Block)) #define offset(b) (b % BLKSIZ) #define mask1(b) ((Block)1 << offset(b)) #define mask0(b) ~((Block)1 << offset(b)) /* Data Structure */ typedef struct bits { size_t nbits_; /* The # of bits */ Block *bits_; /* The base array */ size_t nblks_; /* The # of blocks in base array */ Block clean_mask_; /* To mask-off unused bits */ } Bits; /* Private functions */ static size_t word_(Bits* bp, size_t bit) { return bp->nblks_- 1 - bit/BLKSIZ; } static void set_(Bits *bp, size_t b) { bp->bits_[word_(bp,b)] |= mask1(b); } static void reset_(Bits *bp, size_t b) { bp->bits_[word_(bp,b)] &= mask0(b); } static void toggle_(Bits *bp, size_t b) { bp->bits_[word_(bp, b)] ^= mask1(b); } static int test_(Bits *bp,size_t b) { return !!(bp->bits_[word_(bp,b)] & mask1(b)); } static size_t count_block_(Block n) { size_t sum = 0; while (n) { if (n & (Block)1) ++sum; n >>= 1; } return sum; } static void cleanup_(Bits *bp) { if (bp->nbits_% BLKSIZ) bp->bits_[0] &= bp->clean_mask_; } /* Implementation of public interface */ Bits * bits_create(size_t nbits) { Bits *bp = malloc(sizeof(Bits)); size_t nbytes; if (bp == NULL) return NULL; /* Allocate base array */ bp->nblks_ = (nbits + BLKSIZ - 1) / BLKSIZ; nbytes = bp->nblks_ * sizeof(Block); bp->bits_ = malloc(nbytes); if (bp->bits_ == NULL) { free(bp); return NULL; } memset(bp->bits_,'\0',nbytes); bp->nbits_ = nbits; bp->clean_mask_ = ~(Block)0 >> (bp->nblks_*BLKSIZ - nbits); return bp; } unsigned bits_to_uint(Bits *bp) { size_t nblks = sizeof(unsigned) / sizeof(Block); if (nblks > 1) { int i; unsigned n = bp->bits_[bp->nblks_ - nblks]; /* Collect low-order sub-blocks into an unsigned */ if (nblks > bp->nblks_) nblks = bp->nblks_; while (--nblks) n = (n << BLKSIZ) | bp->bits_[bp->nblks_ - nblks]; return n; } else return (unsigned) bp->bits_[bp->nblks_ - 1]; } Bits * bits_from_uint(Bits *bp, unsigned n) { size_t nblks = sizeof(unsigned) / sizeof(Block); assert(bp); memset(bp->bits_, '\0', bp->nblks_ * sizeof(Block)); if (nblks > 1) { int i; if (nblks > bp->nblks_) nblks = bp->nblks_; for (i = 1; i <- nblks; ++i) { bp->bits [bp->nblks_ - i] = (Block) n; n >>= BLKSIZ; } } else bp->bits_[bp->nblks_- 1] = n; return bp; } Bits * bits_set(Bits *bp, size_t bit) { assert(bp && (bit < bp->nbits_)); set_(bp,bit); return bp; } Bits * bits_set_all(Bits *bp) { assert(bp); memset(bp->bits_,~Ou,bp->nblks_*sizeof(Block)); cleanup_(bp); return bp; } Bits * bits_reset(Bits *bp, size_t bit) { assert(bp && (bit < bp->nbits_)); reset_(bp,bit); return bp; } Bits * bits_reset_all(Bits *bp) { assert(bp); memset(bp->bits_,'\0',bp->nblks_*sizeof(Block)); return bp; } Bits * bits_toggle(Bits *bp, size_t bit) { assert(bp && (bit < bp->nbits_)); toggle_(bp,bit); return bp; } Bits * bits_toggle_all(Bits *bp) { size_t nw; assert(bp); nw = bp->nblks_; while (nw--) bp->bits_[nw] = ~bp->bits_[nw]; cleanup_(bp); return bp; } int bits_test(Bits *bp,size_t bit) { assert(bp && (bit < bp->nbits_)); return test_(bp,bit); } int bits_any(Bits *bp) { int i; assert(bp); for (i = 0; i < bp->nblks_; ++i) if (bp->bits_[i]) return 1; return 0; } size_t bits_count(Bits *bp) { int i; size_t sum; assert(bp); for (i = 0, sum = 0; i < bp->nblks_; ++i) sum += count_block_(bp->bits_[i]); return sum; } Bits * bits_put(Bits *bp, FILE *f) { int i; assert(bp); for (i = 0; i < bp->nbits_; ++i) fprintf(f,"%d",bits_test(bp,bp->nbits_-1-i)); return bp; } Bits * bits_get(Bits *bp, FILE *f) { char *buf; char format[9]; /* Reset all bits */ assert(bp); bits_reset_all(bp); /* Allocate string buffer */ buf = malloc(bp->nbits_+1); if (buf == NULL) return 0; /* Build read format (e.g., " %16[01]") */ sprintf(format," %%%d[01]",bp->nbits_); if (fscanf(f,format,buf) == 1) { int i; size_t slen = strlen(buf); /* Set corresponding bits in bitset */ for (i = 0; i < slen; ++i) if (buf[slen-1-i] == '1') bits_set(bp,i); } free(buf); return bp; } void bits_destroy(Bits *bp) { assert(bp); free(bp->bits_); free(bp); } /* End of File */
Listing 8 Illustrates bits objects
/* tbits.c: Test the Bits Interface */ #include <stdio.h> #include <assert.h> #include "bits.h" #define NBITS 24 main() { int i; unsigned n; Bits *bp = bits_create(NBITS); assert(bp); /* Set the even bits */ for (i = 0; i < NBITS; i += 2) bits_set(bp,i); bits_put(bp,stdout); printf(" (%d)\n",bits_count(bp)); /* Toggle the upper half */ for (i = NBITS/2; i < NBITS; ++i) bits_toggle(bp,i); bits_put(bp,stdout); printf(" (%d)\n",bits_count(bp)); /* Reset the lower half */ for (i = 0; i < NBITS/2; ++i) bits_reset(bp,i); bits_put(bp,stdout); printf(" (%d)\n",bits_count(bp)); /* Read a bit string */ fputs("Enter a bit string: ",stderr); bits_put(bits_get(bp,stdin),stdout); printf(" (%d)\n",bits_count(bp)); /* Convert to and from unsigned */ n = bits_to_uint(bp); printf("n: %u\n",n); bp = bits_from_uint(bp,n); bits_put(bp,stdout); printf(" (%d)\n",bits_count(bp)); /* Test any() and test() */ printf("any? %d\n",bits_any(bp)); printf("test(0)? %d\n",bits_test(bp,0)); /* Test toggle and reset */ bits_put(bits_toggle_all(bp),stdout); printf(" (%d)\n",bits_count(bp)); bits_put(bits_reset_all(bp),stdout); printf(" (%d)\n",bits_count(bp)); bits_put(bits_set_all(bp),stdout); printf(" (%d)\n",bits_count(bp)); return 0; } /* Sample Execution: 010101010101010101010101 (12) 101010101010010101010101 (12) 101010101010000000000000 (6) Enter a bit string: 101001000100001 000000000101001000100001 (5) n: 21025 000000000101001000100001 (5) any? 1 test(0)? 1 111111111010110111011110 (19) 000000000000000000000000 (0) 111111111111111111111111 (24) /* End of File */
Listing 9 Edits to transform bits.h into bitstr.h
1) Change the string "bits" to "bitstr" everywhere (preserving case). 2) Remove the declarations bits_to_uint() and bits_from_uint().
Listing 10 Edits to transform bits.c into bitstr.c
1) Change the string "bits" to "bitstr" everywhere (preserving case). 2) Change line 15 from #define offset(b) (b % BLKSIZ) to #define offset(b) (BLKSIZ - (b % BLKSIZ) - 1) 3) Add the macro definition #define word(b) (b / BLKSIZ) 4) Remove the function static size_t word_(...). 5) In function static void cleanup_(...), change the line bp->bits_[0] &= bp->clean_mask_; to bp->bits_[bp->nblks_ - 1] &= bp->clean_mask_; 6) Change the right shift operator in the second to last line of function bitstr_create to a left shift. 7) In function bitstr_put, change the line fprintf(f, "%d",bitstr_test(bp,bp->nbits_-1-i)); to fprintf(f,"%d",bitstr_test(bp,i)); 8) In function bitstr_get, change the line if (buf[slen-1-i] == '1') to if(buf[i] == '1')
Listing 11 Illustrate bitstr objects
/* tbitstr.c: Test the Bitstr Interface */ #include <stdio.h> #include <assert.h> #include "bitstr.h" #define NBITS 24 main() { int i; unsigned n; Bitstr *bp = bitstr_create(NBITS); assert(bp); /*Set the even bits */ for (i = 0; i <NBITS; i += 2) bitstr_set(bp,i); bitstr_put(bp,stdout); printf(" (%d)\n",bitstr_count(bp)); /*Toggle the upper half */ for (i = NBITS/2; i <NBITS; ++i) bitstr_toggle(bp,i); bitstr_put(bp,stdout); printf(" (%d)\n",bitstr_count(bp)); /*Reset the lower half*/ for (i = 0; i <NBITS/2; i++) bitstr_reset(bp,i); bitstr_put(bp,stdout); printf(" (%d)\n", bitstr_count(bp)); /* Read a bit string */ fputs("Enter a bit string: ",stderr); bitstr_put(bitstr_get(bp,stdin),stdout); printf(" (%d)\n",bitstr_count(bp)); printf("any? (%d\n",bitstr_any(bp)); printf("test(0)? %d\n",bitstr_test(bp,0)); bitstr_put(bitstr_toggle_all(bp),stdout); printf(" (%d)\n",bitstr_count(bp)); bitstr_put(bitstr_reset_all(bp),stdout); printf(" (%d)\n",bitstr_count(bp)); bitstr_put(bitstr_set_all(bp),stdout); printf(" (%d)\n",bitstr_count(bp)); return 0; } /* Sample Execution: 101010101010101010101010 (12) 101010101010010101010101 (12) 000000000000010101010101 (6) Enter a bit string: 101001000100001 101001000100001000000000 (5) any? 1 test(0)? 1 010110111011110111111111 (19) 000000000000000000000000 (0) 111111111111111111111111 (24) /* End of File */