Sum of n numbers with exactly 2 active bits set

In this article, we will explore a program to find the sum of n numbers that have exactly two active bits set in their binary representation. An "active bit" refers to a set bit (1) in the binary representation of a number. For example, the number 3 has two active bits (11 in binary), while the number 5 also has two active bits (101 in binary).

Problem Statement

The task is to find the sum of all numbers with exactly two active bits among the first n positive integers.

Example with n = 10: To better understand the problem, let's find the sum of all numbers with exactly two active bits among the first 10 positive integers.

• Binary representation of numbers with exactly two active bits:

```3 (11)
5 (101)
6 (110)
9 (1001)
10 (1010)
12 (1100)
17 (10001)
18 (10010)
20 (10100)
24 (11000)```
• Sum of the above numbers: 3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 = 124

Another example, if n = 6, the numbers with exactly 2 active bits set in their binary representation are:

``````// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100``````

Result 45 = [3+5+6+9+10+12].

Pseudocode

Before diving into the algorithm, let's define the pseudocode for a function named `twoActiveBits`:

``````twoActiveBits(n):
sum = 0
num = 1
count = n
temp = 1
while count > 0:
num = num << 1
while temp < num and count > 0:
sum = sum + (num | temp)
temp = temp << 1
count = count - 1
temp = 1
print "Given n  : ", n
print "Result   : ", sum
``````

Algorithm Explanation

1. Initialize the variables `sum`, `num`, `count`, and `temp`.
2. Loop while `count > 0`.
3. Left-shift `num` by 1 (equivalent to multiplying `num` by 2) to get the next number with two active bits.
4. Inner loop: While `temp` is less than `num` and `count > 0`, calculate the sum by performing a bitwise OR operation between `num` and `temp` and add it to the `sum`.
5. Left-shift `temp` by 1 (equivalent to multiplying `temp` by 2) to get the next number with a single active bit.
6. Decrement `count` by 1 to keep track of the remaining numbers to be processed.
7. Repeat steps 3-6 until all required numbers have been added to the `sum`.
8. Print the value of `n` and the final calculated `sum`.

Code Solution

``````// C Program for
// Sum of n numbers with exactly 2 active bits set
#include <stdio.h>

void twoActiveBits(int n)
{
int count = n;
int temp = 1;
int num = 1;
int sum = 0;
while (count > 0)
{
num = (num << 1);
while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count--;
}
temp = 1;
}
// Display number of element
printf(" Given n  : %d\n", n);
// Display calculate sum
printf(" Result   : %d\n", sum);
}
int main(int argc, char
const *argv[])
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
twoActiveBits(10);
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
twoActiveBits(30);
return 0;
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````/*
Java Program
Sum of n numbers with exactly 2 active bits set
*/
public class BinaryBits
{
public void twoActiveBits(int n)
{
int count = n;
int temp = 1;
int num = 1;
int sum = 0;

while (count > 0)
{
num = (num << 1);

while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count--;
}
temp = 1;
}
// Display number of element
System.out.println(" Given n  : " + n);
// Display calculate sum
System.out.println(" Result   : " + sum);
}
public static void main(String[] args)
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Sum of n numbers with exactly 2 active bits set
*/
class BinaryBits
{
public: void twoActiveBits(int n)
{
int count = n;
int temp = 1;
int num = 1;
int sum = 0;
while (count > 0)
{
num = (num << 1);
while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count--;
}
temp = 1;
}
// Display number of element
cout << " Given n  : " << n << endl;
// Display calculate sum
cout << " Result   : " << sum << endl;
}
};
int main()
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
return 0;
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````// Include namespace system
using System;
/*
Csharp Program
Sum of n numbers with exactly 2 active bits set
*/
public class BinaryBits
{
public void twoActiveBits(int n)
{
int count = n;
int temp = 1;
int num = 1;
int sum = 0;
while (count > 0)
{
num = (num << 1);
while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count--;
}
temp = 1;
}
// Display number of element
Console.WriteLine(" Given n  : " + n);
// Display calculate sum
Console.WriteLine(" Result   : " + sum);
}
public static void Main(String[] args)
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````package main
import "fmt"
/*
Go Program
Sum of n numbers with exactly 2 active bits set
*/
type BinaryBits struct {}
func getBinaryBits() * BinaryBits {
var me *BinaryBits = &BinaryBits {}
return me
}
func(this BinaryBits) twoActiveBits(n int) {
var count int = n
var temp int = 1
var num int = 1
var sum int = 0
for (count > 0) {
num = (num << 1)
for (temp < num && count > 0) {
sum += (num | temp)
temp = temp << 1
count--
}
temp = 1
}
// Display number of element
fmt.Println(" Given n  : ", n)
// Display calculate sum
fmt.Println(" Result   : ", sum)
}
func main() {
var task * BinaryBits = getBinaryBits()
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````<?php
/*
Php Program
Sum of n numbers with exactly 2 active bits set
*/
class BinaryBits
{
public	function twoActiveBits(\$n)
{
\$count = \$n;
\$temp = 1;
\$num = 1;
\$sum = 0;
while (\$count > 0)
{
\$num = (\$num << 1);
while (\$temp < \$num && \$count > 0)
{
\$sum += (\$num | \$temp);
\$temp = \$temp << 1;
\$count--;
}
\$temp = 1;
}
// Display number of element
echo(" Given n  : ".\$n.
"\n");
// Display calculate sum
echo(" Result   : ".\$sum.
"\n");
}
}

function main()
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}
main();``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````/*
Node JS Program
Sum of n numbers with exactly 2 active bits set
*/
class BinaryBits
{
twoActiveBits(n)
{
var count = n;
var temp = 1;
var num = 1;
var sum = 0;
while (count > 0)
{
num = (num << 1);
while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count--;
}
temp = 1;
}
// Display number of element
console.log(" Given n  : " + n);
// Display calculate sum
console.log(" Result   : " + sum);
}
}

function main()
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}
main();``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````#    Python 3 Program
#    Sum of n numbers with exactly 2 active bits set
class BinaryBits :
def twoActiveBits(self, n) :
count = n
temp = 1
num = 1
sum = 0
while (count > 0) :
num = (num << 1)
while (temp < num and count > 0) :
sum += (num | temp)
temp = temp << 1
count -= 1

temp = 1

#  Display number of element
print(" Given n  : ", n)
#  Display calculate sum
print(" Result   : ", sum)

def main() :
#  Test A
#  n = 10
#  --------------
#     Binary
#  3  11
#  5  101
#  6  110
#  9  1001
#  10  1010
#  12  1100
#  17  10001
#  18  10010
#  20  10100
#  24  11000
#   [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
#  ------------------------------------------------
#  Sum : 124
#  Test B
#  num = 30
#  --------------
#     Binary
#  3  11
#  5  101
#  6  110
#  9  1001
#  10  1010
#  12  1100
#  17  10001
#  18  10010
#  20  10100
#  24  11000
#  33  100001
#  34  100010
#  36  100100
#  40  101000
#  48  110000
#  65  1000001
#  66  1000010
#  68  1000100
#  72  1001000
#  80  1010000
#  96  1100000
#  129  10000001
#  130  10000010
#  132  10000100
#  136  10001000
#  144  10010000
#  160  10100000
#  192  11000000
#  257  100000001
#  258  100000010
#  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
#   34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
#   129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
#  ---------------------------------------------------
#  Sum : 2300

if __name__ == "__main__": main()``````

Output

`````` Given n  :  10
Result   :  124
Given n  :  30
Result   :  2300``````
``````#    Ruby Program
#    Sum of n numbers with exactly 2 active bits set
class BinaryBits
def twoActiveBits(n)
count = n
temp = 1
num = 1
sum = 0
while (count > 0)
num = (num << 1)
while (temp < num && count > 0)
sum += (num | temp)
temp = temp << 1
count -= 1
end

temp = 1
end

#  Display number of element
print(" Given n  : ", n, "\n")
#  Display calculate sum
print(" Result   : ", sum, "\n")
end

end

def main()
#  Test A
#  n = 10
#  --------------
#     Binary
#  3  11
#  5  101
#  6  110
#  9  1001
#  10  1010
#  12  1100
#  17  10001
#  18  10010
#  20  10100
#  24  11000
#   [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
#  ------------------------------------------------
#  Sum : 124
#  Test B
#  num = 30
#  --------------
#     Binary
#  3  11
#  5  101
#  6  110
#  9  1001
#  10  1010
#  12  1100
#  17  10001
#  18  10010
#  20  10100
#  24  11000
#  33  100001
#  34  100010
#  36  100100
#  40  101000
#  48  110000
#  65  1000001
#  66  1000010
#  68  1000100
#  72  1001000
#  80  1010000
#  96  1100000
#  129  10000001
#  130  10000010
#  132  10000100
#  136  10001000
#  144  10010000
#  160  10100000
#  192  11000000
#  257  100000001
#  258  100000010
#  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
#   34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
#   129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
#  ---------------------------------------------------
#  Sum : 2300
end

main()``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300
``````
``````/*
Scala Program
Sum of n numbers with exactly 2 active bits set
*/
class BinaryBits()
{
def twoActiveBits(n: Int): Unit = {
var count: Int = n;
var temp: Int = 1;
var num: Int = 1;
var sum: Int = 0;
while (count > 0)
{
num = (num << 1);
while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count -= 1;
}
temp = 1;
}
// Display number of element
println(" Given n  : " + n);
// Display calculate sum
println(" Result   : " + sum);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BinaryBits = new BinaryBits();
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````
``````/*
Swift 4 Program
Sum of n numbers with exactly 2 active bits set
*/
class BinaryBits
{
func twoActiveBits(_ n: Int)
{
var count: Int = n;
var temp: Int = 1;
var num: Int = 1;
var sum: Int = 0;
while (count > 0)
{
num = (num << 1);
while (temp < num && count > 0)
{
sum += (num | temp);
temp = temp << 1;
count -= 1;
}
temp = 1;
}
// Display number of element
print(" Given n  : ", n);
// Display calculate sum
print(" Result   : ", sum);
}
}
func main()
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}
main();``````

Output

`````` Given n  :  10
Result   :  124
Given n  :  30
Result   :  2300``````
``````/*
Kotlin Program
Sum of n numbers with exactly 2 active bits set
*/
class BinaryBits
{
fun twoActiveBits(n: Int): Unit
{
var count: Int = n;
var temp: Int = 1;
var num: Int = 1;
var sum: Int = 0;
while (count > 0)
{
num = (num shl 1);
while (temp < num && count > 0)
{
sum += (num or temp);
temp = temp shl 1;
count -= 1;
}
temp = 1;
}
// Display number of element
println(" Given n  : " + n);
// Display calculate sum
println(" Result   : " + sum);
}
}
fun main(args: Array < String > ): Unit
{
// Test A
// n = 10
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
//  [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24]
// ------------------------------------------------
// Sum : 124
// Test B
// num = 30
// --------------
//    Binary
// 3  11
// 5  101
// 6  110
// 9  1001
// 10  1010
// 12  1100
// 17  10001
// 18  10010
// 20  10100
// 24  11000
// 33  100001
// 34  100010
// 36  100100
// 40  101000
// 48  110000
// 65  1000001
// 66  1000010
// 68  1000100
// 72  1001000
// 80  1010000
// 96  1100000
// 129  10000001
// 130  10000010
// 132  10000100
// 136  10001000
// 144  10010000
// 160  10100000
// 192  11000000
// 257  100000001
// 258  100000010
// [3 + 5 + 6 + 9 + 10 + 12 + 17 + 18 + 20 + 24 + 33 +
//  34 + 36 + 40 + 48 + 65 + 66 + 68 + 72 + 80 + 96 +
//  129 + 130 + 132 + 136 + 144 + 160 + 192 + 257 + 258]
// ---------------------------------------------------
// Sum : 2300
}``````

Output

`````` Given n  : 10
Result   : 124
Given n  : 30
Result   : 2300``````

Resultant Output Explanation

For the test cases with `n = 10` and `n = 30`, we use the `twoActiveBits` function to find the sums of numbers with exactly two active bits among the first 10 and 30 positive integers, respectively.

• `twoActiveBits(10)` produces the output: Given n : 10 Result : 124

• `twoActiveBits(30)` produces the output: Given n : 30 Result : 2300

Time Complexity

The time complexity of the algorithm depends on the value of `n`. Let `k` be the number of bits needed to represent the largest number among the first `n` numbers. In the worst case, the outer loop runs for `n` iterations, and the inner loop runs for `k` iterations in each iteration of the outer loop. Therefore, the overall time complexity is O(n * k).

Finally

In this article, we have discussed a program to find the sum of numbers with exactly two active bits among the first n positive integers. We explained the problem, provided the pseudocode and algorithm, and demonstrated the outputs for two test cases. The algorithm's time complexity is also analyzed, allowing us to understand the efficiency of the solution for different input values.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.