/**
* Counts number of 1 bits in a 32 bit unsigned number.
*
* @param x unsigned 32 bit number whose bits you wish to count.
*
* @return number of 1 bits in x.
* @author Roedy Green email
*/
public static int countBits(int x ) {
// collapsing partial parallel sums method
// collapse 32x1 bit counts to 16x2 bit counts, mask 01010101
x = (x >>> 1 & 0x55555555) + (x & 0x55555555);
// collapse 16x2 bit counts to 8x4 bit counts, mask 00110011
x = (x >>> 2 & 0x33333333) + (x & 0x33333333);
// collapse 8x4 bit counts to 4x8 bit counts, mask 00001111
x = (x >>> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
// collapse 4x8 bit counts to 2x16 bit counts
x = (x >>> 8 & 0x00ff00ff) + (x & 0x00ff00ff);
// collapse 2x16 bit counts to 1x32 bit count
return(x >>> 16) + (x & 0x0000ffff);
}
루프 돌리는 것보다 5배 빠르다는데 비교해 보실분?
----
I paint objects as I think them, not as I see them. atie's minipage
MSDN에서 본겁니다.
WORD GetNumberOfBits( DWORD dwMask ) { WORD wBits = 0; while( dwMask ) { dwMask = dwMask & ( dwMask - 1 ); wBits++; } return wBits; }MSDN에서 본겁니다. 자주 애용하고 있는 코드기도 하구요.
아, 그리고,
여기서 갯수는 개수로 써야 합니다.
재미있는 코드네요.
댓글 남겨서 기억해놓으렵니다.
저는 이렇게 생각했습니다.
비트연산 공부하시는 것 아니라면 표로 만드세요..bits_in_b
비트연산 공부하시는 것 아니라면 표로 만드세요..
bits_in_byte[256] = {0, 1, 1, 2, ...., 8};
#define NBITS(x) bits_in_byte[(unsigned char)(x)]
이와 비슷한 스레드가 byte 의 bit들을 뒤집는 것이 있었는데,
한번 검색해 보세요.
Re: MSDN에서 본겁니다.
갯수는 어떨 때 쓰죠? 잘못된 말인가요?
C++입니다. :) [code:1]#include <bitset
C++입니다. :)
#include <bitset> #include <limits> void f() { std::bitset<std::numeric_limits<unsigned char>::digits> c; size_t n = c.count(); }Re: MSDN에서 본겁니다.
인터넷으로 검색해보니 개수도 한자어인데 두음절로 된 한자어의 경우 아래 여섯 단어를 제외하고는 모두 사이시옷이 안들어간다는군요
곳간(庫間), 셋방(貰房), 숫자(數字), 찻간(車間), 툇간(退間), 횟수(回數)
그래서 갯수 -> 개수 :)
소수(prime)에게도 사이시옷을 허하라! (생뚱맞게)
소수(prime)에게도 사이시옷을 허하라! (생뚱맞게)
걍.. 비트 연산 하면..
int getNumBits(unsigned char in) { int i, count; for(i=0, count=0; i<8 ; i++) { if(in & (ox01 <<i)) count++; } return count; }물론 테스트는 안한 코드입니다.ㅠ_ㅠ;
A few Good Man
브라이언 커니건의 비트 카운트 입니다. 처음 봤을때 많이 신기해서
브라이언 커니건의 비트 카운트 입니다.
처음 봤을때 많이 신기해서 저장해놨었네요..
int bitcnt(int n) { int c, v=n; for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set } return c; }삽질의 대마왕...
[quote="barmi"][code:1]WORD GetNumberOfB
같은 겁니다... :)
항상 가능한 것은 아니지만
속도를 요구하는 트릭이라면 1차원배열[256]을 써도 됩니다. array[x]="x의true비트수" 가 되는 배열 array를 만들면 되지요.
그런데... 이경우는 로직자체가 간단해서 속도의 잇점이 없겠군요. :cry:
homeless
partial sum collapsing method
/** * Counts number of 1 bits in a 32 bit unsigned number. * * @param x unsigned 32 bit number whose bits you wish to count. * * @return number of 1 bits in x. * @author Roedy Green email */ public static int countBits(int x ) { // collapsing partial parallel sums method // collapse 32x1 bit counts to 16x2 bit counts, mask 01010101 x = (x >>> 1 & 0x55555555) + (x & 0x55555555); // collapse 16x2 bit counts to 8x4 bit counts, mask 00110011 x = (x >>> 2 & 0x33333333) + (x & 0x33333333); // collapse 8x4 bit counts to 4x8 bit counts, mask 00001111 x = (x >>> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f); // collapse 4x8 bit counts to 2x16 bit counts x = (x >>> 8 & 0x00ff00ff) + (x & 0x00ff00ff); // collapse 2x16 bit counts to 1x32 bit count return(x >>> 16) + (x & 0x0000ffff); }루프 돌리는 것보다 5배 빠르다는데 비교해 보실분?
----
I paint objects as I think them, not as I see them.
atie's minipage
헐.. 이해하는데 한 5분걸렸습니다... 정말 생각도
헐.. 이해하는데 한 5분걸렸습니다... 정말 생각도 못한 방법이네요... 정만 똑똑한 사람들 많습니다...
가장 빠른 건 프로세스의 카운터 구하는 명령을 이용하는게 아닐까요?
알고리즘 적인 것이라면 이미 나온 것이고,
비트 수 구하는 것은 CPU 명령으로도 있습니다.
Visual C++ 이라면 __popcnt16, __popcnt, __popcnt64 등을 => https://msdn.microsoft.com/ko-kr/library/bb385231.aspx
GCC같은 GNU계열이라면 __builtin_popcount() 를 이용하시면 됩니다. => https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
댓글 달기