Component bdlb_bitstringimputil [Package bdlb]

Provide functional bit-manipulation of uint64_t values. More...

Namespaces
namespace	bdlb

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Manipulators
    • Accessors

Purpose:

Provide functional bit-manipulation of uint64_t values.

Classes:

bdlb::BitStringImpUtil

namespace for uint64_t utilities

See also:

Component bdlb_bitstringutil

Description:

This component provides a utility struct, bdlb::BitStringImpUtil, that serves as a namespace for a collection of functions that provide bit-level operations on uint64_t values. Some of these functions consist of a single bitwise logical operation. The point of implementing them as functions is to facilitate providing these functions as arguments to templates in bdlb_bitstringutil.

Note that no functions supporting uint32_t are provided here. This component exists solely to support bdlb::BitStringUtil, which deals entirely in uint64_t values.

Note that the find* functions defined here only find set bits -- there is never a context in bdlb_bitstringutil where a find* that found clear bits is needed.

Usage:

This section illustrates the intended use of this component.

Note that, in all of these examples, the low-order bit is considered bit 0 and resides on the right edge of the bit string.

Example 1: Manipulators:

This example demonstrates the "manipulator" static functions defined in this component, which can change the state of a uint64_t.

The *EqBits functions (andEqBits, minusEqBits, orEqBits, and xorEqBits), have the following signature:

    void function(uint64_t *dstValue,
                  int       dstIndex,
                  uint64_t  srcValue,
                  int       numBits);

First, we demonstrate the andEqBits function:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::andEqBits(&dstValue, 8, 0, 8)' in binary:       |
 |                                                                          |
 | 'dstValue' before in binary:       0..00000000000000000011001100110011   |
 | 'srcValue == 0' in binary:         0..00000000000000000000000000000000   |
 | 'srcValue', 0x00, at index 8:                         00000000           |
 | 'dstValue' after in binary:        0..00000000000000000000000000110011   |
 +--------------------------------------------------------------------------+

  uint64_t dstValue;

  dstValue = 0x3333;
  bdlb::BitStringImpUtil::andEqBits(&dstValue, 8, 0, 8);
  assert(static_cast<uint64_t>(0x33) == dstValue);

Then, we apply andEqBits with all bits set in the relevant part of 'srcValue, which has no effect:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::andEqBits(&dstValue, 8, 0, 8)' in binary:       |
 |                                                                          |
 | 'dstValue' before in binary:       0..00000000000000000011001100110011   |
 | 'srcValue == 0xffff' in binary:    0..00000000000000001111111111111111   |
 | 'srcValue', 0xff, at index 8:                         11111111           |
 | 'dstValue' after in binary:        0..00000000000000000011001100110011   |
 +--------------------------------------------------------------------------+

  dstValue = 0x3333;
  bdlb::BitStringImpUtil::andEqBits(&dstValue, 8, 0xffff, 8);
  assert(static_cast<uint64_t>(0x3333) == dstValue);

Next, we demonstrate orEqBits, which takes low-order bits of a srcValue and bitwise ORs them with dstValue:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::orEqBits(&dstValue, 16, 0xffff, 8)' in binary:  |
 |                                                                          |
 | 'dstValue' before in binary:       0..00110011001100110011001100110011   |
 | 'srcValue == 0xffff' in binary:    0..00000000000000001111111111111111   |
 | 'srcValue', 0xff, at index 16:                11111111                   |
 | 'dstValue' after in binary:        0..00110011111111110011001100110011   |
 +--------------------------------------------------------------------------+

  dstValue = 0x33333333;
  bdlb::BitStringImpUtil::orEqBits(&dstValue, 16, 0xffff, 8);
  assert(static_cast<uint64_t>(0x33ff3333) == dstValue);

Then, we demonstrate applying the same operation where *dstValue is initially 0:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::orEqBits(&dstValue, 16, 0xffff, 8)' in binary:  |
 |                                                                          |
 | 'dstValue' before in binary:       0..00000000000000000000000000000000   |
 | 'srcValue == 0xffff' in binary:    0..00000000000000001111111111111111   |
 | 'srcValue', 0xff, at index 16:                11111111                   |
 | 'dstValue' after in binary:        0..00000000111111110000000000000000   |
 +--------------------------------------------------------------------------+

  dstValue = 0;
  bdlb::BitStringImpUtil::orEqBits(&dstValue, 16, 0xffff, 8);
  assert(static_cast<uint64_t>(0x00ff0000) == dstValue);

Now, we apply another function, xorEqBits, that takes the low-order bits of srcValue and bitwise XORs them with dstValue:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::xorEqBits(&dstValue, 16, 0xffff, 8)' in binary: |
 |                                                                          |
 | 'dstValue' before in binary:       0..01110111011101110111011101110111   |
 | 'srcValue', 0xff, at index 16:                11111111                   |
 | 'dstValue' after in binary:        0..01110111100010000111011101110111   |
 ----------------------------------------------------------------------------

  dstValue = 0x77777777;
  bdlb::BitStringImpUtil::xorEqBits(&dstValue, 16, 0xffff, 8);
  assert(static_cast<uint64_t>(0x77887777) == dstValue);

Finally, we apply the same function with a different value of srcValue and observe the result:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::xorEqBits(&dstValue, 16, 0x5555, 8)' in binary: |
 |                                                                          |
 | 'dstValue' before in binary:       0..01110111011101110111011101110111   |
 | 'srcValue', 0x55, at index 16:                01010101                   |
 | 'dstValue' after in binary:        0..01110111001000100111011101110111   |
 +--------------------------------------------------------------------------+

  dstValue = 0x77777777;
  bdlb::BitStringImpUtil::xorEqBits(&dstValue, 16, 0x5555, 8);
  assert(static_cast<uint64_t>(0x77227777) == dstValue);

Accessors:

This example demonstrates the "accessor" static functions, which read, but do not modify, the state of a uint64_t.

The find1At(Max,Min)IndexRaw routines are used for finding the highest-order (or lowest-order) set bit in a uint64_t. These functions are "raw" because the behavior is undefined if they are passed 0.

First, we apply find1AtMaxIndexRaw:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::find1AtMaxIndexRaw(0x10a)' in binary:           |
 |                                                                          |
 | input:                             0..000000000000000000000000100001010  |
 | bit 8, highest bit set:                                       1          |
 +--------------------------------------------------------------------------+

  assert(8 == bdlb::BitStringImpUtil::find1AtMaxIndexRaw(0x10a));

Finally, we apply find1AtMinIndexRaw:

 +--------------------------------------------------------------------------+
 | 'bdlb::BitStringImpUtil::find1AtMinIndexRaw(0xffff0180)' in binary:      |
 |                                                                          |
 | input:                             0..011111111111111110000000110000000  |
 | bit 7, lowest bit set:                                         1         |
 +--------------------------------------------------------------------------+

  assert(7 == bdlb::BitStringImpUtil::find1AtMinIndexRaw(0xffff0180));