AlgoScope

Lowest Set Bit

n and -n keeps only the lowest 1. It is the step a Fenwick tree takes.

Bit manipulation, algorithm, intermediate
The lowest set bit is 8, bit 3.0001021314051607bit
The lowest set bit is 8, bit 3.0001021314051607bit

Bit Manipulation: Isolate the lowest 1

Result, step 2 of 2

88 and -88 = 8, which is bit 3 alone. This is the step a Fenwick tree takes to find its parent.

How bit manipulation works

Cost

Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

Bit Manipulation covers these too, in the same run.