TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
count_of_set_bits.cpp File Reference

Implementation to [count number of set bits of a number] (https://www.geeksforgeeks.org/count-set-bits-in-an-integer/) in an integer. More...

#include <cassert>
#include <cstdint>
#include <iostream>
Include dependency graph for count_of_set_bits.cpp:

Go to the source code of this file.

Namespaces

namespace  bit_manipulation
 for std::string
namespace  count_of_set_bits
 Functions for the count sets bits implementation.

Functions

std::uint64_t bit_manipulation::count_of_set_bits::countSetBits (std ::uint64_t n)
 The main function implements set bit count.
static void test ()
int main ()
 Main function.

Detailed Description

Implementation to [count number of set bits of a number] (https://www.geeksforgeeks.org/count-set-bits-in-an-integer/) in an integer.

We are given an integer number. We need to calculate the number of set bits in it.

A binary number consists of two digits. They are 0 & 1. Digit 1 is known as set bit in computer terms. Worst Case Time Complexity: O(log n) Space complexity: O(1)

Author
Swastika Gupta
Prashant Thakur

Definition in file count_of_set_bits.cpp.

Function Documentation

◆ countSetBits()

std::uint64_t bit_manipulation::count_of_set_bits::countSetBits ( std ::uint64_t n)

The main function implements set bit count.

Parameters
nis the number whose set bit will be counted
Returns
total number of set-bits in the binary representation of number n

Definition at line 38 of file count_of_set_bits.cpp.

39 { // 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}

◆ main()

int main ( void )

Main function.

Returns
0 on exit

Definition at line 88 of file count_of_set_bits.cpp.

88 {
89 test(); // run self-test implementations
90 return 0;
91}
static void test()
Self-test implementations.

◆ test()

void test ( )
static

Definition at line 65 of file count_of_set_bits.cpp.

65 {
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}
std::uint64_t countSetBits(std ::uint64_t n)
The main function implements set bit count.