Mastering Algorithms with C

Implementation and Analysis of Bit Operations

Each bit operation works with a buffer of data defined as a pointer to an unsigned character. This pointer points to as many bytes as are required to represent the number of bits in the buffer. If the number of bits in the buffer is not a multiple of 8, some bits in the final byte are not used.

bit_ get

The bit_ get operation gets the state of a bit in a buffer (see Example 14.2). To do this, we determine in which byte the desired bit resides and then use a mask to get the specific bit from that byte. The bit set to 1 in mask determines which bit will be read from the byte. We use a loop to shift this bit into the proper position. We fetch the desired bit by indexing to the appropriate byte in bits and applying the mask.

The runtime complexity of bit_ get is O (1). This is because all of the steps in getting the state of a bit in a buffer run in a constant amount of time.

bit_set

The bit_set operation sets the state of a bit in a buffer (see Example 14.2). This operation works similarly to bit_ get, except that it uses the mask to set the state of the specified bit rather than to get it.

The runtime complexity of bit_set is O (1). This is because all of the steps in getting the state of a bit in a buffer run in a constant amount of time.

bit_xor

The bit_xor operation computes the bitwise XOR (exclusive OR) of two buffers, bits1 and bits2, and places the result in another buffer, bitsx (see Example 14.2). To do this, we compare the bit in ...