count_of_set_bits.cpp

Go to the documentation of this file.

#include <cassert>   
#include <cstdint>
#include <iostream>  
namespace bit_manipulation {
namespace count_of_set_bits {
std::uint64_t countSetBits(
    std ::uint64_t n) {  // uint64_t is preferred over int so that
                        // no Overflow can be there.
                        //It's preferred over int64_t because it Guarantees that inputs are always non-negative, 
                        //which matches the algorithmic problem statement.
                        //set bit counting is conceptually defined only for non-negative numbers.
                        //Provides a type Safety: Using an unsigned type helps prevent accidental negative values,
 
    std::uint64_t count = 0;  // "count" variable is used to count number of set-bits('1')
                            // in binary representation of number 'n'
                            //Count is uint64_t because it Prevents theoretical overflow if someone passes very large integers.
                            //  Behavior stays the same for all normal inputs.
                            // Safer for edge cases.
 
    while (n != 0) {
        ++count;
        n = (n & (n - 1));
    }
    return count;
    // Why this algorithm is better than the standard one?
    // Because this algorithm runs the same number of times as the number of
    // set-bits in it. Means if my number is having "3" set bits, then this
    // while loop will run only "3" times!!
}
}  // namespace count_of_set_bits
}  // namespace bit_manipulation
 
static void test() {
    // n = 4 return 1
    assert(bit_manipulation::count_of_set_bits::countSetBits(4) == 1);
    // n = 6 return 2
    assert(bit_manipulation::count_of_set_bits::countSetBits(6) == 2);
    // n = 13 return 3
    assert(bit_manipulation::count_of_set_bits::countSetBits(13) == 3);
    // n = 9 return 2
    assert(bit_manipulation::count_of_set_bits::countSetBits(9) == 2);
    // n = 15 return 4
    assert(bit_manipulation::count_of_set_bits::countSetBits(15) == 4);
    // n = 25 return 3
    assert(bit_manipulation::count_of_set_bits::countSetBits(25) == 3);
    // n = 97 return 3
    assert(bit_manipulation::count_of_set_bits::countSetBits(97) == 3);
    // n = 31 return 5
    assert(bit_manipulation::count_of_set_bits::countSetBits(31) == 5);
    std::cout << "All test cases successfully passed!" << std::endl;
}
int main() {
    test();  // run self-test implementations
    return 0;
}