A common interview problem involves counting the number of 1 bits (set bits) in the binary representation of an integer. The key insight lies in understanding how computers store signed integers using two's complement notation.

The expression n &= (n - 1) is a powerful optimization that eliminates the rightmost set bit in each iteration. This works because subtracting 1 from a number flips all bits from the rightmost 1 to the end, including that 1 itself.

Solution Implementation

/**
 * Counts the number of set bits in an integer's binary representation
 * @param num The input integer
 * @return The count of 1s in the 32-bit binary representation
 */
int countSetBits(int num) {
    int bitCount = 0;
    while (num) {
        num &= (num - 1);
        bitCount++;
    }
    return bitCount;
}

Step-by-Step Walkthrough with n = 10

Binary representation: 0000 0000 0000 0000 0000 0000 0000 1010

First iteration:

• n = 10 (binary: 1010)
• n - 1 = 9 (binary: 1001)
• n &= (n-1) gives 8 (binary: 1000)
• bitCount becomes 1

Second iteration:

• n = 8 (binary: 1000)
• n - 1 = 7 (binary: 0111)
• n &= (n-1) gives 0 (binary: 0000)
• bitCount becomes 2

The loop terminates since n equals 0. Final result: 2 set bits.

Another Example with n = 13

Binary representation: 0000 0000 0000 0000 0000 0000 0000 1101

Iteration 1: n=13 (1101), n-1=12 (1100), result=12 (1100), count=1
Iteration 2: n=12 (1100), n-1=11 (1011), result=8  (1000), count=2
Iteration 3: n=8  (1000), n-1=7  (0111), result=0  (0000), count=3

Final result: 3 set bits.

Printing Binary Representation of an Integer

Another practical application involves displaying the full 32-bit binary representation of an integer.

#include <stdio.h>

void printBinary(int value) {
    for (int pos = 31; pos >= 0; pos--) {
        int shifted = value >> pos;
        
        if (shifted & 1) {
            printf("1");
        } else {
            printf("0");
        }
        
        // Add spacing every 8 bits for readability
        if (pos > 0 && pos % 8 == 0) {
            printf(" ");
        }
    }
    printf("\n");
}

int main() {
    int input;
    printf("Enter an integer: ");
    scanf("%d", &input);
    
    printBinary(input);
    return 0;
}

The algorithm iterates from the most significant bit (position 31) to the least significant bit (position 0). For each posision, it right-shifts the value and uses a bitwise AND with 1 to determine if that bit is set. Spaces are inserted every 8 bits to improve readability.

For input 10, the output would be: 00000000 00000000 00000000 00001010