Understanding n & (n - 1): A Bit Manipulation Magic Trick

The bitwise operation n & (n - 1) is a clever manipulation that turns off the rightmost set bit (1) in a binary number.

How It Works

Let’s break down the process:

1. When you subtract 1 from a number (n - 1), all bits after the rightmost 1 are inverted, and that rightmost 1 becomes 0
2. When you AND (&) this result with the original number, it effectively removes that rightmost 1 For example, let’s take the number 52:

n     = 52 = 110100
n - 1 = 51 = 110011
n & (n-1)  = 110000 = 48

Application

1. Counting Set Bits

function countSetBits(n) {
    let count = 0;
    while (n !== 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

console.log(countSetBits(7));   // 3 (binary: 111)
console.log(countSetBits(14));  // 3 (binary: 1110)

2. Removing Last Set Bit

function removeLastSetBit(n) {
   return n & (n - 1);
}

console.log(removeLastSetBit(52)); // 48