bdlb_bitstringimputil

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

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));