Binary Representation of Integers

March 2026 · 24 min read

The previous post covered how to read and convert bases. This post starts from that foundation and focuses on how integers are stored in a fixed number of bits: unsigned ranges, two's complement, overflow, sign extension, and C++ integer types.

Unsigned Integers

An unsigned integer uses all $n$ bits to represent the magnitude. There is no sign. The range is straightforward:

Two's Complement: Representing Negative Numbers

To represent negative numbers, C++ (and virtually all modern hardware) uses two's complement. The key idea: the most significant bit (MSB) has a negative weight.

In an 8-bit two's complement number, the bit values are:

For example, 0b11111110:

How to Negate: Flip and Add 1

To get the two's complement of a number (i.e., negate it), invert all bits and add 1:

// Negate 5 (8-bit):
 5 = 0b00000101
~5 = 0b11111010   (flip all bits)
+1 = 0b11111011   (add 1)
-5 = 0b11111011

// Verify: -128 + 64 + 32 + 16 + 8 + 0 + 2 + 1
//       = -128 + 123 = -5 ✓

This works because $x + \text{NOT}(x) = \text{all 1s} = -1$ in two's complement. So $\text{NOT}(x) + 1 = -x$.

Proof: All-Ones Is Always −1

The claim that every bit set to 1 equals $-1$ holds for any width $n$, and the negation rule above depends on it, so it is worth proving. Each bit at position $k$ carries weight $+2^k$, except the sign bit at position $n-1$, whose weight is $-2^{n-1}$:

Setting every $b_k = 1$ leaves the sign term plus a geometric series over the low bits:

Why Two's Complement?

The hardware does not need a separate subtraction circuit. Subtraction is just addition of the negated value. The same adder circuit handles both signed and unsigned arithmetic. This is why two's complement won over sign-magnitude and one's complement.

Signed Integer Ranges

Notice the asymmetry: there is one more negative value than positive. $|min| = max + 1$. This means -INT_MIN overflows!

Overflow and Underflow

Unsigned overflow wraps around modulo $2^n$. Adding 1 to UINT8_MAX (255) gives 0. This is well-defined in C++.

uint8_t x = 255;
x += 1;   // x is now 0 (wraps around)

// In binary:
//   11111111
// + 00000001
// = 00000000  (9th bit discarded)

Signed overflow is undefined behavior in C++. The compiler is allowed to assume it never happens, which can lead to surprising optimizations.

int x = INT_MAX;     // 2147483647
x += 1;             // UNDEFINED BEHAVIOR!
// Compiler might optimize (x + 1 > x) to always true

Sign Extension

When a smaller signed type is promoted to a larger one, the sign bit is extended to fill the new bits:

int8_t  small = -5;    // 0b11111011 (8 bits)
int32_t big   = small; // 0b11111111 11111111 11111111 11111011 (32 bits)
// The leading 1s (sign bit) are replicated. Value is still -5.

uint8_t  usmall = 251;  // 0b11111011 (8 bits)
uint32_t ubig   = usmall; // 0b00000000 00000000 00000000 11111011
// Zero-extended. Value is 251.

Why Sign Extension Preserves the Value

Replicating the sign bit is not an arbitrary rule; it is the only fill that keeps the value unchanged. Split the low bits off as $L = \sum_{k=0}^{n-2} b_k\,2^k$, the part sign extension never touches:

One extra bit at a time. Widening by a single bit turns position $n-1$ into an ordinary bit (its weight flips from $-2^{n-1}$ to $+2^{n-1}$) and adds a new sign bit at position $n$ with weight $-2^n$. Sign extension copies $s = b_{n-1}$ into that new slot, so the top two positions now contribute:

That is exactly the weight the lone sign bit carried before, so one step changes nothing for either value of $s$. By induction, extending from $n$ up to any width $m$ is value-preserving.

Hexadecimal: A Better Way to Read Bits

Binary patterns are long and hard to read. Hexadecimal (base 16) groups every 4 bits into one digit, making it much more compact:

0xFF       = 0b11111111           = 255
0xDEADBEEF = 0b11011110 10101101 10111110 11101111
0x0000000F = 0b00000000 00000000 00000000 00001111

Integer Types in C++

#include <cstdint>   // fixed-width types

int8_t   a;  // exactly 8 bits, signed
uint8_t  b;  // exactly 8 bits, unsigned
int16_t  c;  // exactly 16 bits, signed
uint32_t d;  // exactly 32 bits, unsigned
int64_t  e;  // exactly 64 bits, signed

// Standard types (platform-dependent sizes):
// int:       at least 16 bits (usually 32)
// long:      at least 32 bits
// long long: at least 64 bits

// Size checking:
static_assert(sizeof(int) == 4);   // 4 bytes = 32 bits on most platforms
static_assert(sizeof(long long) == 8);

Printing Binary in C++

#include <bitset>
#include <iostream>

int x = 42;
std::cout << std::bitset<8>(x) << "\n";   // 00101010
std::cout << std::bitset<32>(x) << "\n";  // 00000000000000000000000000101010

// Custom printer:
void print_bits(uint32_t n) {
    for (int i = 31; i >= 0; --i) {
        std::cout << ((n >> i) & 1);
        if (i % 8 == 0) std::cout << ' ';
    }
    std::cout << "\n";
}
print_bits(42);  // 00000000 00000000 00000000 00101010

CP Tips: Builtins, Unsigned Tricks, and Identities

A few facts worth burning into memory before you write a contest solution that touches bits.

GCC __builtin_* intrinsics ($O(1)$)

These compile to single CPU instructions on modern x86 (POPCNT, BSF/TZCNT, BSR/LZCNT). They are the standard "go to" toolkit in competitive programming — both Codeforces and CSES judges support them.

__builtin_popcount(x)    // number of set bits in unsigned int
__builtin_popcountll(x)  // ... in unsigned long long
__builtin_ctz(x)         // count trailing zeros (index of lowest set bit)
__builtin_clz(x)         // count leading zeros (31 - msb_index for 32-bit)
__builtin_parity(x)      // popcount(x) & 1
__builtin_ffs(x)         // 1 + index of lowest set bit, or 0 if x == 0

// WARNING: __builtin_ctz(0) and __builtin_clz(0) are UNDEFINED.
// Always guard: if (x) k = __builtin_ctz(x);

For 64-bit values use the ll suffix (__builtin_popcountll, __builtin_ctzll, __builtin_clzll). With uint32_t the highest set bit is 31 - __builtin_clz(x); with uint64_t it is 63 - __builtin_clzll(x).

Why unsigned is the safe choice for hashing and bit tricks

Unsigned arithmetic in C++ is defined to wrap modulo $2^n$. That makes it safe — and idiomatic — for polynomial hashing, rolling hashes, mixing functions, and any place you want $\bmod\,2^{32}$ or $\bmod\,2^{64}$ semantics for free:

uint64_t h = 0;
for (char c : s) h = h * 1315423911u + c;   // wraps mod 2^64 — well-defined

The same code with int64_t is technically undefined behavior the moment overflow happens. Modern optimizers exploit signed-overflow UB aggressively (loop bounds inference, dead-branch elimination), so prefer uint32_t / uint64_t whenever you intend wrap-around.

Two's-complement identities you should recognize on sight

• $\sim x = -x - 1$, equivalently $-x = \sim x + 1$ — the formal definition of two's complement negation.
• $x + \sim x = -1$ — every bit is either 0+1 or 1+0, giving all-ones, which is $-1$ in two's complement.
• $x \mathbin{\&} (-x)$ isolates the lowest set bit. Reason: $-x = \sim x + 1$ flips everything above the lowest 1 and leaves it alone.
• $x \mathbin{\&} (x - 1)$ clears the lowest set bit. Combined with a counter, this is Brian Kernighan's popcount.
• $x \oplus (x - 1)$ produces a mask of the lowest set bit and everything below it.
• -1 as an unsigned value is UINT_MAX (all-ones); useful as a "full mask" sentinel.

Summary

• Binary representation in programs is fixed-width: the same bit pattern must be interpreted with its type and width.
• Unsigned integers use all bits for magnitude: range $[0, 2^n - 1]$.
• Two's complement represents signed integers by giving the MSB a negative weight. Negate by flipping all bits and adding 1.
• Signed range: $[-2^{n-1}, 2^{n-1} - 1]$. There is one more negative value than positive.
• Unsigned overflow wraps modulo $2^n$ (well-defined). Signed overflow is undefined behavior.
• Sign extension fills new high bits with the sign bit. Zero extension fills with 0.
• Hexadecimal groups 4 bits into one digit, making binary patterns readable.
• Use fixed-width types (uint32_t) for portable bit manipulation.

Now that you understand how numbers are stored, the next post introduces the six bitwise operators and how they transform bit patterns.

Practice Problems

These problems drill exactly what this post covered: fixed-width representation, two's complement, overflow, and bit layout. Ordered roughly easy → hard.

• LeetCode 67 — Add Binary binary arithmetic implement school-book ripple-carry addition on bit strings.
• LeetCode 405 — Convert a Number to Hexadecimal hex · two's complement negative inputs force you to think in unsigned 32-bit.
• LeetCode 190 — Reverse Bits bit layout classic 32-bit reversal; great practice for shift + mask.
• LeetCode 7 — Reverse Integer signed overflow the whole point of the problem is detecting INT_MAX/INT_MIN overflow before it happens.
• LeetCode 371 — Sum of Two Integers two's complement · XOR + carry add without + or -; forces you to internalize how addition works at the bit level.
• LeetCode 29 — Divide Two Integers signed overflow trap watch out for INT_MIN / -1; classic CP edge case.
• LeetCode 50 — Pow(x, n) negative-n trap n = INT_MIN means -n overflows; cast to long long first.
• CSES — Bit Strings powers of two · modular exponentiation compute $2^n \bmod (10^9{+}7)$; uses the unsigned/modular thinking from this post.