Common Tricks - Learning Module

Loading content...

0/276

Clear the Rightmost Set Bit

Removing the Lowest Set Bit

In the previous page, we learned to extract the rightmost set bit using n & -n. The complementary operation is equally important: clearing (removing) the rightmost set bit while leaving all other bits unchanged.

Transforming:

1100 (12) → 1000 (8) — remove the rightmost 1
1010 (10) → 1000 (8) — remove the rightmost 1
0111 (7) → 0110 (6) — remove the rightmost 1

This operation uses the elegant expression n & (n-1), which is the heart of the famous Brian Kernighan's algorithm for counting set bits. Understanding why this works deepens your mastery of bit manipulation and opens doors to efficient problem-solving.

What You Will Learn

By the end of this page, you will understand why n & (n-1) clears the rightmost set bit, how this enables efficient bit counting with Brian Kernighan's algorithm, power-of-two checking in a single operation, and numerous practical applications in algorithm design.

Why n & (n-1) Works

To understand this technique, we need to examine what happens to a binary number when we subtract 1.

Key Insight: Subtracting 1 creates a complement pattern at the rightmost set bit.

When we compute n - 1:

The rightmost set bit becomes 0
All bits to the right of it (which were 0s) become 1s
All bits to the left remain unchanged

Example with n = 12 (binary: 1100):

n     = 1100
n - 1 = 1011  ← Notice: rightmost 1 becomes 0, trailing 0s become 1s

Now AND them:

n       = 1100
n - 1   = 1011
n&(n-1) = 1000  ← The rightmost set bit is cleared!

Why the AND clears only the rightmost set bit:

Left of rightmost set bit: Same in both n and n-1, so AND preserves them
At the rightmost set bit position: n has 1, n-1 has 0, AND gives 0
Right of rightmost set bit: n has 0s, n-1 has 1s, AND gives 0s

The result: all bits are preserved except the rightmost set bit, which becomes 0.

Step-by-step analysis of n & (n-1)
n	Binary n	Binary (n-1)	n & (n-1)	Result
1	0001	0000	0000	0
2	0010	0001	0000	0
3	0011	0010	0010	2
4	0100	0011	0000	0
5	0101	0100	0100	4
6	0110	0101	0100	4
7	0111	0110	0110	6
8	1000	0111	0000	0
10	1010	1001	1000	8
12	1100	1011	1000	8
15	1111	1110	1110	14

The Borrow Chain

Think of subtraction in binary. When you subtract 1 from a number ending in ...10...0, you need to borrow. The borrow propagates through all the trailing zeros until it reaches the rightmost 1, which becomes 0, and all the zeros it passed through become 1s. This borrow chain is exactly what creates the complement pattern.

Formal Proof

Let's prove rigorously that n & (n-1) clears the rightmost set bit.

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

Where:

$k$ is the position of the rightmost set bit (0-indexed)
$a$ represents all the bits to the left of position $k$
The $0$ term represents bits 0 through $k-1$, all of which are 0

Step 1: Compute n - 1 $$n - 1 = a \cdot 2^{k+1} + 2^k - 1$$

Since $2^k - 1 = 2^{k-1} + 2^{k-2} + \ldots + 2^1 + 2^0$: $$n - 1 = a \cdot 2^{k+1} + (2^{k-1} + 2^{k-2} + \ldots + 2^0)$$

In binary:

Bits above position $k$: same as in $n$ (equal to $a$)
Bit at position $k$: was 1, now 0
Bits below position $k$: were all 0, now all 1

Step 2: Compute n & (n-1)

Bits above position $k$: $a & a = a$ (preserved)
Bit at position $k$: $1 & 0 = 0$ (cleared!)
Bits below position $k$: $0 & 1 = 0$ (still 0)

Result: $$n & (n-1) = a \cdot 2^{k+1} = n - 2^k$$

The rightmost set bit ($2^k$) is removed, all other bits remain.

Edge Case: Zero

When n = 0, there are no set bits to clear. The expression 0 & (0-1) = 0 & (-1) = 0 (in two's complement, -1 is all 1s, but 0 AND anything is 0). The result correctly indicates 'no change' since there was no set bit to remove.

Brian Kernighan's Algorithm: Counting Set Bits

The most famous application of n & (n-1) is Brian Kernighan's algorithm for counting the number of set bits (1s) in an integer. This algorithm is elegant in its simplicity and efficiency.

The Insight: If n & (n-1) removes exactly one set bit, then we can count set bits by repeatedly applying this operation until the number becomes zero. The number of iterations equals the number of set bits.

Time Complexity: O(number of set bits), not O(number of bits)!

This is a significant improvement over the naive approach of checking each bit position, which always takes O(log n) or O(32/64) iterations.

brian_kernighan.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
def count_set_bits_naive(n: int) -> int:
    """
    Naive approach: check each bit position.
    Time: O(log n) or O(bit_width)
    """
    count = 0
    while n:
        count += n & 1  # Check LSB
        n >>= 1         # Shift right
    return count
 
 
def count_set_bits_kernighan(n: int) -> int:
    """
    Brian Kernighan's Algorithm: clear rightmost set bit repeatedly.
    
    Time: O(number of set bits) — only iterates once per set bit!
    Space: O(1)
    
    This is optimal: we do exactly as many operations as there are set bits.
    A number with only 2 set bits (like 2^30 + 2^0) takes only 2 iterations,
    not 30 iterations like the naive approach.
    """
    count = 0
    while n:
        n = n & (n - 1)  # Clear the rightmost set bit
        count += 1        # Count the removed bit
    return count
 
 
# Trace through execution
def count_set_bits_kernighan_verbose(n: int) -> int:
    """Same algorithm with step-by-step output."""
    print(f"Counting set bits in {n} (binary: {bin(n)})")
    print("-" * 50)
    
    original = n
    count = 0
    step = 0
    
    while n:
        step += 1
        n_before = n
        n = n & (n - 1)
        count += 1
        print(f"Step {step}: {n_before:6} ({bin(n_before):>12}) → {n:6} ({bin(n):>12})")
    
    print("-" * 50)
    print(f"Total set bits: {count}")
    return count
 
 
# Demonstrations
print("=== Brian Kernighan's Algorithm ===\n")
 
# Compare approaches on various numbers
test_numbers = [
    (15, "All 4 low bits set"),
    (8, "Single bit (power of 2)"),
    (7, "3 consecutive bits"),
    (1023, "10 consecutive bits"),
    (2**30 + 1, "Only 2 bits set, far apart"),
]
 
print("Comparison of approaches:\n")
for num, description in test_numbers:
    result = count_set_bits_kernighan(num)
    print(f"{description}:")
    print(f"  n = {num}")
    print(f"  Set bits = {result}")
    print(f"  Naive iterations: {num.bit_length()}")
    print(f"  Kernighan iterations: {result}")
    print()
 
# Verbose trace for a specific number
print("\n=== Detailed Trace ===\n")
count_set_bits_kernighan_verbose(156)  # 156 = 10011100 (4 set bits)

When Kernighan's Algorithm Shines

This algorithm is particularly efficient for sparse bit patterns (numbers with few set bits). For n = 2³⁰ + 1 (only 2 bits set), the naive approach takes 31 iterations, while Kernighan's takes just 2. In competitive programming and systems with many sparse numbers, this difference can be significant.

Power of Two Check: The Elegant Test

A natural consequence of n & (n-1) clearing the rightmost set bit is an elegant test for powers of 2:

Key Insight: A power of 2 has exactly one set bit. If we clear that single bit, we get zero.

$$n \text{ is a power of 2} \Leftrightarrow n > 0 \text{ and } n & (n-1) = 0$$

Examples:

8 = 1000₂: 8 & 7 = 1000 & 0111 = 0000 = 0 ✓ Power of 2
16 = 10000₂: 16 & 15 = 10000 & 01111 = 00000 = 0 ✓ Power of 2
12 = 1100₂: 12 & 11 = 1100 & 1011 = 1000 = 8 ✗ Not a power of 2
7 = 0111₂: 7 & 6 = 0111 & 0110 = 0110 = 6 ✗ Not a power of 2

power_of_two.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
62
63
64
65
66
67
def is_power_of_two(n: int) -> bool:
    """
    Check if n is a power of 2 using n & (n-1).
    
    A power of 2 has exactly one set bit.
    Clearing that bit results in 0.
    
    Time: O(1)
    Space: O(1)
    
    Examples:
        is_power_of_two(1)   # True (2^0)
        is_power_of_two(2)   # True (2^1)
        is_power_of_two(4)   # True (2^2)
        is_power_of_two(6)   # False
        is_power_of_two(0)   # False (special case)
        is_power_of_two(-4)  # False (negative)
    """
    return n > 0 and (n & (n - 1)) == 0
 
 
def is_power_of_two_verbose(n: int) -> bool:
    """Same check with explanation."""
    if n <= 0:
        print(f"  {n} ≤ 0, not a power of 2")
        return False
    
    result = n & (n - 1)
    binary_n = bin(n)
    binary_nm1 = bin(n - 1)
    binary_result = bin(result)
    
    print(f"  n     = {n:5} = {binary_n}")
    print(f"  n-1   = {n-1:5} = {binary_nm1}")
    print(f"  n&(n-1) = {result:3} = {binary_result}")
    
    if result == 0:
        print(f"  Result is 0 → {n} IS a power of 2")
        return True
    else:
        print(f"  Result is non-zero → {n} is NOT a power of 2")
        return False
 
 
# Demonstration
print("=== Power of Two Check ===\n")
 
test_values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 16, 31, 32, 64, 100, 128, 256]
 
print("Quick check results:")
for n in test_values:
    result = is_power_of_two(n)
    indicator = "✓" if result else " "
    print(f"  {indicator} {n:3}: {result}")
 
print("\nDetailed analysis:")
for n in [6, 8, 12, 16]:
    print(f"\nAnalyzing n = {n}:")
    is_power_of_two_verbose(n)
 
 
# Find all powers of 2 in a range
def powers_of_two_in_range(start: int, end: int) -> list:
    """Find all powers of 2 in [start, end] range."""
    return [n for n in range(start, end + 1) if is_power_of_two(n)]
 
print(f"\nPowers of 2 from 1 to 1000: {powers_of_two_in_range(1, 1000)}")

Powers of 2 Pattern

•1 = 1
•2 = 10
•4 = 100
•8 = 1000
•16 = 10000
•32 = 100000
•All have exactly one 1-bit

Non-Powers of 2

•3 = 11
•5 = 101
•6 = 110
•7 = 111
•9 = 1001
•10 = 1010
•Multiple 1-bits present

More Applications

The n & (n-1) operation enables several other useful techniques:

Practical Applications

•Round down to nearest power of 2 — Repeatedly clear rightmost bit until only one remains
•Check if exactly two bits are set — Apply twice; if result is 0, exactly two bits were set
•Subset enumeration — Each n & (n-1) gives the 'previous' subset in a specific ordering
•Memory alignment verification — Check if an address is aligned to a power-of-2 boundary
•Binary search optimization — Some implementations use bit manipulation for midpoint calculation
•Game state transitions — In games using bitmask states, this can represent 'removing' a piece or option

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
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
# Application 1: Round down to nearest power of 2
def round_down_to_power_of_2(n: int) -> int:
    """
    Find the largest power of 2 that is <= n.
    Clear bits one by one until only the highest bit remains.
    """
    if n <= 0:
        return 0
    
    # Keep clearing the rightmost set bit until only one remains
    while n & (n - 1):  # While more than one bit is set
        n = n & (n - 1)
    return n
 
 
# Application 2: Check if exactly k bits are set
def has_exactly_k_bits(n: int, k: int) -> bool:
    """Check if exactly k bits are set in n."""
    count = 0
    while n and count <= k:
        n = n & (n - 1)
        count += 1
    return count == k
 
 
# Application 3: Get all numbers with one fewer bit set
def subsets_with_one_less_bit(n: int) -> list:
    """
    Generate all numbers that can be formed by clearing
    exactly one bit from n.
    
    Example: 7 (111) → [6 (110), 5 (101), 3 (011)]
    """
    result = []
    temp = n
    while temp:
        bit = temp & -temp      # Get rightmost set bit
        result.append(n ^ bit)  # Clear that bit in original n
        temp = temp & (temp - 1)  # Move to next set bit
    return result
 
 
# Application 4: Binary representation journey
def bit_clearing_journey(n: int) -> list:
    """
    Show the sequence of numbers formed by repeatedly
    clearing the rightmost set bit.
    """
    journey = [n]
    while n:
        n = n & (n - 1)
        journey.append(n)
    return journey
 
 
# Demonstrations
print("=== Applications of n & (n-1) ===\n")
 
# Round down to power of 2
print("Round down to nearest power of 2:")
test_values = [1, 3, 5, 7, 8, 10, 15, 16, 17, 100, 1000]
for n in test_values:
    result = round_down_to_power_of_2(n)
    print(f"  {n:4} → {result}")
 
print()
 
# Check exact bit counts
print("Numbers with exactly 3 bits set (from 1-20):")
nums_with_3_bits = [n for n in range(1, 21) if has_exactly_k_bits(n, 3)]
for n in nums_with_3_bits:
    print(f"  {n} = {bin(n)}")
 
print()
 
# Subsets with one less bit
print("Subsets with one less bit:")
for n in [7, 13, 15]:
    subsets = subsets_with_one_less_bit(n)
    print(f"  {n} ({bin(n)}) → {[(s, bin(s)) for s in subsets]}")
 
print()
 
# Bit clearing journey
print("Bit clearing journey:")
for n in [7, 12, 15, 100]:
    journey = bit_clearing_journey(n)
    print(f"  {n}: {' → '.join(str(x) for x in journey)}")

Relationship Between n & -n and n & (n-1)

We've now learned two fundamental operations:

Operation	Expression	Result
Extract rightmost set bit	`n & -n`	Returns the value of the rightmost set bit
Clear rightmost set bit	`n & (n-1)`	Returns n with the rightmost set bit removed

These operations are complementary:

$$n = (n & (n-1)) + (n & -n)$$

The original number equals the number with the rightmost bit cleared, plus the value of that bit.

Example with n = 12:

12 & 11 = 8 (cleared version)
12 & -12 = 4 (extracted bit)
8 + 4 = 12 ✓

Understanding both operations and their relationship gives you a complete toolkit for manipulating the rightmost set bit in any way needed.

Extract vs Clear: Complete Comparison
n	Binary	n & -n (Extract)	n & (n-1) (Clear)	Verification
7	0111	1	6	6 + 1 = 7 ✓
8	1000	8	0	0 + 8 = 8 ✓
10	1010	2	8	8 + 2 = 10 ✓
12	1100	4	8	8 + 4 = 12 ✓
15	1111	1	14	14 + 1 = 15 ✓
24	11000	8	16	16 + 8 = 24 ✓

Mental Model

Think of it this way: n & -n answers 'What is the rightmost set bit?' while n & (n-1) answers 'What's left after removing it?' These two pieces always combine back to the original number.

Edge Cases and Pitfalls

While n & (n-1) is robust, there are edge cases to understand:

Edge Cases to Consider

•Zero — 0 & (-1) = 0. Zero has no set bits, so the result is zero. The power-of-two check correctly returns false for zero because we require n > 0.
•One — 1 & 0 = 0. Since 1 = 2⁰, clearing its only bit gives 0. Correctly identified as a power of 2.
•Negative numbers — The operation works mathematically, but interpretation differs. For -12 (in two's complement), (-12) & (-13) gives a predictable result, but 'power of 2' doesn't make sense for negatives.
•Overflow with n-1 — When n is the minimum negative integer (e.g., -2³¹ for 32-bit), subtracting 1 causes overflow. Handle with care in languages with fixed-width integers.

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
36
37
38
39
40
41
42
43
44
45
46
# Edge case analysis
 
print("Edge Cases for n & (n-1):\n")
 
# Case 1: Zero
n = 0
result = n & (n - 1)
print(f"n = 0:")
print(f"  0 & (-1) = {result}")
print(f"  (In Python, -1 has infinite 1-bits, but 0 AND anything = 0)")
print()
 
# Case 2: One
n = 1
result = n & (n - 1)
print(f"n = 1:")
print(f"  1 & 0 = {result}")
print(f"  1 is 2^0, clearing its only bit gives 0")
print()
 
# Case 3: Negative numbers
print("Negative numbers (32-bit two's complement simulation):")
import struct
 
def to_int32(n):
    """Simulate 32-bit signed integer."""
    return struct.unpack('i', struct.pack('I', n & 0xFFFFFFFF))[0]
 
for n in [-1, -2, -4, -8, -12]:
    result = n & (n - 1)
    print(f"  {n:4} & {n-1:4} = {result}")
print()
 
# Case 4: Powers of two test should exclude negative numbers
def is_power_of_two_safe(n: int) -> bool:
    """Safe power of 2 check that handles edge cases."""
    # Must be positive
    if n <= 0:
        return False
    # Standard check
    return (n & (n - 1)) == 0
 
print("Safe power of 2 check:")
test_cases = [0, 1, 2, 4, -4, -1, 8, 16, -16]
for n in test_cases:
    print(f"  is_power_of_two_safe({n:3}) = {is_power_of_two_safe(n)}")

Always Check for Zero/Negative

When using n & (n-1) == 0 to check for power of 2, always include an explicit check that n > 0. The expression n & (n-1) == 0 is also true for n = 0, but zero is not a power of 2.

Performance Considerations

Single Operation Cost:

The expression n & (n-1) compiles to just a few CPU instructions:

Subtract 1 from n (one instruction)
Bitwise AND with original n (one instruction)

This is O(1) with minimal constant factor, making it ideal for performance-critical code.

Brian Kernighan's Algorithm Performance:

For counting set bits:

Best case: O(1) — number has 1 set bit (like powers of 2)
Worst case: O(k) where k is the number of bits in the integer
Average case: O(k/2) for random integers (about half the bits are set on average)

Compared to alternatives:

Naive bit checking: Always O(k) iterations
Lookup table: O(k/8) with byte-wise lookup, but requires memory
Hardware popcount: O(1), fastest when available

When to use Brian Kernighan's:

When you expect sparse bit patterns (few 1s)
When counting is infrequent (not worth building lookup tables)
When portability matters (works everywhere, no special instructions needed)

Modern CPU Instructions

Most modern CPUs have hardware population count (popcount) instructions. In Python, this is n.bit_count(). In Java, Integer.bitCount(). These are faster than any software implementation. Use Brian Kernighan's algorithm when hardware support isn't available or when teaching/understanding the concept.

Summary and Key Takeaways

We've explored the powerful n & (n-1) operation—the complement to extracting the rightmost set bit. Let's consolidate the key insights:

Key Takeaways

•n & (n-1) clears the rightmost set bit — The borrow chain when subtracting 1 creates a perfect mask.
•Brian Kernighan's Algorithm — Count set bits in O(number of set bits) by repeatedly clearing the rightmost bit.
•Power of two check — n > 0 && (n & (n-1)) == 0 is the elegant one-liner test.
•Complementary to n & -n — Extract extracts the bit, clear removes it. Together: n = (n & (n-1)) + (n & -n).
•O(1) single operation — Just one subtraction and one AND, minimal overhead.
•Wide applicability — From bit counting to subset enumeration to memory alignment.

What's Next:

We've mastered operations on the rightmost set bit. In the next page, we'll learn to work with bits at arbitrary positions—checking, setting, clearing, and toggling specific bits using position-based masks. This extends our toolkit from just the rightmost bit to any bit we choose.

Page Complete

You now understand how to clear the rightmost set bit using n & (n-1), enabling efficient bit counting and power-of-two checks. Combined with the extract operation from the previous page, you have complete control over the rightmost set bit. Next, we'll extend this to manipulating bits at any position.