Exercism c++ problem

Projects Programming
1

Hello,

I have to do this :

Your task is to count the number of 1 bits in the binary representation of a number.
Restrictions

Keep your hands off that bit-count functionality provided by your standard library! Solve this one yourself using other basic tools instead.

But how can I check if for example how many 1 there are in the number 5 without using bit operations ?

2

Re-read your assignment. It doesn't say you can't use bit operations. It says you cant use the "bit-count functionality provided by your standard library". Look into the C++ Bitwise Operators.

3

Maybe use the right shift operator in a loop and see what is in bit position 0 each time. Unsigned integers work best with bit shifts. Negative numbers are more tricky.

4
  • Also, you can use a Mask to examine bits.
5

We can count the number of set bits (1s) in the binary representation of a number without using any built-in bit-counting functions. A common and efficient way to do this is using Brian Kernighan's Algorithm .

The idea is to repeatedly turn off the rightmost set bit of the number until the number becomes 0. Each time we turn off a bit, we increment a counter. The operation n & (n - 1) clears the least significant set bit of n .

For example:
If n = 6 (binary 0110 ):

  1. n & (n - 1) => 0110 & 0101 => 0100 (n becomes 4, count = 1)
  2. n & (n - 1) => 0100 & 0011 => 0000 (n becomes 0, count = 2)
    The loop stops. The count is 2, which is correct for the number 6.
#include <iostream>

// Function to count set bits using Brian Kernighan's Algorithm
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // Clear the least significant set bit
        count++;
    }
    return count;
}
6

So much for @roelofw learning to catch his own fish. School Assignment: 0, Plagiarism: 1.

7

Modulus and division?

void setup() {
  Serial.begin(115200);
  uint32_t num = 65535; // number to test
  int cnt = 0;  // 1's counter
  while (num > 0) {
    if (num % 2 == 1) cnt++;
    num /= 2;   // short form of num = num / 2
  }
  Serial.println(cnt);
}

void loop() {
}
8

meh...

9

Indeed. He didn't even have to trouble himself tipping the problem into ChatGPT.

10

By this, they mean: "don't use __builtin_popcount()" or similar functions.
Primitive C/C++ Bit operations are fine.

11

look this over

output

11000101

void
prBin (
    unsigned val )
{
    for (unsigned mask = 0x80; mask; mask >>= 1)  {
        if (mask & val)
            Serial.print ("1");
        else
            Serial.print ("0");
    }
    Serial.println ();
}

void setup()
{
    Serial.begin (9600);

    prBin (0xC5);
}

void loop() { }
12

Since the OP has already been handed a ready made solution, I feel it will not be doing any harm to add yet another one and, anyway, I guess his professor will being seeing a stack of similar AI generated solutions.
Here I used Deep Seek to produce a solution based on a recursive lambda function which should distinguish it from the other solutions that will be provided. It looks plausible enough but I've not tested it.

#include <iostream>
#include <functional>  // Required for std::function

int main() {
    unsigned int number;
    std::cout << "Enter a number: ";
    std::cin >> number;

    // Recursive lambda (requires std::function)
    std::function<int(unsigned int)> count_ones = [&](unsigned int num) {
        return (num == 0) ? 0 : 1 + count_ones(num & (num - 1));
    };

    std::cout << "Number of 1 bits: " << count_ones(number) << std::endl;
    return 0;
}
13

no he hasn't.
it demonstrates concepts he may not be seeing

14

He has. In Post #5.

15

isn't that a pretty "obscure" approach

16

Post #7 shows a less obscure approach.

17

even that approach is odd, using math instead of logic.

i use that approach with awk which doesn't have bit operations

i think there's a more direct way using masking

18

Maybe something like this? :wink:

void setup()
{
    Serial.begin (9600);
    delay(1000);

    unsigned val = 123; // Input value

    int ones = 0;

    for (unsigned mask = 0x80; mask; mask >>= 1)  {
        ones += (mask & val) > 0 ? 1 : 0;
    }

    Serial.print("Number of ones: ");
    Serial.println(ones);
}

void loop() { }
19

The naive approach won't fly in your interview for that job you really want. It shows you been nowhere and haven't read beyond the end of your nose.

Courtesy of Claude. Extra points for spotting the BS items:

  1. Naive Method
  2. Recursion
  3. Kernighan’s Algorithm
  4. Looping Over Only Set Bits
  5. Table Lookup for Nibbles
  6. 128-entry Table for Byte Lookup
  7. Lookup Table
  8. GCC Built-in Function
  9. Divide-and-Conquer (Parallel Bit Count / HAKMEM Algorithm)
  10. SWAR (SIMD Within A Register)
  11. MIT HAKMEM Popcount
  12. Kernighan with Loop Unrolling
  13. AVX / SSE Intrinsics
  14. Parallel Algorithm with Carry-Save Adders
  15. Hardware Instruction Access (e.g. POPCNT)
  16. Recursive Bit Pairing
  17. Bit Manipulation with Floating Point Hack

a7

20

At least this because it was explicitly precluded as an acceptable solution in the OP and the later entries in that list also look unconvincing :

Incidentally, it the thread title "Exercise c++ problem" or "Exorcism c++ problem". The devil is, as always, in the detail.