countNumberOfOnes

Walkthrough

To solve this problem, we can use bitwise operators to count the number of 1 bits in an unsigned 32-bit integer.

function countNumberOf1Bits(number) {
  let result = 0;

  // Remove every other bit
  let everyOtherBitRemoved = number & 0x55555555;

  // Shift removed bits up and add pairs
  let removedBitsShiftedUp = (number >> 1) & 0x55555555;
  let sumOfEachPair = everyOtherBitRemoved + removedBitsShiftedUp;

  // Zero out every other pair of bits
  sumOfEachPair = (sumOfEachPair & 0x33333333) + ((sumOfEachPair >> 2) & 0x33333333);
  sumOfEachPair = (sumOfEachPair & 0x0f0f0f0f) + ((sumOfEachPair >> 4) & 0x0f0f0f0f);
  sumOfEachPair = (sumOfEachPair & 0x00ff00ff) + ((sumOfEachPair >> 8) & 0x00ff00ff);
  sumOfEachPair = (sumOfEachPair & 0x0000ffff) + ((sumOfEachPair >> 16) & 0x0000ffff);

  // Add the number of 1 bits
  result = sumOfEachPair;

  return result;
}

The first step is to create a variable called "everyOtherBitRemoved" that will contain a binary representation that alternates between zeroes and ones. We will use a bitwise AND operation to remove every other bit from the original number. We choose the value "0xAAAAAAAA" to perform the AND operation, which represents a 32-bit integer with alternating bits of 1 and 0. The "x" in "0x" indicates that the following characters are in hexadecimal notation, which is a base-16 numbering system that uses digits 0-9 and letters A-F to represent values. In this case, "A" represents the value 1010 in binary, so "0xAAAAAAAA" represents the binary number 10101010101010101010101010101010.

The next step is to right shift the number once and perform a bitwise AND operation with the same value as before to obtain the removed bits aligned up. The reason we shift the number to the right by one is that we want to obtain the removed bits from the adjacent positions to those we previously removed. We choose the value "0xAAAAAAAA" again to perform the AND operation because it will give us the same result as before, but with the bits shifted over by one position.

Next, we add every other bit removed and removed bits aligned up by creating a variable called "sumOfPairs". This step effectively adds pairs of adjacent bits that we have removed, resulting in each pair holding the sum of that pair in the original value.

The next step is to find the sum of every pair of bits holding the sum of that pair in the original value by zeroing out every other pair of bits. We choose the value "0x33333333" to perform the bitwise AND operation, which represents a 32-bit integer with alternating pairs of zeroes and ones. This value is obtained by performing an OR operation on two 16-bit integers with the value "0x3333" (which represents the binary number 0011001100110011) and then shifting the result over by 16 bits. We perform the bitwise AND operation on "sumOfPairs" and "0x33333333" to set every other pair of bits to zero, effectively zeroing out all pairs except for the pairs that hold the sum of the original bits.

Finally, we add the groups of pairs together starting with groups of 4, then groups of 8, then groups of 16, and finally the entire 32-bit integer. We perform a bitwise AND operation with corresponding values for each group and then bit shift the result by the number of bits in that group. This effectively adds up the bits in each group and returns the total number of 1 bits in the 32-bit integer.