Bit Width, Indexing, and C++ Safety

May 2026 · 20 min read

Most bit bugs are not caused by AND, OR, or XOR. They are caused by using the wrong width, shifting the wrong literal, or forgetting that some C++ bit operations are undefined for edge values. This post is the safety checklist you should internalize before writing serious bit code.

Bit Indexing

Bits are usually indexed from right to left. The rightmost bit is bit 0, also called the least significant bit (LSB). The leftmost meaningful bit is the most significant bit (MSB).

Value:      0b10110100
Positions:    76543210

bit 2 = 1
bit 6 = 0
LSB = bit 0
MSB set position = 7

Literal Width: 1 vs 1LL

The literal 1 is an int. On most platforms that means 32 bits. If you write 1 << 40, you are shifting a 32-bit value by 40, which is undefined behavior.

// Wrong: 1 is int, so this is undefined when k >= 32.
long long bad = 1 << 40;

// Right: shift a 64-bit literal.
long long good = 1LL << 40;
unsigned long long mask = 1ULL << 63;

Safe Shift Rules

For a type with width W, the shift count must satisfy 0 <= k < W. Shifting by a negative amount or by the width itself is undefined.

uint32_t x = 1;
x << 31;  // ok
x << 32;  // undefined
x << -1;  // undefined

Signed vs Unsigned

Use unsigned types when you want bit patterns and modular arithmetic. Unsigned overflow is defined modulo 2^W. Signed overflow is undefined behavior in C++.

uint32_t a = 0xffffffffu;
a += 1;       // wraps to 0, well-defined

int b = INT_MAX;
b += 1;       // undefined behavior

Right shifting unsigned values is always logical: zeros are inserted on the left. Right shifting negative signed values is implementation-defined before C++20-era wording changes and should be avoided in portable code. Cast to unsigned when you want a guaranteed logical shift.

Builtin Intrinsics

GCC and Clang expose CPU-friendly bit intrinsics. They are fast, but some are undefined for zero.

__builtin_popcount(x)      // number of set bits in unsigned int
__builtin_popcountll(x)    // number of set bits in unsigned long long
__builtin_ctz(x)           // trailing zeros; undefined if x == 0
__builtin_clz(x)           // leading zeros; undefined if x == 0
__builtin_parity(x)        // popcount(x) % 2

int highest_bit(uint32_t x) {
    if (x == 0) return -1;
    return 31 - __builtin_clz(x);
}

int lowest_bit(uint32_t x) {
    if (x == 0) return -1;
    return __builtin_ctz(x);
}

C++20 <bit> Helpers

If your judge supports C++20, prefer the standard helpers for clarity.

#include <bit>

std::popcount(x);
std::countr_zero(x);
std::countl_zero(x);
std::has_single_bit(x);
std::bit_floor(x);
std::bit_ceil(x);
std::rotl(x, k);
std::rotr(x, k);

Safety Checklist

• Use 1LL or 1ULL for 64-bit masks.
• Guard shift counts: 0 <= k < width.
• Guard __builtin_ctz(0) and __builtin_clz(0).
• Use unsigned types when overflow is intentional.
• Know whether a right shift should be logical or arithmetic.
• When debugging, print fixed-width bitsets so leading zeros are visible.

Practice Problems

• LeetCode 191 - Number of 1 Bits builtins compare loop and intrinsic approaches.
• LeetCode 231 - Power of Two single bit guard zero before using n & (n - 1).
• LeetCode 342 - Power of Four masking combine single-bit check with an alternating-bit mask.
• LeetCode 190 - Reverse Bits width fixed 32-bit layout is the whole problem.