TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
count_of_set_bits.cpp
Go to the documentation of this file.
1
18#include <cassert>
19#include <cstdint>
20#include <iostream>
25namespace bit_manipulation {
32namespace count_of_set_bits {
38std::uint64_t countSetBits(
39 std ::uint64_t n) { // uint64_t is preferred over int so that
40 // no Overflow can be there.
41 //It's preferred over int64_t because it Guarantees that inputs are always non-negative,
42 //which matches the algorithmic problem statement.
43 //set bit counting is conceptually defined only for non-negative numbers.
44 //Provides a type Safety: Using an unsigned type helps prevent accidental negative values,
45
46 std::uint64_t count = 0; // "count" variable is used to count number of set-bits('1')
47 // in binary representation of number 'n'
48 //Count is uint64_t because it Prevents theoretical overflow if someone passes very large integers.
49 // Behavior stays the same for all normal inputs.
50 // Safer for edge cases.
51
52 while (n != 0) {
53 ++count;
54 n = (n & (n - 1));
55 }
56 return count;
57 // Why this algorithm is better than the standard one?
58 // Because this algorithm runs the same number of times as the number of
59 // set-bits in it. Means if my number is having "3" set bits, then this
60 // while loop will run only "3" times!!
61}
62} // namespace count_of_set_bits
63} // namespace bit_manipulation
64
65static void test() {
66 // n = 4 return 1
68 // n = 6 return 2
70 // n = 13 return 3
72 // n = 9 return 2
74 // n = 15 return 4
76 // n = 25 return 3
78 // n = 97 return 3
80 // n = 31 return 5
82 std::cout << "All test cases successfully passed!" << std::endl;
83}
88int main() {
89 test(); // run self-test implementations
90 return 0;
91}
int main()
Main function.
std::uint64_t countSetBits(std ::uint64_t n)
The main function implements set bit count.
static void test()
Self-test implementations.
for std::string
Functions for the count sets bits implementation.