The lowest set bit of you can compute as: def lowbit(i): return i & (-i) Why does this work? In two's complement, is computed by flipping all bits of and adding .
This causes all bits below the lowest to flip back to , and the lowest remains. The AND isolates just that bit.
Example: (binary ) - (binary in two's complement, but the last 4 bits are ) - This operation is the heart of Fenwick Trees.
Every query and update uses it. Time: . Space: .