Common Bit Manipulation Tricks - Learning Module

Loading content...

0/279

Extract the Rightmost Set Bit

Isolating the Lowest Set Bit

In the previous page, we learned to check the least significant bit using n & 1. But what if we need to find and isolate the rightmost bit that is actually set to 1, regardless of its position?

Consider the number 12 (binary: 1100). The rightmost set bit is at position 2 (the bit representing 4). How do we extract just that bit, producing the value 4?

This operation—extracting the rightmost set bit (also called the lowest set bit, least significant set bit, or LSB)—is surprisingly elegant. It uses a beautiful property of two's complement arithmetic that produces one of the most elegant expressions in bit manipulation: n & -n.

What You Will Learn

By the end of this page, you will understand why n & -n isolates the rightmost set bit, how two's complement negation creates the perfect mask, common applications including Fenwick Trees (Binary Indexed Trees), and how this forms the foundation for efficient bit counting algorithms.

The Two's Complement Magic

To understand why n & -n works, we need to trace through what happens when we negate a number in two's complement representation.

Recall: To negate a number in two's complement:

Flip all the bits (bitwise NOT)
Add 1 to the result

Let's trace through an example with n = 12 (binary: 01100 using 5 bits):

Step 1: Flip all bits (~n)

n  = 01100
~n = 10011

Step 2: Add 1

~n     = 10011
       +    1
-n     = 10100

Now AND them together:

n      = 01100
-n     = 10100
n & -n = 00100  ← Only the rightmost set bit remains!

Result: n & -n = 4, which is exactly the rightmost set bit of 12.

Why Does This Work?

The key insight is what happens when we add 1 after flipping bits. Starting from the right, all the trailing zeros in n become ones after flipping. When we add 1, the carry propagates through all these ones (turning them back to zeros) until it reaches the first zero (which was originally the rightmost set bit). This bit becomes 1. Everything to the left of this position is the opposite of what's in n, so they AND to zero. Only the rightmost set bit position has 1 in both n and -n.

Step-by-step analysis of n & -n
n	Binary n	~n	~n + 1 = -n	n & -n	Result
1	0001	1110	1111	0001	1
2	0010	1101	1110	0010	2
3	0011	1100	1101	0001	1
4	0100	1011	1100	0100	4
5	0101	1010	1011	0001	1
6	0110	1001	1010	0010	2
7	0111	1000	1001	0001	1
8	1000	0111	1000	1000	8
12	1100	0011	0100	0100	4
40	101000	010111	011000	001000	8

Mathematical Proof

Let's formalize why n & -n extracts the rightmost set bit with a rigorous proof.

Setup: Let n be a positive integer. We can write n in the form: $$n = a \cdot 2^{k+1} + 2^k$$

Where:

$k$ is the position of the rightmost set bit (0-indexed from the right)
$a$ represents all the bits to the left of position $k$
The bits at positions $0$ through $k-1$ are all zeros (by definition of rightmost set bit)

Step 1: Compute -n in two's complement $$-n = \sim n + 1$$

Let's analyze what $\sim n$ looks like:

Bits at positions $0$ through $k-1$: were 0s, now 1s
Bit at position $k$: was 1, now 0
Bits above position $k$: flipped (opposite of $a$)

Step 2: Add 1 to ~n When we add 1:

The trailing $k$ ones (positions 0 through $k-1$) become zeros with carry
The carry adds to position $k$ (which was 0), making it 1
Bits above position $k$ remain as the complement of $a$

Step 3: Compute n & -n

Bits at positions 0 through $k-1$: 0 in both, result is 0
Bit at position $k$: 1 in both, result is 1
Bits above position $k$: $a$ in $n$, complement of $a$ in $-n$, AND gives 0

Result: Only the bit at position $k$ survives, giving us $2^k$—the rightmost set bit.

$$n & (-n) = 2^k$$

Where $k$ is the index of the rightmost set bit in $n$.

Edge Case: Zero

When n = 0, there are no set bits. In this case, -0 = 0 in two's complement (with overflow), and 0 & 0 = 0. The result correctly indicates 'no rightmost set bit' by returning 0.

Alternative Expression: n & ~(n-1)

There's an equivalent expression that achieves the same result:

$$\text{Rightmost Set Bit} = n & \ \sim(n-1)$$

Let's verify this with n = 12 (binary: 1100):

n     = 1100
n-1   = 1011  (subtract 1, borrows flip trailing zeros and the first 1)
~(n-1)= 0100  (flip to get the mask)
n & ~(n-1) = 0100  ← Same result!

Why does this work?

When we subtract 1 from n:

The rightmost set bit becomes 0
All trailing zeros become 1s
Everything to the left stays the same

When we complement (n-1):

The rightmost set bit position becomes 1
All trailing positions become 0
Everything to the left becomes the complement

ANDing with n zeros out everything except the rightmost set bit position.

n & -n

•Simpler expression — Only 2 operands
•Fewer operations — Negation + AND
•More common — Standard idiom in competitive programming
•Direct intent — Shows we're using two's complement property

n & ~(n-1)

•More intuitive — Can trace the logic step by step
•Avoids negation — Works in languages without easy unary minus
•Educational value — Shows the n-1 relationship clearly
•Equivalent speed — Same number of CPU operations

In practice, n & -n is more commonly used due to its brevity. Both expressions compile to equally efficient machine code on modern processors.

Implementation and Examples

Let's implement functions to extract the rightmost set bit and explore various use cases:

rightmost_set_bit.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def rightmost_set_bit(n: int) -> int:
    """
    Extract the rightmost set bit from n.
    
    Returns the value of the rightmost set bit (a power of 2).
    Returns 0 if n is 0 (no set bits).
    
    Time Complexity: O(1)
    Space Complexity: O(1)
    
    Examples:
        rightmost_set_bit(12)  # 12 = 1100₂ → returns 4 (0100₂)
        rightmost_set_bit(10)  # 10 = 1010₂ → returns 2 (0010₂)
        rightmost_set_bit(1)   # 1 = 0001₂  → returns 1 (0001₂)
        rightmost_set_bit(0)   # 0 = 0000₂  → returns 0
    """
    return n & -n
 
 
def rightmost_set_bit_position(n: int) -> int:
    """
    Get the position (0-indexed) of the rightmost set bit.
    
    Returns -1 if n is 0 (no set bits).
    
    Examples:
        rightmost_set_bit_position(12)  # returns 2 (bit at position 2)
        rightmost_set_bit_position(10)  # returns 1 (bit at position 1)
        rightmost_set_bit_position(8)   # returns 3 (bit at position 3)
    """
    if n == 0:
        return -1
    
    rsb = n & -n
    position = 0
    while rsb > 1:
        rsb >>= 1
        position += 1
    return position
 
 
def rightmost_set_bit_position_log(n: int) -> int:
    """
    Get the position using logarithm (faster for large numbers in Python).
    Note: Python's bit_length() is optimized for this.
    """
    if n == 0:
        return -1
    return (n & -n).bit_length() - 1
 
 
# Demonstration
print("n     | Binary     | n & -n | RSB Value | RSB Position")
print("-" * 60)
test_values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 16, 24, 40, 100]
for n in test_values:
    rsb = rightmost_set_bit(n)
    pos = rightmost_set_bit_position(n)
    binary = format(n, '08b') if n >= 0 else 'negative'
    print(f"{n:5} | {binary} | {rsb:6} | {rsb:9} | {pos}")
 
 
# Verify both methods give same position
print("
Verifying position methods are equivalent:")
for n in range(1, 1000):
    assert rightmost_set_bit_position(n) == rightmost_set_bit_position_log(n)
print("✓ All positions match!")

Critical Application: Fenwick Trees (Binary Indexed Trees)

The n & -n operation is the core building block of Fenwick Trees (also known as Binary Indexed Trees or BITs)—a data structure that supports efficient prefix sum queries and point updates in O(log n) time.

Why is the rightmost set bit important for Fenwick Trees?

In a Fenwick Tree, each index i is responsible for a range of elements. The size of this range is determined by the rightmost set bit of i:

Index 1 (binary: 001) → responsible for 1 element
Index 2 (binary: 010) → responsible for 2 elements
Index 3 (binary: 011) → responsible for 1 element
Index 4 (binary: 100) → responsible for 4 elements
Index 6 (binary: 110) → responsible for 2 elements
Index 8 (binary: 1000) → responsible for 8 elements

Update Operation: To update index i, we also need to update all indices that include i in their range:

i += (i & -i)  // Move to next index that includes this one

Query Operation: To query the prefix sum up to index i, we sum values at decreasing indices:

i -= (i & -i)  // Move to the previous index in the tree

fenwick_tree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class FenwickTree:
    """
    Binary Indexed Tree (Fenwick Tree) implementation.
    
    Supports:
    - Point updates in O(log n)
    - Prefix sum queries in O(log n)
    - Range sum queries in O(log n)
    
    The key insight: i & -i gives the lowest set bit of i,
    which determines the range responsibility of each index.
    """
    
    def __init__(self, n: int):
        """Initialize a Fenwick Tree of size n (1-indexed)."""
        self.n = n
        self.tree = [0] * (n + 1)  # 1-indexed, tree[0] unused
    
    def update(self, i: int, delta: int) -> None:
        """
        Add delta to element at index i (1-indexed).
        
        We traverse upward through the tree, updating all nodes
        that include index i in their range.
        
        The key operation: i += (i & -i)
        This moves us to the next index whose range includes i.
        """
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i  # ← The magic: add the rightmost set bit
    
    def prefix_sum(self, i: int) -> int:
        """
        Get the sum of elements from index 1 to i (inclusive).
        
        We traverse downward through the tree, accumulating
        sums from each responsible node.
        
        The key operation: i -= (i & -i)
        This moves us to the previous node in the tree structure.
        """
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i  # ← The magic: subtract the rightmost set bit
        return total
    
    def range_sum(self, left: int, right: int) -> int:
        """Get the sum of elements from index left to right (inclusive)."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)
    
    def visualize_tree(self) -> None:
        """Visualize the ranges each index is responsible for."""
        print("
Fenwick Tree Structure:")
        print("Index | Binary  | RSB | Range Size | Responsible For")
        print("-" * 60)
        for i in range(1, self.n + 1):
            rsb = i & -i
            range_size = rsb
            range_start = i - rsb + 1
            binary = format(i, '04b')
            print(f"  {i:2}  | {binary}   |  {rsb}  |     {range_size}      | [{range_start}, {i}]")
 
 
# Demonstration
print("=== Fenwick Tree Demo ===
")
 
# Create a Fenwick Tree and add some values
ft = FenwickTree(8)
 
# Original array: [_, 3, 2, 5, 1, 4, 2, 3, 1] (1-indexed)
values = [3, 2, 5, 1, 4, 2, 3, 1]
for i, v in enumerate(values, 1):
    ft.update(i, v)
 
print("Original values: [3, 2, 5, 1, 4, 2, 3, 1]")
print()
 
# Query prefix sums
print("Prefix sums:")
for i in range(1, 9):
    print(f"  Sum[1..{i}] = {ft.prefix_sum(i)}")
 
print()
print("Range queries:")
print(f"  Sum[3..6] = {ft.range_sum(3, 6)}")  # 5 + 1 + 4 + 2 = 12
print(f"  Sum[2..5] = {ft.range_sum(2, 5)}")  # 2 + 5 + 1 + 4 = 12
 
# Visualize the tree structure
ft.visualize_tree()

Why Fenwick Trees Are Elegant

The Fenwick Tree is a perfect example of how understanding bit manipulation leads to elegant data structures. The entire tree navigation—both updates and queries—relies on the simple operation of adding or subtracting the rightmost set bit. No explicit tree pointers, no complex node structures—just arithmetic on indices.

More Applications

Beyond Fenwick Trees, the rightmost set bit operation appears in several other contexts:

Practical Applications

•Brian Kernighan's Algorithm — Count set bits by repeatedly clearing the rightmost set bit. Uses n & (n-1) which is closely related.
•Finding Trailing Zeros — The position of the rightmost set bit equals the number of trailing zeros. Useful in many algorithms.
•Power of Two Check — If n & -n == n, then n has exactly one set bit, making it a power of two.
•Bitwise GCD Optimization — Some GCD algorithms use the rightmost set bit to factor out powers of 2 efficiently.
•Memory Alignment — Finding the lowest set bit helps determine alignment requirements.
•Gray Code Computation — Gray codes use bit position information for efficient computation.
•Subset Enumeration — When iterating through subsets, the rightmost set bit often determines the next element to add/remove.

more_applications.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# Application 1: Check if n is a power of two
def is_power_of_two(n: int) -> bool:
    """
    A number is a power of 2 if and only if it has exactly one set bit.
    If n & -n equals n itself, then n has only one set bit.
    """
    return n > 0 and (n & -n) == n
 
# Alternative (more common): use n & (n-1)
def is_power_of_two_alt(n: int) -> bool:
    """If removing the rightmost set bit leaves 0, only one bit was set."""
    return n > 0 and (n & (n - 1)) == 0
 
print("Power of Two Check:")
for n in [1, 2, 3, 4, 5, 6, 7, 8, 16, 17, 32, 100, 128]:
    print(f"  {n:3}: {is_power_of_two(n)}")
print()
 
 
# Application 2: Count trailing zeros
def count_trailing_zeros(n: int) -> int:
    """
    Count trailing zeros = position of rightmost set bit.
    """
    if n == 0:
        return -1  # or return bit width for "all zeros"
    return (n & -n).bit_length() - 1
 
print("Trailing Zeros Count:")
for n in [1, 2, 4, 8, 12, 24, 40, 48]:
    binary = format(n, '08b')
    print(f"  {n:3} ({binary}): {count_trailing_zeros(n)} trailing zeros")
print()
 
 
# Application 3: Binary GCD (Stein's Algorithm) uses this concept
def binary_gcd(a: int, b: int) -> int:
    """
    GCD using binary operations (Stein's Algorithm).
    Uses the rightmost set bit to factor out powers of 2.
    """
    if a == 0: return b
    if b == 0: return a
    
    # Factor out common powers of 2
    # common_twos = number of trailing zeros in (a | b)
    common_twos = ((a | b) & -(a | b)).bit_length() - 1
    a >>= count_trailing_zeros(a)  # Make a odd
    
    while b != 0:
        b >>= count_trailing_zeros(b)  # Make b odd
        if a > b:
            a, b = b, a  # Ensure a <= b
        b -= a
    
    return a << common_twos  # Restore common factors of 2
 
print("Binary GCD (Stein's Algorithm):")
test_pairs = [(48, 18), (100, 35), (56, 42), (1024, 256)]
for a, b in test_pairs:
    print(f"  GCD({a}, {b}) = {binary_gcd(a, b)}")

Edge Cases and Pitfalls

The n & -n operation is robust, but there are edge cases to be aware of:

Edge Cases to Consider

•Zero — 0 & -0 = 0. This is correct (no set bits), but ensure your code handles zero appropriately if you're looking for a position.
•Minimum Integer — In languages with fixed-width integers, the minimum negative value (e.g., -2³¹ for 32-bit int) has special behavior. -(-2³¹) overflows back to -2³¹ in two's complement, but n & -n still correctly gives 2³¹.
•Negative Numbers — n & -n works correctly for negative numbers too, returning the rightmost set bit. For example, -12 & 12 = 4 in Python.
•Unsigned vs Signed — In languages with unsigned integers, be aware of how negation is handled. The operation still works, but the interpretation may differ.

edge_cases.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Edge case demonstrations
 
# Case 1: Zero
n = 0
print(f"0 & -0 = {n & -n}")  # Output: 0
 
# Case 2: Negative numbers
n = -12
print(f"-12 in binary (last 8 bits): {format(n & 0xFF, '08b')}")
print(f"-12 & -(-12) = {n & -n}")  # Output: 4
 
# Case 3: Various negative numbers
print("
Negative number behavior:")
for n in [-1, -2, -3, -4, -7, -8, -12, -16]:
    rsb = n & -n
    print(f"  {n:3} & {-n:3} = {rsb}")
 
# Case 4: Edge case with minimum 32-bit integer simulation
import sys
if hasattr(sys, 'maxsize'):
    # Simulate 32-bit behavior
    MIN_INT32 = -2**31
    MAX_INT32 = 2**31 - 1
    
    # In Python, -(-2^31) doesn't overflow, but in Java/C++ it would
    print(f"
32-bit minimum: {MIN_INT32}")
    print(f"In Python: -({MIN_INT32}) = {-MIN_INT32}")
    
    # Mask to simulate 32-bit
    def to_int32(n):
        return ((n + 2**31) % 2**32) - 2**31
    
    print(f"32-bit simulation: rsb of MIN_INT32 = {to_int32(MIN_INT32) & to_int32(-MIN_INT32)}")

Language-Specific Behavior

In languages with fixed-width integers (C, C++, Java), negating the minimum integer value causes overflow. For 32-bit signed integers, -(-2³¹) = -2³¹ due to overflow. However, MIN_INT & -MIN_INT still gives 2³¹ (the sign bit), which is technically the rightmost set bit when interpreted as an unsigned value.

Connection to the Next Topic: Clearing Bits

We've learned to extract the rightmost set bit with n & -n. A closely related operation is to clear (remove) the rightmost set bit, transforming:

1100 (12) → 1000 (8)
1010 (10) → 1000 (8)
0111 (7)  → 0110 (6)

This operation uses the expression n & (n-1), which we'll explore in depth in the next page.

Preview of the relationship:

n & -n isolates the rightmost set bit (gives you the bit)
n & (n-1) clears the rightmost set bit (removes the bit)

These two operations are complementary and together form the foundation for efficient bit counting algorithms like Brian Kernighan's algorithm.

Extract vs Clear: Complementary Operations
n	Binary	n & -n (Extract)	n & (n-1) (Clear)
12	1100	0100 (4)	1000 (8)
10	1010	0010 (2)	1000 (8)
7	0111	0001 (1)	0110 (6)
8	1000	1000 (8)	0000 (0)
6	0110	0010 (2)	0100 (4)

Summary and Key Takeaways

We've explored one of the most elegant expressions in bit manipulation—extracting the rightmost set bit using n & -n. Let's consolidate the key insights:

Key Takeaways

•n & -n extracts the rightmost set bit — The result is a power of 2 representing the value of the lowest set bit.
•Two's complement makes it work — Negation flips all bits and adds 1, which creates a mask that isolates the rightmost set bit.
•Equivalent expression: n & ~(n-1) — Same result, different perspective on why it works.
•Critical for Fenwick Trees — The entire navigation of Binary Indexed Trees depends on adding/subtracting the rightmost set bit.
•Foundation for many algorithms — Power-of-two checks, trailing zero counts, bit counting, and more.
•O(1) time complexity — This is a single-instruction operation on most CPUs.

What's Next:

In the next page, we'll learn the complementary operation: clearing the rightmost set bit using n & (n-1). This technique is the heart of Brian Kernighan's bit counting algorithm and is equally important to master.

Page Complete

You now understand how to extract the rightmost set bit using two's complement properties. This elegant operation—just three characters: n & -n—enables efficient data structures like Fenwick Trees and forms the foundation for numerous algorithms. Next, we'll explore its complement: clearing the rightmost set bit.