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

In the example above, the binary representation of 52 (110100) had its rightmost set bit at position 3. After applying n & (n - 1), the result (110000) has a 0 in that position. The rightmost 1 was cleared.

Application

1. Counting Set Bits

function countSetBits(n) {
  // Keep a running total of set bits we've found
  let count = 0;

  /*
   Loop until n becomes 0. Each iteration clears the rightmost set bit
   of n using the expression `n & (n - 1)`. That means the number of
   iterations equals the number of 1-bits in the original integer.

   Important JS note: bitwise operators in JavaScript operate on 32-bit
   signed integers.
  */
  while (n !== 0) {
    // Clear the lowest set bit of n. Example: n=0b110100 -> n-1=0b110011 -> n&(n-1)=0b110000
    n = n & (n - 1);

    // We removed one set bit, so increment the counter
    count++;
  }

  // The final count is the number of 1-bits in the original input
  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