Mastering Algorithms With C - Kyle Loudon [158]
unsigned char *bitsx, int size);
Return Value
None.
Description
Computes the bitwise XOR (exclusive OR) of the two buffers bits1 and bits2, each containing size bits, and returns the result in bitsx. The bitwise XOR of two binary operands yields in each position i of the result where in position i of the operands the bits are the same, and 1 in each position where the bits are different. For example, 11010 ⊕ 01011 = 10001 (⊕ denotes XOR). It is the responsibility of the caller to manage the storage required by bitsx.
Complexity
O (β), where β is the number of bits in each buffer.
Name
bit_rot_left
Synopsis
void bit_rot_left(unsigned char *bits, int size, int count);
Return Value
None.
Description
Rotates the buffer bits, containing size bits, to the left count bits. After the operation, the leftmost count bits become the count rightmost bits in the buffer, and all other bits are shifted accordingly.
Complexity
O (n β), where n is the number of bits rotated to the left and β is the number of bits in the buffer.
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 position i of bits1 with the bit in position i of bits2. If the bits are the same, we set the bit in position i of bitsx to 0; otherwise, we set the bit in position i of bitsx to 1. This process continues for as many bits are in each buffer, as specified by size.
The runtime complexity of bit_xor is O (β), where β is the number of bits in each buffer. This is because the loop in the operation iterates once for each bit.
bit_rot_left
The bit_rot_left operation rotates a buffer a specified number of bits to the left (see Example 14.2). We begin by saving the leftmost bit of the leftmost byte and then shifting each byte one bit to the left. As we shift each byte, we set the rightmost bit of the preceding byte to the bit shifted off the left of the current byte. Once we have shifted the last byte, we set its rightmost bit to the bit shifted off the first byte. This process is repeated as many times as the number of bits to be rotated.
The runtime complexity of bit_rot_left is O (n β), where n is the number of bits rotated to the left and β is the number of bits in the buffer. This is because for each rotation, (β/8) + 1 shifts are performed to the left.
Example 14.2. Implementation of Bit Operations
/*****************************************************************************
* *
* --------------------------------- bit.c -------------------------------- *
* *
*****************************************************************************/
#include #include