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 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access