Advertisement
aaronhma

Count # of 1 bits using f(x) = x & (x - 1)

May 18th, 2022 (edited)
898
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int f(int x)
  6. {
  7.   return x & (x - 1);
  8. }
  9.  
  10. int countOnes(int f)
  11. {
  12.   int ans = 0;
  13.  
  14.   while (f) // break when f = 0
  15.   {
  16.     ans++;
  17.     f = ::f(f);
  18.   }
  19.  
  20.   return ans;
  21. }
  22.  
  23. int main()
  24. {
  25.   // f(101) = 100 = b1100100
  26.   // NOTE: f(x) >= 0 for the countOnes() to work
  27.   cout << countOnes(f(101)) << "\n"; // 3
  28.  
  29.   // Alternatively, you can use C++'s built-in function:
  30.   // cout << __builtin_popcount(f(101)) << "\n";
  31.  
  32.   return 0;
  33. }
Advertisement
RAW Paste Data Copied
Advertisement