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.
/***************************************************************************** * * * --------------------------------- bit.c -------------------------------- * * * *****************************************************************************/ #include <string.h> #include "bit.h" /***************************************************************************** * * * -------------------------------- bit_get ------------------------------- * * * *****************************************************************************/ int bit_get(const unsigned char *bits, int pos) { unsigned char mask; int i; /***************************************************************************** * * * Set a mask for the bit to get. * * * *****************************************************************************/ mask = 0x80; for (i = 0; i < (pos % 8); i++) mask = mask >> 1; /***************************************************************************** * * * Get the bit. * * * *****************************************************************************/ return (((mask & bits[(int)(pos / 8)]) == mask) ? 1 : 0); } /***************************************************************************** * * * -------------------------------- bit_set ------------------------------- * * * *****************************************************************************/ void bit_set(unsigned char *bits, int pos, int state) { unsigned char mask; int i; /***************************************************************************** * * * Set a mask for the bit to set. * * * *****************************************************************************/ mask = 0x80; for (i = 0; i < (pos % 8); i++) mask = mask >> 1; /***************************************************************************** * * * Set the bit. * * * *****************************************************************************/ if (state) bits[pos / 8] = bits[pos / 8] | mask; else bits[pos / 8] = bits[pos / 8] & (~mask); return; } /***************************************************************************** * * * -------------------------------- bit_xor ------------------------------- * * * *****************************************************************************/ void bit_xor(const unsigned char *bits1, const unsigned char *bits2, unsigned char *bitsx, int size) { int i; /***************************************************************************** * * * Compute the bitwise XOR (exclusive OR) of the two buffers. * * * *****************************************************************************/ for (i = 0; i < size; i++) { if (bit_ get(bits1, i) != bit_ get(bits2, i)) bit_set(bitsx, i, 1); else bit_set(bitsx, i, 0); } return; } /***************************************************************************** * * * ----------------------------- bit_rot_left ----------------------------- * * * *****************************************************************************/ void bit_rot_left(unsigned char *bits, int size, int count) { int fbit, lbit, i, j; /***************************************************************************** * * * Rotate the buffer to the left the specified number of bits. * * * *****************************************************************************/ if (size > 0) { for (j = 0; j < count; j++) { for (i = 0; i <= ((size - 1) / 8); i++) { /******************************************************************** * * * Get the bit about to be shifted off the current byte. * * * ********************************************************************/ lbit = bit_get(&bits[i], 0); if (i == 0) { /***************************************************************** * * * Save the bit shifted off the first byte for later. * * * *****************************************************************/ fbit = lbit; } else { /***************************************************************** * * * Set the rightmost bit of the previous byte to the leftmost * * bit about to be shifted off the current byte. * * * *****************************************************************/ bit_set(&bits[i - 1], 7, lbit); } /******************************************************************** * * * Shift the current byte to the left. * * * ********************************************************************/ bits[i] = bits[i] << 1; } /*********************************************************************** * * * Set the rightmost bit of the buffer to the bit shifted off the * * first byte. * * * ***********************************************************************/ bit_set(bits, size - 1, fbit); } } return; }