Count set bits

JavaView on GFG

Intuition

Count total set bits from 1 to n. Use pattern: bits in range [0, 2^k-1] = k * 2^(k-1).

Algorithm

1Find highest bit k. Count contribution of each bit position separately.
2For bit i: count = (n/(2^(i+1))) * 2^i + max(0, n%(2^(i+1)) - 2^i + 1).

Common Pitfalls

•O(log n) solution. Or Brian Kernighan per number: O(n log n). Use mathematical approach for large n.

Count set bits.java

Java

// Approach: Brian Kernighan's algorithm: repeatedly flip the lowest set bit (n &= n-1) and count.
// Alternatively use lookup table for O(1) per block.
// Time: O(log n) Space: O(1)
class Solution {
    public static int countSetBits(int n) {
        if (n == 0)
            return 0;

        // WHAT THE HELL ARE THESE LINES DOING ?

        // 17 -> nearest pow(2) which is < 17 -> 16
        // if u write binary from 15 to 1, u will find each position having (15+1)/2 ->
        // 8 set bits
        // so for _ _ _ _, each having 8 set bits -> total set bits from 1-15 => 8 * 4
        // => 32

        int p = Integer.highestOneBit(n); // largest power of 2 <= n // in this case => 16
        int x = Integer.numberOfTrailingZeros(p); // gives exponent // in this case => 4

        int bitsTill2x = x * (p >> 1); // 4 * (16 >> 1) => 4 * (8) = 32

        // so what all remains is to count for 17, 16
        // their contribution => 17 - 16 + 1 (2 set bits, basically => 10001 & 10000,
        // the 1s at leftmost are 2)
        int msbBits = n - p + 1;

        return bitsTill2x + msbBits + countSetBits(n - p);
    }
}

Was this solution helpful?