Component bdlb_bitutil [Package bdlb]

Provide efficient bit-manipulation of uint32_t/uint64_t values. More...

Namespaces
namespace	bdlb

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage

Purpose:

Provide efficient bit-manipulation of uint32_t/uint64_t values.

Classes:

bdlb::BitUtil

namespace for uint32_t and uint64_t bit-level operations

Description:

This component provides a utility struct, bdlb::BitUtil, that serves as a namespace for a collection of efficient, bit-level procedures on uint32_t and uint64_t. In particular, BitUtil supplies single bit manipulation, bit counting, and mathematical functions that can be optimized with bitwise operations.

Some of the methods provided in BitUtil have other common names. Below is a list of mappings from the name used in BitUtil to these related function names:

• numLeadingUnsetBits: cntlz, clz, ffs, ffo, nlz, ctlz
• numTrailingUnsetBits: cnttz, ctz, ntz, cttz
• numBitsSet: popcnt, popcount

Usage:

The following usage examples illustrate how some of the methods provided by this component are used. 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.

First, we use withBitSet to demonstrate the ordering of bits:

  assert(static_cast<uint32_t>(0x00000001)
                 == bdlb::BitUtil::withBitSet(static_cast<uint32_t>(0),  0));
  assert(static_cast<uint32_t>(0x00000008)
                 == bdlb::BitUtil::withBitSet(static_cast<uint32_t>(0),  3));
  assert(static_cast<uint32_t>(0x00800000)
                 == bdlb::BitUtil::withBitSet(static_cast<uint32_t>(0), 23));
  assert(static_cast<uint32_t>(0x66676666)
        == bdlb::BitUtil::withBitSet(static_cast<uint32_t>(0x66666666), 16));

  /*------------------------------------------------------------------------+
  | 'bdlb::BitUtil::withBitSet(0x66666666, 16)' in binary:                  |
  |                                                                         |
  | input in binary:                       01100110011001100110011001100110 |
  | set bit 16:                                           1                 |
  | result:                                01100110011001110110011001100110 |
  +------------------------------------------------------------------------*/

Then, we count the number of set bits in a value with numBitsSet:

  assert(0 == bdlb::BitUtil::numBitsSet(static_cast<uint32_t>(0x00000000)));
  assert(2 == bdlb::BitUtil::numBitsSet(static_cast<uint32_t>(0x00101000)));
  assert(8 == bdlb::BitUtil::numBitsSet(static_cast<uint32_t>(0x30071101)));

  /*------------------------------------------------------------------------+
  | 'bdlb::BitUtil::numBitsSet(0x30071101)' in binary:                      |
  |                                                                         |
  | input in binary:                       00110000000001110001000100000001 |
  | that has 8 bits set.  result: 8                                         |
  +------------------------------------------------------------------------*/

Finally, we use numLeadingUnsetBits to determine the number of unset bits with a higher index than the first set bit:

  assert(32 ==
      bdlb::BitUtil::numLeadingUnsetBits(static_cast<uint32_t>(0x00000000)));
  assert(31 ==
      bdlb::BitUtil::numLeadingUnsetBits(static_cast<uint32_t>(0x00000001)));
  assert(7 ==
      bdlb::BitUtil::numLeadingUnsetBits(static_cast<uint32_t>(0x01000000)));
  assert(7 ==
      bdlb::BitUtil::numLeadingUnsetBits(static_cast<uint32_t>(0x01620030)));

  /*------------------------------------------------------------------------+
  | 'bdlb::BitUtil::numLeadingUnsetBits(0x01620030)' in binary:             |
  |                                                                         |
  | input in binary:                       00000001011000100000000000110000 |
  | highest set bit:                              1                         |
  | number of unset bits leading this set bit == 7                          |
  +------------------------------------------------------------------------*/