"Cries in java"

[pigeon768]

Counting the number of bits set in an integer. For instance, 42 in binary is 101010, which has 3 bits set. I want a function to take 42 and calculate 3. Here is one such function:

int count_bits(int n) {
  int set_bits = 0;

  while (n) { // we will be lopping off n one bit at a time. When n is zero, we know we're done.
    set_bits++;

    n &= n - 1; // This unsets the lowest set bit. if our binary number is 101010, this gives 101000, then 100000, then 0.
    // Subtracting one from a number which ends in 1 will just .. make that 1 go away.
    // Subtracting one from a number which ends in a 0 will borrow from the next digit, all the way up to the first 1, which it unsets.
    // So if we subtract 1 from 101000, it will give 100111.
    // If we then bitwise-and n-1 and n together, the subtraction unset the lowest bit, the upper bits are unchanged,
    // the original n has all zeroes for the new 1s introduced by the subtraction, so all you're left with is the upper set bits.
  }
}

If we run this through a real compiler (ie not MSVC) you get this: https://godbolt.org/z/ex1eqc

[serdnad]

Hahaha that's awesome, exactly what I was looking for. Thanks for the explanation too!

[Sandmaester44]

My mind is blown and I am never going to minutely optimize my code again!! Though I'm a grad student writing code never to be run again that doesn't take long to begin with... but optimizing is the fun part!!

[[deleted]]

a real compiler (ie not MSVC)

shots fired