CountOne.cpp

#include <iostream>
#include <bitset>
using namespace std;

int countOne(unsigned int n) {
  int count = 0;
  while (n) {
    n = n & (n - 1);
    count++;
  }
  return count;
}

int countOneBasic(unsigned int n) {
  int count = 0;
  while (n) {
    if (n & 1) count++;
    n = n >> 1;
  }
  return count;
}

int countOneAdvanced(unsigned int n) {
  //cout << "n = " << (bitset<32>) n << endl;
  n = (n & 0x55555555) + (n >> 1 & 0x55555555);
  //cout << "n = " << (bitset<32>) n << endl;
  n = (n & 0x33333333) + (n >> 2 & 0x33333333);
  //cout << "n = " << (bitset<32>) n << endl;
  n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f);
  //cout << "n = " << (bitset<32>) n << endl;
  n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff);
  //cout << "n = " << (bitset<32>) n << endl;
  n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff);
  //cout << "n = " << (bitset<32>) n << endl;
  return n;
}

int main() {
  cout << "size of int: " << sizeof(int) << endl;
  cout << countOne(15437) << " == " << countOneBasic(15437)
    << " == " << countOneAdvanced(15437) << endl;
  cout << countOne(3) << " == " << countOneBasic(3)
    << " == " << countOneAdvanced(3) << endl;
  for (int i = 0; i < (1 << 23); i++) {
    int a = countOne(i);
    int b = countOneBasic(i);
    int c = countOneAdvanced(i);
    if (a != b || a != c) {
      cout << "ERROR: " << i << endl;
      cout << "a: " << a << endl;
      cout << "b: " << b << endl;
      cout << "c: " << c << endl;
      break;
    }
  }
  return 0;
}