Component of the Week #15: bdlb_bitutil

Summary:

  • Provides efficient utility functions for bit manipulation on 32- and 64-bit unsigned integers.

The bdlb_bitutil component supplies a collection of efficient, low-level bit manipulation utilities for 32- and 64-bit unsigned integer types. These functions are essential for systems programming, performance-critical code, and any scenario where direct bitwise operations are required.

The methods provided include bit counting, bit setting/clearing, rounding to powers of two, and more. The implementation uses platform-specific intrinsics when available for maximum performance.

For example, you can use bdlb::BitUtil to count the number of set bits in a value:

#include <bdlb_bitutil.h>
#include <bsl_iostream.h>

unsigned int value = 0x3;
int count = bdlb::BitUtil::numBitsSet(value);
bsl::cout << "Number of set bits: " << count << bsl::endl;
// 0x3 is 11
// Output: Number of set bits: 2

You can also determine the number of leading unset bits (i.e., zeros before the first set bit):

unsigned int value = 0x8;
int leadingZeros = bdlb::BitUtil::numLeadingUnsetBits(value);
bsl::cout << "Leading unset bits: " << leadingZeros << bsl::endl;
// 8 is 0000 0000 0000 0000 0000 0000 0000 1000
//         4    8   12   16   20   24   28
// Output: Leading unset bits: 28

The component also provides functions to set or clear individual bits:

unsigned int value = 0x3;
unsigned int withBitSet = bdlb::BitUtil::withBitSet(value, 3);
unsigned int withBitCleared = bdlb::BitUtil::withBitCleared(value, 0);

bsl::cout << "With bit 3 set: 0x"
          << bsl::hex << withBitSet
          << " ("
          << bsl::dec << withBitSet
          << ")"
          << bsl::endl;
// Start with 0x3      (... 0011)
// Set bit 3 (0-based) (... 1011)
// Result: 0xa (11)

bsl::cout << "With bit 0 cleared: 0x"
          << bsl::hex << withBitCleared
          << " ("
          << bsl::dec << withBitCleared
          << ")"
          << bsl::endl;
// Start with 0x3      (... 0011)
// Clear bit 0         (... 0001)
// Result: 0x2

You can round up to the nearest power of two (i.e., the smallest power of two greater than the value):

unsigned int value = 37;
unsigned int rounded = bdlb::BitUtil::roundUpToBinaryPower(value);
bsl::cout << "Rounded up to next power of two: "
          << rounded
          << bsl::endl;
// Output: Rounded up to next power of two: 64
//     100101 (37)
// -> 1000000 (64)

You can also round to a boundary (i.e., round up to the nearest value that is a multiple of a supplied boundary value):

unsigned int boundary = 8;
unsigned int roundedToBoundary = bdlb::BitUtil::roundUp(value, boundary);
bsl::cout << "Rounded up to boundary: "
          << roundedToBoundary
          << bsl::endl;
// Output: Rounded up to boundary: 40
//     100101 (37)
// ->  101000 (40)

In summary, bdlb_bitutil provides reliable primitive bit operations and should be preferred to, for example, brewing them yourself using Hacker’s Delight.

If you’d like to know more, check out: