정수에서 1이 설정된 비트(Bit) 수 세기

보통 정수나 입력받은 값에 1이 몇개인지 셀경우가 있죠. 그때 사용하면 좋구요.

입력받은 어떤 정수값에서 1로 설정된 Bit 수가 몇개인지 셀때 public member function : bitset::count 를 사용한다.

Returns the amount of bits in the bitset that are set (i.e., have a value of 1).

이걸 올린 계기는 "생각하는 프로그래밍" 에 1장에 좋은 예를 보면서 한번 찾아봤습니다.

// bitset::count
#include <iostream>
#include <string>
#include <bitset>
using namespace std;
 
int main ()
{
  bitset<8> myset (string("10110011"));
 
  cout << "myset has " << int(myset.count()) << " ones ";
  cout << "and " << int(myset.size()-myset.count()) << " zeros.\n";
 
  return 0; 
}
 
 
output : 5, 3
 

이게 예제~ 출처가 http://www.cplusplus.com/ 

실제로 자기가 알고리즘을 짜서 해결할려면 이렇게 짠다.

int Number_of_Integer(int input_value)
{
 
         unsigned int number_of_bits_set = 0;
 
        for (; input_value > 0 ; input_value >>= 1)
 
        number_of_bits_set += input_value & 1;
        
        return number_of_bits_set;
}
 
 

더 빠른 방법들을 찾아보니, 아주 여러가지 방법이 있다.

아래 8가지 방법들의 코드와 검증코드, 비교까지 잘 ~

기억 : http://gurmeet.net/puzzles/fast-bit-counting-routines/

/* ==========================================================================

   Bit Counting routines



   Author: Gurmeet Singh Manku    (manku@cs.stanford.edu)

   Date:   27 Aug 2002

   ========================================================================== */
 
 
 
 
 
#include <stdlib.h>
 
#include <stdio.h>
 
#include <limits.h>
 
 
 
/* Iterated bitcount iterates over each bit. The while condition sometimes helps

   terminates the loop earlier */
 
int iterated_bitcount (unsigned int n)
 
{
 
    int count=0;    
 
    while (n)
 
    {
 
        count += n & 0x1u ;    
 
        n >>= 1 ;
 
    }
 
    return count ;
 
}
 
 
 
 
 
/* Sparse Ones runs proportional to the number of ones in n.

   The line   n &= (n-1)   simply sets the last 1 bit in n to zero. */
 
int sparse_ones_bitcount (unsigned int n)
 
{
 
    int count=0 ;
 
    while (n)
 
    {
 
        count++ ;
 
        n &= (n - 1) ;     
 
    }
 
    return count ;
 
}
 
 
 
 
 
/* Dense Ones runs proportional to the number of zeros in n.

   It first toggles all bits in n, then diminishes count repeatedly */
 
int dense_ones_bitcount (unsigned int n)
 
{
 
    int count = 8 * sizeof(int) ;   
 
    n ^= (unsigned int) -1 ;
 
    while (n)
 
    {
 
        count-- ;
 
        n &= (n - 1) ;    
 
    }
 
    return count ;
 
}
 
 
 
 
 
/* Precomputed bitcount uses a precomputed array that stores the number of ones

   in each char. */
 
static int bits_in_char [256] ;
 
 
 
void compute_bits_in_char (void)
 
{
 
    unsigned int i ;    
 
    for (i = 0; i < 256; i++)
 
        bits_in_char [i] = iterated_bitcount (i) ;
 
    return ;
 
}
 
 
 
int precomputed_bitcount (unsigned int n)
 
{
 
    // works only for 32-bit ints
 
    
 
    return bits_in_char [n         & 0xffu]
 
        +  bits_in_char [(n >>  8) & 0xffu]
 
        +  bits_in_char [(n >> 16) & 0xffu]
 
        +  bits_in_char [(n >> 24) & 0xffu] ;
 
}
 
 
 
 
 
/* Here is another version of precomputed bitcount that uses a precomputed array

   that stores the number of ones in each short. */
 
 
 
static char bits_in_16bits [0x1u << 16] ;
 
 
 
void compute_bits_in_16bits (void)
 
{
 
    unsigned int i ;    
 
    for (i = 0; i < (0x1u<<16); i++)
 
        bits_in_16bits [i] = iterated_bitcount (i) ;
 
    return ;
 
}
 
 
 
int precomputed16_bitcount (unsigned int n)
 
{
 
    // works only for 32-bit int
 
    
 
    return bits_in_16bits [n         & 0xffffu]
 
        +  bits_in_16bits [(n >> 16) & 0xffffu] ;
 
}
 
 
 
 
 
/* Parallel   Count   carries   out    bit   counting   in   a   parallel

   fashion.   Consider   n   after    the   first   line   has   finished

   executing. Imagine splitting n into  pairs of bits. Each pair contains

   the <em>number of ones</em> in those two bit positions in the original

   n.  After the second line has finished executing, each nibble contains

   the  <em>number of  ones</em>  in  those four  bits  positions in  the

   original n. Continuing  this for five iterations, the  64 bits contain

   the  number  of ones  among  these  sixty-four  bit positions  in  the

   original n. That is what we wanted to compute. */
 
 
 
#define TWO(c) (0x1u << (c))
 
#define MASK(c) (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
 
#define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
 
 
 
int parallel_bitcount (unsigned int n)
 
{
 
    n = COUNT(n, 0) ;
 
    n = COUNT(n, 1) ;
 
    n = COUNT(n, 2) ;
 
    n = COUNT(n, 3) ;
 
    n = COUNT(n, 4) ;
 
    /* n = COUNT(n, 5) ;    for 64-bit integers */
 
    return n ;
 
}
 
 
 
 
 
/* Nifty  Parallel Count works  the same  way as  Parallel Count  for the

   first three iterations. At the end  of the third line (just before the

   return), each byte of n contains the number of ones in those eight bit

   positions in  the original n. A  little thought then  explains why the

   remainder modulo 255 works. */
 
 
 
#define MASK_01010101 (((unsigned int)(-1))/3)
 
#define MASK_00110011 (((unsigned int)(-1))/5)
 
#define MASK_00001111 (((unsigned int)(-1))/17)
 
 
 
int nifty_bitcount (unsigned int n)
 
{
 
    n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
 
    n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
 
    n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;        
 
    return n % 255 ;
 
}
 
 
 
/* MIT Bitcount



   Consider a 3 bit number as being

        4a+2b+c

   if we shift it right 1 bit, we have

        2a+b

  subtracting this from the original gives

        2a+b+c

  if we shift the original 2 bits right we get

        a

  and so with another subtraction we have

        a+b+c

  which is the number of bits in the original number.



  Suitable masking  allows the sums of  the octal digits  in a 32 bit  number to

  appear in  each octal digit.  This  isn't much help  unless we can get  all of

  them summed together.   This can be done by modulo  arithmetic (sum the digits

  in a number by  molulo the base of the number minus  one) the old "casting out

  nines" trick  they taught  in school before  calculators were  invented.  Now,

  using mod 7 wont help us, because our number will very likely have more than 7

  bits set.   So add  the octal digits  together to  get base64 digits,  and use

  modulo 63.   (Those of you  with 64  bit machines need  to add 3  octal digits

  together to get base512 digits, and use mod 511.)

 

  This is HACKMEM 169, as used in X11 sources.

  Source: MIT AI Lab memo, late 1970's.

*/
 
 
 
int mit_bitcount(unsigned int n)
 
{
 
    /* works for 32-bit numbers only */
 
    register unsigned int tmp;
 
    
 
    tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
 
    return ((tmp + (tmp >> 3)) & 030707070707) % 63;
 
}
 
 
 
void verify_bitcounts (unsigned int x)
 
{
 
    int iterated_ones, sparse_ones, dense_ones ;
 
    int precomputed_ones, precomputed16_ones ;
 
    int parallel_ones, nifty_ones ;
 
    int mit_ones ;
 
    
 
    iterated_ones      = iterated_bitcount      (x) ;
 
    sparse_ones        = sparse_ones_bitcount   (x) ;
 
    dense_ones         = dense_ones_bitcount    (x) ;
 
    precomputed_ones   = precomputed_bitcount   (x) ;
 
    precomputed16_ones = precomputed16_bitcount (x) ;
 
    parallel_ones      = parallel_bitcount      (x) ;
 
    nifty_ones         = nifty_bitcount         (x) ;
 
    mit_ones           = mit_bitcount           (x) ;
 
 
 
    if (iterated_ones != sparse_ones)
 
    {
 
        printf ("ERROR: sparse_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
    
 
    if (iterated_ones != dense_ones)
 
    {
 
        printf ("ERROR: dense_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
 
 
    if (iterated_ones != precomputed_ones)
 
    {
 
        printf ("ERROR: precomputed_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
        
 
    if (iterated_ones != precomputed16_ones)
 
    {
 
        printf ("ERROR: precomputed16_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
    
 
    if (iterated_ones != parallel_ones)
 
    {
 
        printf ("ERROR: parallel_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
 
 
    if (iterated_ones != nifty_ones)
 
    {
 
        printf ("ERROR: nifty_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
 
 
    if (mit_ones != nifty_ones)
 
    {
 
        printf ("ERROR: mit_bitcount (0x%x) not okay!\n", x) ;
 
        exit (0) ;
 
    }
 
    
 
    return ;
 
}
 
 
 
 
 
int main (void)
 
{
 
    int i ;
 
    
 
    compute_bits_in_char () ;
 
    compute_bits_in_16bits () ;
 
 
 
    verify_bitcounts (UINT_MAX) ;
 
    verify_bitcounts (0) ;
 
    
 
    for (i = 0 ; i < 100000 ; i++)
 
        verify_bitcounts (lrand48 ()) ;
 
    
 
    printf ("All bitcounts seem okay!\n") ;
 
    
 
    return 0 ;
 
}

도움이 되엇으면 좋겠네요~ 대한민국 개발자 만세 !  거침없이 전진하라 !