AdvancedMath for DSABit Manipulation & Math
Two's complement: how negative numbers live in bits
−x is ~x + 1, so −1 is all ones. x & −x isolates the lowest set bit. And Python needs a mask to act like 32-bit ints.
The idea
Computers store negative integers as two's complement: flip every bit and add 1. In 8 bits, 5 = 00000101 and −5 = 11111011. Adding them gives 0 with the carry falling off the end, which is why the CPU can use one adder for both.
Handy consequences: −1 is all ones; x & −x keeps only the lowest set bit (used by Fenwick trees). Python ints are unbounded, so to mimic 32-bit you mask with & 0xFFFFFFFF and convert back if the top bit is set.
Worked example
x & −x for x = 12
- 12 = 01100. −12 = flip (10011) + 1 = 10100.
- 01100 & 10100 = 00100 = 4: the lowest set bit of 12.
In code (Python)
MASK = 0xFFFFFFFF
def to_int32(x):
x &= MASK
return x - (1 << 32) if x >> 31 else x
def add_without_plus(a, b): # Sum of Two Integers
a, b = a & MASK, b & MASK
while b:
a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
return to_int32(a)
def lowest_bit(x):
return x & -xO(32) per addition: constant.
How to spot it
- Bit problems with negative inputs, “without using + or −”, reversing or counting bits of signed ints.
Common mistakes
- Python loops forever on negative numbers in bit loops without a mask.
- Assuming >> on negatives fills with zeros: Python and Java's >> keep the sign.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →