Two's Complement Explained

The carry flag is set when an unsigned addition or subtraction produces a result that does not fit in the destination width; it indicates an unsigned overflow. The overflow flag is set when a signed addition or subtraction produces a result outside the two's complement range; it indicates a signed overflow. You can have carry without overflow (adding two unsigned numbers that exceed the width but are both positive in two's complement), overflow without carry (adding two positives that become negative), both, or neither. Detect overflow on addition by checking if the signs of the operands are the same and the sign of the result differs.

In C, right shift of a negative signed value is implementation-defined per C17 6.5.7. On GCC and Clang, it is arithmetic, so the sign bit is copied, and -1 >> 1 is -1. To write portable code, avoid relying on the result for negative numbers. If you must, cast to unsigned, shift, then cast back, but be aware that conversion of a negative value to unsigned is well-defined only modulo 2^N. For portability, use unsigned right shifts (which fill with zeros) and handle the sign separately, or use memcpy to inspect the bit pattern.

Python integers have arbitrary precision, and bitwise operations emulate infinite two's complement. So -1 is represented as an infinite string of 1s. A right shift fills with 1s, so -1 >> 1 is still an infinite string of 1s, which is -1. But a bitwise AND with 0xFF masks the low 8 bits, keeping only the last 8 ones, which is 255. The mask truncates the infinite sign extension, so the result is positive. The rule: Python's shifts sign-extend infinitely, but bitwise AND/OR/XOR with a finite mask produces a non-negative result if the mask's high bit is 0.

A carry out occurs when the addition of the unsigned values produces a result of 256 or more, setting the carry flag. Overflow occurs when the addition of two signed values produces a result outside -128 to +127. For example, 127 + 1 = 128 in 8-bit: carry out is 0, overflow is 1 because 128 is out of signed range. 255 + 1 = 0 with carry out 1, overflow is 0 because as unsigned it is 256, as signed it is -1 + 1 = 0, which is fine. You can have both: 127 + 127 = 254, carry out 0, overflow 1. You cannot have overflow without the sign of the operands and result being misleading; check the signs.

Binary multiplication is shift-and-add: for each bit of the multiplier, if it is 1, add the multiplicand shifted left by that bit position; if 0, add nothing. For signed operands, use Booth's algorithm or convert to positive, multiply, then adjust the sign. Two's complement multiplication works directly if you extend the sign bits correctly and take the low N bits of the product for an N-bit result. Division is shift-and-subtract; for signed division, the quotient is truncated toward zero in C, so -7 / 2 = -3 (in C, integer division truncates toward zero, so -7 / 2 equals -3, and -7 % 2 equals -1). To do it by hand, compute the magnitude division, then apply the sign: if the signs differ, the quotient is negative, and the remainder takes the sign of the dividend.

Write the positive number in binary. Invert all bits, then add one. For example, -5 in 8 bits: +5 is 00000101, invert to 11111010, add 1 to get 11111011. To check, apply the same rule to the result: invert 11111011 to 00000100, add 1 to get 00000101, which is +5. The shortcut: copy from the right up to and including the first 1, then invert the rest. This works because adding 1 to a string of trailing zeros and a single 1 flips them all.

A logical right shift fills the vacated bits with zeros; it is used for unsigned values. An arithmetic right shift fills with the sign bit (the MSB), preserving the sign for negative numbers; it is used for signed values. In C, right shift of an unsigned value is always logical, but for signed values it is implementation-defined, though most compilers use arithmetic. Left shifts are the same for both, filling with zeros on the right, but overflow is undefined for signed left shifts in C. JavaScript's bitwise operators convert to 32-bit signed integers, so -1 >>> 0 gives 4294967295, but -1 >> 1 gives -1.