Bit Counting

Write a function that takes an integer as input, and returns the number of bits that are equal to one in the binary representation of that number. You can guarantee that input is non-negative.

 

Example:

The binary representation of 1234 is 10011010010, so the function should return 5 in this case

 

Solution

unsigned int countBits(unsigned long long n){
  unsigned int result = 0;
  while(0 < n) {
    if(n % 2 == 1) result++;
    n = n / 2;
  }
  
  return result;
}

 

7097511의 코드

#include <limits>
#include <bitset>
inline constexpr unsigned int countBits(const unsigned long long n) noexcept {
  std::bitset<std::numeric_limits<unsigned long long>::digits> b(n);
  return b.count();
}

 

hobovsky의 코드

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

 

후기

중학생 때 배웠던 이진 수 만드는 방법으로 코드를 짜 봤다. 남들은 실행 속도가 느린 나누기나 나머지 연산 대신에 bit 연산을 했다. 혹은 bit 연산 관련의 STL을 사용했다. 아마 이 CodeKata에 시간제한이 있었다면, 나는 탈락. 앞으로 bit 얘기가 나오면 모든 비트를 쪼개서 풀어주어야겠다.

 

(url: https://www.codewars.com/kata/526571aae218b8ee490006f4/)