Binary numbers, two's complement and overflow

Computers store a whole number as a fixed number of bits, and each bit stands for a power of two: 13 is 1101 in binary, because 8 + 4 + 1 = 13. Negative numbers use two’s complement: in an n-bit integer the top bit counts as −2ⁿ⁻¹ instead of +2ⁿ⁻¹, so 8 bits hold −128 to 127 and −5 is stored as 11111011. Overflow happens when a result needs more bits than the type has. The extra bits are dropped, so in 8 bits 127 + 1 comes out as −128. Languages disagree about whether that is allowed: Java and Go define the wrap, C++ calls signed overflow undefined behaviour, JavaScript computes in floating point until a bitwise operator forces 32 bits, and Python’s integers simply grow. This lesson converts between bases, builds two’s complement patterns three ways, and runs the same overflow and shift experiments in all five languages, with the output each one printed.

Binary and hexadecimal: place values in base 2 and base 16

In base 10 each position is worth ten times the one to its right. In base 2 each position is worth twice as much: 1, 2, 4, 8, 16 and so on, and every digit is 0 or 1. The binary digits of a number say which powers of two add up to it: 200 is 128 + 64 + 8, so it is written 11001000. Repeated division finds those digits without guessing. Divide by 2, and the remainder is the lowest bit; divide the quotient by 2 again for the next bit, until nothing is left.

Hexadecimal is base 16, with the digits 0 to 9 and then a to f for 10 to 15. Because 16 is 2⁴, one hexadecimal digit holds exactly four bits, so converting between binary and hexadecimal is only regrouping: 1100 1000 is c8. That is why programmers write bit patterns in hexadecimal: 0xff is eight 1 bits, one full byte, and 0xffff_ffff is 32 of them.

"""Writing whole numbers in base 2 and base 16 by repeated division, checked against Python's own conversions."""

DIGITS = "0123456789abcdef"


def to_base(n, base):
    """The digits of n >= 0 in the given base, most significant first."""
    if n == 0:
        return "0"
    digits = []
    while n > 0:
        n, remainder = divmod(n, base)  # the remainder is the next digit, from the right
        digits.append(DIGITS[remainder])
    return "".join(reversed(digits))


def from_base(text, base):
    """The value of a string of digits: multiply what you have by the base, then add the next digit."""
    value = 0
    for ch in text:
        value = value * base + DIGITS.index(ch)
    return value


def in_fours(bits):
    """Binary digits in groups of four from the right, the way hexadecimal reads them."""
    bits = bits.zfill(-(-len(bits) // 4) * 4)
    return " ".join(bits[i : i + 4] for i in range(0, len(bits), 4))


print(f"{'decimal':>8}  {'binary':<19}  {'hex':>4}  matches Python")
for n in (13, 200, 255, 1000, 65535):
    b, h = to_base(n, 2), to_base(n, 16)
    same = b == format(n, "b") and h == format(n, "x") and from_base(b, 2) == n == int(h, 16)
    print(f"{n:>8}  {in_fours(b):<19}  {h:>4}  {'yes' if same else 'NO'}")

# Every 1 bit contributes its power of two.
n = 200
powers = [1 << i for i in range(n.bit_length() - 1, -1, -1) if (n >> i) & 1]
print(f"\n{n} = " + " + ".join(map(str, powers)))
# One hexadecimal digit is exactly one group of four bits.
print("0xc8: " + ", ".join(f"{d} is {int(d, 16):04b}" for d in "c8") + ", so 0xc8 = 1100 1000")

 decimal  binary                hex  matches Python
      13  1101                    d  yes
     200  1100 1000              c8  yes
     255  1111 1111              ff  yes
    1000  0011 1110 1000        3e8  yes
   65535  1111 1111 1111 1111  ffff  yes

200 = 128 + 64 + 8
0xc8: c is 1100, 8 is 1000, so 0xc8 = 1100 1000

The table compares the hand-written conversions with Python’s format() and int() for five numbers, and they agree. Reading the rows back gives a rule worth knowing by heart: n bits can form 2ⁿ different patterns, so read as plain non-negative numbers they cover 0 to 2ⁿ − 1. Eight bits reach 255, sixteen bits 65,535 and 32 bits 4,294,967,295. The number 65,535 is sixteen 1 bits, ffff, the largest 16-bit value.

Negative numbers: two’s complement

A row of bits has no room for a minus sign. Two’s complement solves this by giving the top bit a negative weight. In 8 bits the weights are −128, 64, 32, 16, 8, 4, 2 and 1, so every pattern that starts with 0 is one of 0 to 127, and every pattern that starts with 1 is one of −128 to −1, because −128 plus at most 127 never reaches zero.

Three methods give the pattern of a negative number −x, and they always agree:

1. Invert and add one. Write x, flip every bit, then add 1: 5 is 00000101, inverted 11111010, plus one 11111011.
2. Subtract from 2ⁿ. In n bits, −x is stored as the unsigned number 2ⁿ − x: 256 − 5 = 251, which is 11111011.
3. Add up the weights. Choose the bits whose weights sum to −x: −128 + 123 = −5.

The program below applies all three to eight values and compares them with Python’s own conversion, int.to_bytes(signed=True), which the Python documentation describes as two’s complement:

"""Signed numbers in 8 bits: the two's complement pattern, found three ways, and read back with a negative top bit."""

BITS = 8
MASK = (1 << BITS) - 1  # 0b11111111: keeps the lowest 8 bits


def pattern(x):
    """The 8-bit two's complement pattern of x, for -128 <= x <= 127."""
    return format(x & MASK, "08b")


def value(bits):
    """Reads a pattern: the top bit weighs -128, the others +64, +32, ..., +1."""
    return -int(bits[0]) * (1 << (BITS - 1)) + int(bits[1:], 2)


print(f"{'value':>6}   {'pattern':<8}   {'invert, +1':>10}   {'256 - |x|':>10}   to_bytes")
for x in (0, 1, 5, 127, -1, -5, -127, -128):
    if x < 0:
        by_flip = format((~(-x) + 1) & MASK, "08b")  # invert the bits of |x|, then add one
        by_minus = format((1 << BITS) + x, "08b")  # 256 - |x|
    else:
        by_flip = by_minus = "(as is)"
    library = x.to_bytes(1, "big", signed=True).hex()
    assert value(pattern(x)) == x
    print(f"{x:>6}   {pattern(x)}   {by_flip:>10}   {by_minus:>10}   0x{library}")

# One adder serves both readings: the same 8 bits are 251 unsigned and -5 signed.
a, b = 0b11111011, 0b00000111
total = a + b
print(f"\n{a:08b} + {b:08b} = {total:09b}: the ninth bit does not fit, {total & MASK:08b} is kept")
print(f"read unsigned: 251 + 7 = {total & MASK}, which is 258 - 256")
print(f"read signed:    -5 + 7 = {value(format(total & MASK, '08b'))}")

# The ranges are lopsided: one more negative number than positive ones.
for bits in (8, 16, 32, 64):
    print(f"{bits:>2} bits: {-(1 << (bits - 1)):,} to {(1 << (bits - 1)) - 1:,}")
negated = format(-(-128) & MASK, "08b")  # +128 does not fit in 8 bits, so only its low 8 bits are kept
print(f"-(-128) in 8 bits: {negated}, which reads as {value(negated)}")

 value   pattern    invert, +1    256 - |x|   to_bytes
     0   00000000      (as is)      (as is)   0x00
     1   00000001      (as is)      (as is)   0x01
     5   00000101      (as is)      (as is)   0x05
   127   01111111      (as is)      (as is)   0x7f
    -1   11111111     11111111     11111111   0xff
    -5   11111011     11111011     11111011   0xfb
  -127   10000001     10000001     10000001   0x81
  -128   10000000     10000000     10000000   0x80

11111011 + 00000111 = 100000010: the ninth bit does not fit, 00000010 is kept
read unsigned: 251 + 7 = 2, which is 258 - 256
read signed:    -5 + 7 = 2
 8 bits: -128 to 127
16 bits: -32,768 to 32,767
32 bits: -2,147,483,648 to 2,147,483,647
64 bits: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
-(-128) in 8 bits: 10000000, which reads as -128

Hardware uses two’s complement because one adder then serves signed and unsigned numbers alike. The same bits 11111011 are 251 when read unsigned and −5 when read signed. Adding 00000111 gives a ninth bit that does not fit, and the eight bits that remain, 00000010, are right for both readings: 251 + 7 = 258, which is 2 after dropping 256, and −5 + 7 = 2. A separate sign bit in front of the magnitude, the obvious alternative, gives two zeros, +0 and −0, and needs extra rules for adding numbers of different signs; two’s complement has exactly one zero.

The ranges are lopsided. There is one more negative number than there are positive ones, because zero takes one of the patterns that start with 0, so 8 bits run from −128 to 127, and a 32-bit int covers −2,147,483,648 up to 2,147,483,647. Negating the most negative number therefore overflows back to itself: −(−128) needs +128, which 8 bits cannot hold, and the bits left over read as −128 again. The C++ standard now requires this representation for its signed types, calling the range $-2^{N-1}$ to $2^{N-1} - 1$ for a type of width N, and the Java and Go specifications define their integers as two’s complement too.

Overflow: when a result does not fit

Picture the 16 patterns of 4 bits around a circle, in counting order. Adding 1 moves one step clockwise, and two places on the circle are special: one where an unsigned reading jumps from 15 back to 0, and one where a signed reading jumps from +7 to −8.

The signed jump is the dangerous one, because nothing in the bits marks it. There is a simple test for it: adding two numbers of the same sign must give a result of that sign, so a sum of two positive numbers that comes out negative, or of two negative numbers that comes out positive, has overflowed. Adding numbers of opposite signs can never overflow. What happens next depends on the language, so the same experiments follow in five of them, starting with the two that run in the browser:

"""Python's int never overflows; the fixed-size places a Python program writes ints into refuse values that do not fit."""

import struct
from array import array

top = 2**31 - 1  # the largest 32-bit signed value
print("2**31 - 1 + 1 =", top + 1)
print("2**64 =", 2**64, "which needs", (2**64).bit_length(), "bits")

# Converting to a fixed width is where overflow can happen, and each of these refuses loudly.
for attempt in (
    lambda: (2**31).to_bytes(4, "little", signed=True),
    lambda: struct.pack("<i", 2**31),
    lambda: array("b", [200]),  # "b" holds one signed byte, -128 to 127
):
    try:
        attempt()
    except (OverflowError, struct.error) as e:
        name = "struct.error" if isinstance(e, struct.error) else type(e).__name__
        print(f"{name}: {e}")


def wrap32(x):
    """What a 32-bit signed int would hold: keep the low 32 bits, then give the top bit the weight -2**31."""
    x &= 0xFFFF_FFFF
    return x - (1 << 32) if x >> 31 else x


print(f"in 32 bits, 2**31 - 1 + 1 would be {wrap32(top + 1):,}")
print(f"in 32 bits, 50,000 * 50,000 would be {wrap32(50_000 * 50_000):,}")

2**31 - 1 + 1 = 2147483648
2**64 = 18446744073709551616 which needs 65 bits
OverflowError: int too big to convert
struct.error: 'i' format requires -2147483648 <= number <= 2147483647
OverflowError: signed char is greater than maximum
in 32 bits, 2**31 - 1 + 1 would be -2,147,483,648
in 32 bits, 50,000 * 50,000 would be -1,794,967,296

// JavaScript numbers are 64-bit floating point, so ordinary arithmetic does not wrap; the bitwise operators
// convert their operands to 32-bit integers first, and integers above 2 ** 53 lose exactness.
console.log('2147483647 + 1 =', 2147483647 + 1);
console.log('(2 ** 31) | 0 =', (2 ** 31) | 0);
console.log('(2 ** 32 + 5) | 0 =', (2 ** 32 + 5) | 0);
console.log('Math.imul(2147483647, 2) =', Math.imul(2147483647, 2));
console.log('Number.MAX_SAFE_INTEGER =', Number.MAX_SAFE_INTEGER);
console.log('2 ** 53 + 1 === 2 ** 53:', 2 ** 53 + 1 === 2 ** 53);
console.log('Number.isSafeInteger(2 ** 53):', Number.isSafeInteger(2 ** 53));
// BigInt has no size limit; BigInt.asIntN wraps a value to n bits on request.
console.log('2n ** 64n =', String(2n ** 64n));
console.log('BigInt.asIntN(32, 2n ** 31n) =', String(BigInt.asIntN(32, 2n ** 31n)));

2147483647 + 1 = 2147483648
(2 ** 31) | 0 = -2147483648
(2 ** 32 + 5) | 0 = 5
Math.imul(2147483647, 2) = -2
Number.MAX_SAFE_INTEGER = 9007199254740991
2 ** 53 + 1 === 2 ** 53: true
Number.isSafeInteger(2 ** 53): false
2n ** 64n = 18446744073709551616
BigInt.asIntN(32, 2n ** 31n) = -2147483648

Python’s integers have unlimited precision, so 2³¹ − 1 + 1 is simply 2,147,483,648 and 2⁶⁴ needs 65 bits without any trouble. Overflow meets a Python program only where a value goes into a fixed-size slot: to_bytes, struct and array all refuse a value that does not fit, with an exception, instead of storing something else. The wrap32 function shows what a 32-bit integer would have kept.

JavaScript’s ordinary numbers are 64-bit floating-point values, so 2147483647 + 1 is exact too. The bitwise operators are different: the specification’s ToInt32 step first reduces their operands modulo 2³², so (2 ** 31) | 0 is −2,147,483,648 and (2 ** 32 + 5) | 0 is 5. A second limit applies to all numbers. Integers are exact only up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1, and above it neighbouring integers share one value, so 2 ** 53 + 1 === 2 ** 53 is true. BigInt has no such limit, and BigInt.asIntN wraps a value to n bits only when asked.

Java, Go and C++ check nothing at run time, but they disagree about what that means:

// Java's int is 32-bit two's complement and wraps silently; Math.addExact and its relatives throw instead.
public class Overflow {
    public static void main(String[] args) {
        int max = Integer.MAX_VALUE;
        System.out.println("Integer.MAX_VALUE + 1 = " + (max + 1));
        System.out.println("Integer.MIN_VALUE - 1 = " + (Integer.MIN_VALUE - 1));
        System.out.println("50000 * 50000 = " + (50000 * 50000));
        System.out.println("Math.abs(Integer.MIN_VALUE) = " + Math.abs(Integer.MIN_VALUE));
        System.out.println("(byte) 200 = " + (byte) 200);
        System.out.println("(long) max + 1 = " + ((long) max + 1));
        try {
            System.out.println(Math.addExact(max, 1));
        } catch (ArithmeticException e) {
            System.out.println("Math.addExact(max, 1) threw ArithmeticException: " + e.getMessage());
        }
    }
}

// Go's sized integers wrap at run time; the language specification defines the result.
package main

import (
	"fmt"
	"math"
)

func main() {
	top := int32(math.MaxInt32)
	fmt.Println("int32 MaxInt32 + 1 =", top+1)
	x, y := int32(50000), int32(50000)
	fmt.Println("int32 50000 * 50000 =", x*y)
	low := int32(math.MinInt32)
	fmt.Println("int32 -MinInt32 =", -low)
	var b uint8 = 255
	b++
	fmt.Println("uint8 255 + 1 =", b)
	big := int64(math.MaxInt64)
	fmt.Println("int64 MaxInt64 + 1 =", big+1)
}

// The same addition written with constants: Go evaluates it exactly while compiling, and refuses a value that
// does not fit the type.
package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(int32(math.MaxInt32 + 1))
}

// Signed overflow in C++ is undefined behaviour: the standard says nothing about the result, so the compiler may
// assume it never happens. The number comes from the command line so that the compiler cannot work it out early.
#include <climits>
#include <cstdio>
#include <cstdlib>

bool still_larger(int x) { return x + 1 > x; }

int main(int argc, char** argv) {
    std::setvbuf(stdout, nullptr, _IONBF, 0);  // print in program order, between the sanitizer's reports
    int x = argc > 1 ? std::atoi(argv[1]) : 0;
    int y = x + 1;
    std::printf("x + 1 = %d\n", y);
    std::printf("x + 1 > x is %s\n", still_larger(x) ? "true" : "false");
    unsigned u = UINT_MAX;
    std::printf("UINT_MAX + 1u = %u (unsigned arithmetic is defined to wrap)\n", u + 1u);
}

from session import run, versions

versions("java -version", "go version", "clang++ --version")
# The C++ file is built three ways: with UndefinedBehaviorSanitizer, without optimisation, and optimised.
run(
    """
java Overflow.java
go run overflow.go
go run constant_overflow.go
clang++ -std=c++23 -g -fsanitize=undefined overflow.cpp -o overflow_ubsan
./overflow_ubsan 2147483647
clang++ -std=c++23 -O0 overflow.cpp -o overflow_O0
./overflow_O0 2147483647
clang++ -std=c++23 -O2 overflow.cpp -o overflow_O2
./overflow_O2 2147483647
""",
    expect_failure=("go run constant_overflow.go",),
)

# openjdk version "25.0.4.1" LTS
# go version go1.27.1 darwin/arm64
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ java Overflow.java
Integer.MAX_VALUE + 1 = -2147483648
Integer.MIN_VALUE - 1 = 2147483647
50000 * 50000 = -1794967296
Math.abs(Integer.MIN_VALUE) = -2147483648
(byte) 200 = -56
(long) max + 1 = 2147483648
Math.addExact(max, 1) threw ArithmeticException: integer overflow
$ go run overflow.go
int32 MaxInt32 + 1 = -2147483648
int32 50000 * 50000 = -1794967296
int32 -MinInt32 = -2147483648
uint8 255 + 1 = 0
int64 MaxInt64 + 1 = -9223372036854775808
$ go run constant_overflow.go
# command-line-arguments
./constant_overflow.go:11:20: constant 2147483648 overflows int32
[exit status 1]
$ clang++ -std=c++23 -g -fsanitize=undefined overflow.cpp -o overflow_ubsan
$ ./overflow_ubsan 2147483647
overflow.cpp:12:15: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior overflow.cpp:12:15 
x + 1 = -2147483648
overflow.cpp:7:37: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior overflow.cpp:7:37 
x + 1 > x is false
UINT_MAX + 1u = 0 (unsigned arithmetic is defined to wrap)
$ clang++ -std=c++23 -O0 overflow.cpp -o overflow_O0
$ ./overflow_O0 2147483647
x + 1 = -2147483648
x + 1 > x is false
UINT_MAX + 1u = 0 (unsigned arithmetic is defined to wrap)
$ clang++ -std=c++23 -O2 overflow.cpp -o overflow_O2
$ ./overflow_O2 2147483647
x + 1 = -2147483648
x + 1 > x is true
UINT_MAX + 1u = 0 (unsigned arithmetic is defined to wrap)

Read the results language by language:

• Java wraps silently: the Java Language Specification states that its integer operators give no sign of overflow at all. Integer.MAX_VALUE + 1 is −2,147,483,648, and Math.abs(Integer.MIN_VALUE) is still negative, the lopsided range again. (byte) 200 keeps the lowest 8 bits and reads them as −56. Casting to long before adding gives the right answer, and Math.addExact throws an ArithmeticException instead of wrapping.
• Go wraps too, and its specification defines the result for signed integers: “Overflow does not cause a run-time panic”, and a compiler may not assume that x < x + 1 is always true. Constant expressions are the exception. Go computes them exactly while compiling, so int32(math.MaxInt32 + 1) stops the build with “constant 2147483648 overflows int32”.
• C++ leaves signed overflow undefined: the standard says the behaviour is undefined when a result is not in the range of its type, so a program that overflows has no defined meaning at all. UndefinedBehaviorSanitizer reports both additions as “signed integer overflow”. The unoptimised build happens to wrap, so x + 1 > x prints false. The optimised build prints the wrapped −2,147,483,648 and then says that x + 1 > x is true: the optimiser assumed that signed overflow never happens and replaced the comparison with true. Unsigned arithmetic is different, because the standard defines it modulo $2^N$, so UINT_MAX + 1u is 0 in every build.

The C++ result is why overflow bugs survive testing: the same source can print different answers at different optimisation levels. Three habits prevent them in every language. Choose a type wide enough for the largest value the program can meet, and compute in it from the start ((long) a + b, not (long) (a + b)). Use checked arithmetic, such as Math.addExact, where a wrong number is worse than an error. And test at the edges of the range, with UndefinedBehaviorSanitizer turned on for C++. The midpoint of a binary search is the classic case: the binary search lesson shows a midpoint formula that cannot overflow.

Shifts: multiplying and dividing by powers of two

Shifting a number’s bits k places to the left multiplies it by 2ᵏ, and shifting them k places to the right divides it by 2ᵏ. Two questions decide what a right shift does to a negative number. The first is what fills the empty places on the left. A logical shift fills them with zeros, which treats the pattern as unsigned. An arithmetic shift copies the sign bit, so a negative number stays negative. The second question is rounding: an arithmetic shift rounds down, towards minus infinity, while integer division in Java, C++ and Go rounds towards zero.

"""Shifts in Python: multiplying and dividing by powers of two, rounding down, with no fixed width."""

print("13 << 3 =", 13 << 3, "= 13 * 2**3")
print("1 << 100 =", 1 << 100)
print("13 >> 2 =", 13 >> 2, "= 13 // 4")

# A right shift rounds down (towards minus infinity), like //, while int(a / b) rounds towards zero.
for a in (7, -7):
    print(f"{a:>2} >> 1 = {a >> 1:>2}   {a:>2} // 2 = {a // 2:>2}   int({a} / 2) = {int(a / 2):>2}")

print("-1 >> 10 =", -1 >> 10, "(the sign bits never run out)")
# A logical (zero-filling) shift needs a width: mask to 32 bits first.
x = -16
print(f"-16 as 32 bits: {x & 0xFFFF_FFFF:032b}")
print("(-16 & 0xFFFF_FFFF) >> 2 =", (x & 0xFFFF_FFFF) >> 2)
try:
    1 << -1
except ValueError as e:
    print("1 << -1: ValueError:", e)

13 << 3 = 104 = 13 * 2**3
1 << 100 = 1267650600228229401496703205376
13 >> 2 = 3 = 13 // 4
 7 >> 1 =  3    7 // 2 =  3   int(7 / 2) =  3
-7 >> 1 = -4   -7 // 2 = -4   int(-7 / 2) = -3
-1 >> 10 = -1 (the sign bits never run out)
-16 as 32 bits: 11111111111111111111111111110000
(-16 & 0xFFFF_FFFF) >> 2 = 1073741820
1 << -1: ValueError: negative shift count

// Shifts in JavaScript work on 32-bit integers: >> copies the sign bit in, >>> fills with zeros, and only the
// lowest 5 bits of the shift count are used.
console.log('13 << 3 =', 13 << 3);
console.log('-7 >> 1 =', -7 >> 1, '  Math.trunc(-7 / 2) =', Math.trunc(-7 / 2));
console.log('-16 >> 2 =', -16 >> 2, '  -16 >>> 2 =', -16 >>> 2);
console.log('(-16 >>> 0).toString(2) =', (-16 >>> 0).toString(2));
console.log('1 << 31 =', 1 << 31);
console.log('1 << 32 =', 1 << 32, '  1 << 33 =', 1 << 33);
console.log('2 ** 33 =', 2 ** 33, '  1n << 33n =', String(1n << 33n));

13 << 3 = 104
-7 >> 1 = -4   Math.trunc(-7 / 2) = -3
-16 >> 2 = -4   -16 >>> 2 = 1073741820
(-16 >>> 0).toString(2) = 11111111111111111111111111110000
1 << 31 = -2147483648
1 << 32 = 1   1 << 33 = 2
2 ** 33 = 8589934592   1n << 33n = 8589934592

Python has only the arithmetic >>, and its documentation defines it as floor division by a power of two, so -7 >> 1 is −4, the same as -7 // 2, while int(-7 / 2) rounds towards zero and gives −3. With no fixed width, the sign bits never run out: -1 >> 10 stays −1. A logical shift needs a width, so mask the value to 32 bits first. JavaScript has both shifts: >> copies the sign bit and >>> fills with zeros, both on 32-bit values. The count is reduced modulo 32, so 1 << 32 is 1 and 1 << 33 is 2. To shift past 31 bits, use multiplication or BigInt.

// Java: >> copies the sign bit in, >>> fills with zeros, and an int shift uses only the lowest 5 bits of its count.
public class Shifts {
    public static void main(String[] args) {
        System.out.println("-7 / 2 = " + (-7 / 2) + ", -7 >> 1 = " + (-7 >> 1));
        System.out.println("-16 >> 2 = " + (-16 >> 2) + ", -16 >>> 2 = " + (-16 >>> 2));
        System.out.println("Integer.toBinaryString(-16) = " + Integer.toBinaryString(-16));
        System.out.println("1 << 31 = " + (1 << 31));
        System.out.println("1 << 32 = " + (1 << 32) + ", 1 << 33 = " + (1 << 33));
        System.out.println("1L << 32 = " + (1L << 32));
    }
}

// Go: >> is arithmetic for signed and logical for unsigned integers, and a shift count has no upper limit.
package main

import "fmt"

func main() {
	a := -7
	fmt.Println("-7 / 2 =", a/2, " -7 >> 1 =", a>>1)
	s := int32(-16)
	fmt.Println("int32 -16 >> 2 =", s>>2, " uint32(-16) >> 2 =", uint32(s)>>2)
	fmt.Printf("%%b of int32(-16) = %b, of uint32(-16) = %b\n", s, uint32(s))
	one, count := uint32(1), 32
	fmt.Println("uint32 1 << 32 =", one<<count, " 1 << 31 =", one<<(count-1))
}

// C++: a right shift rounds down, while / rounds towards zero; a shift count as large as the type's width is
// undefined behaviour. The count comes from the command line so that the compiler cannot work it out early.
#include <cstdio>
#include <cstdlib>

int main(int argc, char** argv) {
    std::setvbuf(stdout, nullptr, _IONBF, 0);  // print in program order, between the sanitizer's reports
    int n = argc > 1 ? std::atoi(argv[1]) : 0;
    int a = -7;
    std::printf("-7 / 2 = %d, -7 >> 1 = %d\n", a / 2, a >> 1);
    unsigned one = 1;
    std::printf("1u << %d = %u\n", n, one << n);
}

from session import run, versions

versions("java -version", "go version", "clang++ --version")
# The C++ file is built with UndefinedBehaviorSanitizer and shifts 1u by 32, the width of unsigned int.
run(
    """
java Shifts.java
go run shifts.go
clang++ -std=c++23 -g -fsanitize=undefined shifts.cpp -o shifts_ubsan
./shifts_ubsan 32
"""
)

# openjdk version "25.0.4.1" LTS
# go version go1.27.1 darwin/arm64
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ java Shifts.java
-7 / 2 = -3, -7 >> 1 = -4
-16 >> 2 = -4, -16 >>> 2 = 1073741820
Integer.toBinaryString(-16) = 11111111111111111111111111110000
1 << 31 = -2147483648
1 << 32 = 1, 1 << 33 = 2
1L << 32 = 4294967296
$ go run shifts.go
-7 / 2 = -3  -7 >> 1 = -4
int32 -16 >> 2 = -4  uint32(-16) >> 2 = 1073741820
%b of int32(-16) = -10000, of uint32(-16) = 11111111111111111111111111110000
uint32 1 << 32 = 0  1 << 31 = 2147483648
$ clang++ -std=c++23 -g -fsanitize=undefined shifts.cpp -o shifts_ubsan
$ ./shifts_ubsan 32
-7 / 2 = -3, -7 >> 1 = -4
shifts.cpp:12:43: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior shifts.cpp:12:43 
1u << 32 = 1

• Java behaves like JavaScript for int: >> is arithmetic, >>> logical, and only the lowest five bits of the count are used, so 1 << 32 is 1. A long uses the lowest six bits, which is why 1L << 32 works.
• Go chooses by type: the shift is arithmetic for signed integers and logical for unsigned ones, and the count has no upper limit, so shifting a uint32 by 32 leaves 0. Its %b format prints a signed number with a minus sign, -10000, where Java’s toBinaryString prints all 32 bits of the pattern.
• C++ defines >> on signed types as division by 2ᵏ rounded down, an arithmetic shift, and a count that is negative or at least the width of the type is undefined behaviour. The sanitizer reports “shift exponent 32 is too large for 32-bit type ‘unsigned int’”, and the machine then produced 1, which nothing in the language promised.

Masks: picking bits out of a number

A mask picks out bits: its 1s sit exactly at the positions a program wants to keep or change. x & 0xff keeps the lowest byte of x and clears everything else; (x >> 8) & 0xff first moves the next byte down, then keeps it. An IPv4 address is a natural example: the Internet Protocol specification makes every address four octets, 32 bits, and the dotted form 192.168.1.10 is just those four bytes in decimal.

"""An IPv4 address is one 32-bit number written as four bytes: shifts and masks move between the two forms."""

import ipaddress


def pack(dotted):
    """'192.168.1.10' -> one int: shift what you have 8 bits left, then OR in the next byte."""
    value = 0
    for part in dotted.split("."):
        value = (value << 8) | int(part)
    return value


def unpack(value):
    """One int -> four bytes: shift each byte down to the bottom, then keep 8 bits with & 0xFF."""
    return ".".join(str((value >> shift) & 0xFF) for shift in (24, 16, 8, 0))


addr = pack("192.168.1.10")
print(f"192.168.1.10 = {addr:,} = 0x{addr:08x}")
print("its four bytes:", " ".join(f"{(addr >> s) & 0xFF:08b}" for s in (24, 16, 8, 0)))
print("unpacked again:", unpack(addr), "| matches ipaddress:", int(ipaddress.IPv4Address("192.168.1.10")) == addr)

# A /24 network mask is 24 ones followed by 8 zeros: & keeps the network part, & ~mask the host part.
mask = (0xFFFF_FFFF << (32 - 24)) & 0xFFFF_FFFF
print(f"/24 mask = 0x{mask:08x} = {unpack(mask)}")
print("network:", unpack(addr & mask), "| host number:", addr & ~mask & 0xFFFF_FFFF)
print("ipaddress says the network is", ipaddress.IPv4Interface("192.168.1.10/24").network)

192.168.1.10 = 3,232,235,786 = 0xc0a8010a
its four bytes: 11000000 10101000 00000001 00001010
unpacked again: 192.168.1.10 | matches ipaddress: True
/24 mask = 0xffffff00 = 255.255.255.0
network: 192.168.1.0 | host number: 10
ipaddress says the network is 192.168.1.0/24

Packing shifts the value 8 bits left and ORs in the next byte, and unpacking reverses it with shifts and & 0xff; Python’s ipaddress module agrees with both. A network prefix is a mask too. The /24 mask is 24 one bits followed by 8 zeros, 0xffffff00. ANDing the address with it keeps the network, 192.168.1.0, and ANDing with the inverted mask keeps the host number, 10.

Exercise: write and read two’s complement patterns

Write both directions by hand: the pattern of a number in a given width, refusing numbers that do not fit, and the value of a pattern whose first bit is the sign bit.

def to_binary(n, bits):
    """The bits-character two's complement pattern of n; OverflowError when n does not fit in bits bits."""
    raise NotImplementedError("write to_binary")


def from_binary(text):
    """The signed value of a pattern of 0s and 1s whose first character is the sign bit; ValueError for other text."""
    raise NotImplementedError("write from_binary")

from twos import from_binary, to_binary


def raises(error, call):
    try:
        call()
    except error:
        return True
    return False


def test_positive_numbers_and_zero():
    """non-negative numbers get leading zeros up to the width"""
    assert to_binary(5, 8) == "00000101"
    assert to_binary(0, 4) == "0000"
    assert to_binary(127, 8) == "01111111"


def test_negative_numbers():
    """negative numbers have a 1 in the sign bit"""
    assert to_binary(-1, 8) == "11111111"
    assert to_binary(-5, 8) == "11111011"
    assert to_binary(-128, 8) == "10000000"
    assert to_binary(-8, 4) == "1000"
    assert to_binary(-1, 1) == "1"


def test_numbers_that_do_not_fit():
    """a number outside -2**(bits-1) .. 2**(bits-1) - 1 raises OverflowError"""
    assert raises(OverflowError, lambda: to_binary(128, 8))
    assert raises(OverflowError, lambda: to_binary(-129, 8))
    assert raises(OverflowError, lambda: to_binary(8, 4))
    assert raises(OverflowError, lambda: to_binary(2**31, 32))


def test_reading_patterns():
    """the first character weighs -2**(length-1)"""
    assert from_binary("00000101") == 5
    assert from_binary("11111011") == -5
    assert from_binary("1000") == -8
    assert from_binary("0111") == 7
    assert from_binary("1") == -1
    assert from_binary("0") == 0


def test_wide_patterns():
    """32- and 64-bit patterns, at both ends of their ranges"""
    assert to_binary(-(2**31), 32) == "1" + "0" * 31
    assert to_binary(2**31 - 1, 32) == "0" + "1" * 31
    assert to_binary(-2, 64) == "1" * 63 + "0"
    assert from_binary("1" * 64) == -1
    assert from_binary("1" + "0" * 63) == -(2**63)


def test_every_pattern_round_trips():
    """for 1 to 10 bits, every number in range is written once and read back unchanged"""
    for bits in range(1, 11):
        numbers = range(-(2 ** (bits - 1)), 2 ** (bits - 1))
        patterns = [to_binary(n, bits) for n in numbers]
        assert all(len(p) == bits for p in patterns)
        assert len(set(patterns)) == 2**bits
        assert [from_binary(p) for p in patterns] == list(numbers)


def test_text_that_is_not_a_pattern():
    """empty text, or characters other than 0 and 1, raise ValueError"""
    assert raises(ValueError, lambda: from_binary(""))
    assert raises(ValueError, lambda: from_binary("102"))
    assert raises(ValueError, lambda: from_binary("0b101"))

/** The `bits`-character two's complement pattern of n; throws a RangeError when n does not fit in `bits` bits. */
export function toBinary(n, bits) {
  throw new Error('write toBinary');
}

/** The signed value of a pattern of 0s and 1s whose first character is the sign bit; RangeError for other text. */
export function fromBinary(text) {
  throw new Error('write fromBinary');
}

import { test, assert } from 'mysmartcopilot:test';
import { fromBinary, toBinary } from './twos.mjs';

test('non-negative numbers get leading zeros up to the width', () => {
  assert.equal(toBinary(5, 8), '00000101');
  assert.equal(toBinary(0, 4), '0000');
  assert.equal(toBinary(127, 8), '01111111');
});

test('negative numbers have a 1 in the sign bit', () => {
  assert.equal(toBinary(-1, 8), '11111111');
  assert.equal(toBinary(-5, 8), '11111011');
  assert.equal(toBinary(-128, 8), '10000000');
  assert.equal(toBinary(-8, 4), '1000');
  assert.equal(toBinary(-1, 1), '1');
});

test('a number outside -2 ** (bits - 1) .. 2 ** (bits - 1) - 1 throws a RangeError', () => {
  assert.throws(() => toBinary(128, 8), RangeError);
  assert.throws(() => toBinary(-129, 8), RangeError);
  assert.throws(() => toBinary(8, 4), RangeError);
  assert.throws(() => toBinary(2 ** 31, 32), RangeError);
});

test('the first character weighs -2 ** (length - 1)', () => {
  assert.equal(fromBinary('00000101'), 5);
  assert.equal(fromBinary('11111011'), -5);
  assert.equal(fromBinary('1000'), -8);
  assert.equal(fromBinary('0111'), 7);
  assert.equal(fromBinary('1'), -1);
  assert.equal(fromBinary('0'), 0);
});

test('32-bit patterns, at both ends of the range', () => {
  assert.equal(toBinary(-(2 ** 31), 32), '1' + '0'.repeat(31));
  assert.equal(toBinary(2 ** 31 - 1, 32), '0' + '1'.repeat(31));
  assert.equal(toBinary(-2, 32), '1'.repeat(31) + '0');
  assert.equal(fromBinary('1'.repeat(32)), -1);
  assert.equal(fromBinary('1' + '0'.repeat(31)), -(2 ** 31));
});

test('for 1 to 10 bits, every number in range is written once and read back unchanged', () => {
  for (let bits = 1; bits <= 10; bits++) {
    const seen = new Set();
    for (let n = -(2 ** (bits - 1)); n < 2 ** (bits - 1); n++) {
      const p = toBinary(n, bits);
      assert.equal(p.length, bits);
      seen.add(p);
      assert.equal(fromBinary(p), n);
    }
    assert.equal(seen.size, 2 ** bits);
  }
});

test('empty text, or characters other than 0 and 1, throw a RangeError', () => {
  assert.throws(() => fromBinary(''), RangeError);
  assert.throws(() => fromBinary('102'), RangeError);
  assert.throws(() => fromBinary('0b101'), RangeError);
});

Interview questions

Warm-up (fresher): What is two’s complement, and why do computers use it to store negative integers?

In n-bit two’s complement the top bit has the weight −2ⁿ⁻¹ and every other bit its usual positive weight, so 8 bits hold −128 to 127 and 11111011 is −128 + 123 = −5. To negate a number, invert its bits and add 1, which is the same as computing 2ⁿ − x. Computers use it because addition, subtraction and multiplication then need one circuit for signed and unsigned numbers: the bits of the result are the same, only the reading differs, and the carry out of the top bit is dropped. It also has a single zero, unlike sign and magnitude, which has +0 and −0. The price is a lopsided range: there is one more negative number than positive, so negating the most negative value overflows back to itself.

Warm-up (fresher to mid-level): How does an arithmetic right shift differ from a logical one?

Both move the bits k places to the right and drop the k lowest bits; they differ in what fills the k places on the left. A logical shift fills them with zeros, so it treats the pattern as unsigned. An arithmetic shift copies the sign bit, so a negative number stays negative and the result is the number divided by 2ᵏ rounded down: -7 >> 1 is −4, while -7 / 2 is −3 in Java, C++ and Go, which round towards zero. Java and JavaScript have both, >> arithmetic and >>> logical. C++ shifts signed types arithmetically and unsigned types logically, and Go chooses by type in the same way. Python has only an arithmetic >>, because its integers have no fixed width; mask to a width first to get a logical shift.

Key takeaways

• In binary each position is worth twice the one to its right; one hexadecimal digit is exactly four bits.
• In n-bit two’s complement the top bit weighs −2ⁿ⁻¹, so the range is −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1, and −x is stored as 2ⁿ − x, which is “invert and add one”.
• A sum of two numbers with the same sign that comes out with the other sign has overflowed.
• Java and Go wrap on overflow by definition; C++ signed overflow is undefined behaviour, and an optimiser may assume it never happens; Python’s integers grow; JavaScript wraps only inside its 32-bit bitwise operators and loses exactness above 2⁵³ − 1.
• >> on a negative number rounds down where division rounds towards zero; >>> and unsigned types shift in zeros; shift counts are reduced modulo the width in Java and JavaScript, unlimited in Go and Python, and undefined in C++ once they reach the width.